基于中间层的可扩展学习索引技术
CSTR:
作者:
作者单位:

作者简介:

高远宁(1994-),男,山东平阴人,博士生,主要研究领域为数据工程,数据库索引;高晓沨(1982-),女,博士,教授,博士生导师,CCF专业会员,主要研究领为数据库索引,算法设计与优化;叶金标(1998-),男,本科生,主要研究领域为数据库索引,机器学习;陈贵海(1963-),男,博士,教授,博士生导师,CCF会士,主要研究领为云计算,分布式系统,无线网络;杨念祖(1999-),男,本科生,主要研究领域为数据库索引,机器学习.

通讯作者:

高晓沨,E-mail:gao-xf@cs.sjtu.edu.cn

中图分类号:

基金项目:

国家重点研发计划(2018YFB1004700);国家自然科学基金(61872238,61972254,61832005);上海市科技创新行动计划(17510740200);CCF-华为数据库创新研究计划(CCF-Huawei DBIR2019002A)


Middle Layer Based Scalable Learned Index Scheme
Author:
Affiliation:

Fund Project:

National Key Research and Development Program of China (2018YFB1004700); National Natural Science Foundation of China (61872238, 61972254, 61832005); Shanghai Science and Technology Fund (17510740200); CCF-Huawei Database System Innovation Research Plan (CCF-Huawei DBIR2019002A)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    在大数据与云计算时代,数据访问速度是衡量大规模存储系统性能的一个重要指标.因此,如何设计一种轻量、高效的数据索引结构,从而满足系统高吞吐率、低内存占用的需求,是当前数据库领域的研究热点之一.Kraska等人提出使用机器学习模型代替传统的B树索引,并在真实数据集上取得了不错的效果,但其提出的模型假设工作负载是静态的、只读的,对于索引更新问题没有提出很好的解决办法.提出了基于中间层的可扩展的学习索引模型Dabble,用来解决索引更新引发的模型重训练问题.首先,Dabble模型利用K-Means聚类算法将数据集划分为K个区域,并训练K个神经网络分别学习不同区域的数据分布.在模型训练阶段,创新性地把数据的访问热点信息融入到神经网络中,从而提高模型对热点数据的预测精度.在数据插入时,借鉴了LSM树延迟更新的思想,提高了数据写入速度.在索引更新阶段,提出一种基于中间层的机制将模型解耦,从而缓解由于数据插入带来的模型更新问题.分别在Lognormal数据集以及Weblogs数据集上进行实验验证,结果表明,与当前先进的方法相比,Dabble模型在查询以及索引更新方面都取得了非常好的效果.

    Abstract:

    In the era of big data and cloud computing, efficient data access is an important metric to measure the performance of a large-scale storage system. Therefore, design a lightweight and efficient index structure, which can meet the system's demand for high throughput and low memory footprint, is one of the research hotspots in the current database field. Recently, Kraska, et al proposed to use the machine learning models instead of traditional B-tree indexes, and remarkable results are achieved on real data sets. However, the proposed model assumes that the workload is static and read-only, failing to handle the index update problem. This study proposes Dabble, a middle layer based scalable learning index model, which is used to mitigate the index update problem. Dabble first uses K-means algorithm to divide the data set into K regions, and trains K neural networks to learn the data distribution of different regions. During the training phase, it innovatively integrates the data access patterns into the neural network, which can improve the prediction accuracy of the model for hotspot data. For data insertion, it borrows the idea of LSM tree, i.e., delay update mechanism, which greatly improved the data writing speed. In the index update phase, a middle layer based mechanism is proposed for model decoupling, thus easing the problem of index updating cost. Dabble model is evaluated on two datasets, the Lognormal distribution dataset and the real-world Weblogs dataset. The experiment results demonstrate the effectiveness and efficiency of the proposed model compared with the state-of-the-art methods.

    参考文献
    相似文献
    引证文献
引用本文

高远宁,叶金标,杨念祖,高晓沨,陈贵海.基于中间层的可扩展学习索引技术.软件学报,2020,31(3):620-633

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2019-07-20
  • 最后修改日期:2019-11-25
  • 录用日期:
  • 在线发布日期: 2020-01-10
  • 出版日期: 2020-03-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号