主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第6期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李梁,吴刚,王国仁.面向数据特征的内存跳表优化技术.软件学报,2020,31(3):663-679
面向数据特征的内存跳表优化技术
In-memory Skiplist Optimization Technologies Based on Data Feature
投稿时间:2019-07-19  修订日期:2019-11-25
DOI:10.13328/j.cnki.jos.005902
中文关键词:  内存索引  跳表  机器学习  密度估计
英文关键词:in-memory index  skiplist  machine learning  density estimation
基金项目:国家自然科学基金(61872072,U1811262,61572119,61622202,61672145,61732003,61572121,61332006,61332014,61328202,61702087);中央高校基本科研业务费专项资金(N181605012,N171604007,N171904007);中国博士后科学基金(2018M631358)
作者单位E-mail
李梁 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169  
吴刚 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
计算机软件新技术国家重点实验室(南京大学), 江苏 南京 210093 
 
王国仁 北京理工大学 计算机学院, 北京 100081 wanggr@bit.edu.cn 
摘要点击次数: 589
全文下载次数: 316
中文摘要:
      跳表作为数据库中被广泛采用的索引技术,优点在于可以达到类似折半查找的复杂度O(log(n)).但是标准跳表算法中,结点的层数是通过随机算法生成的,这就导致跳表的性能是不稳定的.在极端情况下,查找复杂度会退化到On).这是因为经典跳表结构没有结合数据的特征.一个稳定的跳表结构应该充分考虑数据的分布特征去决定结点层数.基于核密度估计的方式估计数据累积分布函数,预测数据在跳表中的位置,进而设计用于判定结点层数的跳表算法.另外,跳表的查找过程中,结点层数越大的结点被访问的概率越高.针对历史数据的访问频次,设计一种保证频繁访问的"热"数据尽可能地在跳表的上层,而访问较少的"冷"数据在跳表的下层的跳表算法.最后,基于合成数据和真实数据对标准跳表和5种改进的跳表算法进行了全面的实验评估并开源代码.实验结果表明,优化的跳表最高可以获取60%的性能提升.这为未来的科研工作者和系统开发人员指出了一个很好的方向.
英文摘要:
      Skiplist is a widely used indexing technology in the database systems. The advantage is that the complexity of skiplist is O(log(n)). However, in the standard skiplist algorithm, the level of each nodes is generated by a random generator, thus, the performance of the skiplist is unstable. In extreme case, the searching complexity deceases to O(n) which is similar to the list searching time. This is because the classic skiplist do not combine data features to generate its structure. It is believed that a stable skiplist structure should fully consider the distribution characteristics of the data to determine the number of node levels. This study estimates the data cumulative distribution function based on the kernel density estimation method, and predicts the position of the data in the skiplist, determines the number of node levels. In addition, it is found that the node with a higher level has a higher probability of being accessed. This study also focuses on the access frequency and the hot data of frequent access, make sure that the upper level of the skiplist is hot data, and access the less cold data in the lower level of skiplist. Finally, a comprehensive experimental evaluation of the six kinds of skiplist algorithms is performed based on the synthesis dataset and real dataset, besides, the source code is open. The results show that the best skiplist algorithm can achieve a 60% performance improvement, which points out a authentic direction for the future researchers and system developers.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利