In-memory Skiplist Optimization Technologies Based on Data Feature
Author:
Affiliation:

Clc Number:

Fund Project:

National Natural Science Foundation of China (61872072, U1811262, 61572119, 61622202, 61672145, 61732003, 61572121, 61332006, 61332014, 61328202, 61702087); Fundamental Research Funds for the Central Universities (N181605012, N171604007, N171904007); China Postdoctoral Science General Program Foundation (2018M631358)

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    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.

    Reference
    Related
    Cited by
Get Citation

李梁,吴刚,王国仁.面向数据特征的内存跳表优化技术.软件学报,2020,31(3):663-679

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 19,2019
  • Revised:November 25,2019
  • Adopted:
  • Online: January 10,2020
  • Published: March 06,2020
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063