主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第6期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
高远宁,叶金标,杨念祖,高晓沨,陈贵海.基于中间层的可扩展学习索引技术.软件学报,2020,31(3):620-633
基于中间层的可扩展学习索引技术
Middle Layer Based Scalable Learned Index Scheme
投稿时间:2019-07-20  修订日期:2019-11-25
DOI:10.13328/j.cnki.jos.005910
中文关键词:  学习索引  聚类  神经网络  动态更新
英文关键词:learned index  clustering  neural network  dynamic update
基金项目:国家重点研发计划(2018YFB1004700);国家自然科学基金(61872238,61972254,61832005);上海市科技创新行动计划(17510740200);CCF-华为数据库创新研究计划(CCF-Huawei DBIR2019002A)
作者单位E-mail
高远宁 上海市可扩展计算与系统重点实验室, 上海 200240
上海交通大学 计算机科学与工程系, 上海 200240 
 
叶金标 上海市可扩展计算与系统重点实验室, 上海 200240
上海交通大学 计算机科学与工程系, 上海 200240 
 
杨念祖 上海市可扩展计算与系统重点实验室, 上海 200240
上海交通大学 计算机科学与工程系, 上海 200240 
 
高晓沨 上海市可扩展计算与系统重点实验室, 上海 200240
上海交通大学 计算机科学与工程系, 上海 200240 
gao-xf@cs.sjtu.edu.cn 
陈贵海 上海市可扩展计算与系统重点实验室, 上海 200240
上海交通大学 计算机科学与工程系, 上海 200240 
 
摘要点击次数: 660
全文下载次数: 555
中文摘要:
      在大数据与云计算时代,数据访问速度是衡量大规模存储系统性能的一个重要指标.因此,如何设计一种轻量、高效的数据索引结构,从而满足系统高吞吐率、低内存占用的需求,是当前数据库领域的研究热点之一.Kraska等人提出使用机器学习模型代替传统的B树索引,并在真实数据集上取得了不错的效果,但其提出的模型假设工作负载是静态的、只读的,对于索引更新问题没有提出很好的解决办法.提出了基于中间层的可扩展的学习索引模型Dabble,用来解决索引更新引发的模型重训练问题.首先,Dabble模型利用K-Means聚类算法将数据集划分为K个区域,并训练K个神经网络分别学习不同区域的数据分布.在模型训练阶段,创新性地把数据的访问热点信息融入到神经网络中,从而提高模型对热点数据的预测精度.在数据插入时,借鉴了LSM树延迟更新的思想,提高了数据写入速度.在索引更新阶段,提出一种基于中间层的机制将模型解耦,从而缓解由于数据插入带来的模型更新问题.分别在Lognormal数据集以及Weblogs数据集上进行实验验证,结果表明,与当前先进的方法相比,Dabble模型在查询以及索引更新方面都取得了非常好的效果.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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