主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
高远宁,叶金标,杨念祖,高晓沨,陈贵海.基于中间层的可扩展学习索引技术.软件学报,2020,31(3):0
基于中间层的可扩展学习索引技术
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 gao-xf@cs.sjtu.edu.cn 
陈贵海 上海市可扩展计算与系统重点实验室, 计算机科学与工程系, 上海交通大学, 上海 200240  
摘要点击次数: 44
全文下载次数: 11
中文摘要:
      在大数据与云计算时代,数据访问速度是衡量大规模存储系统性能的一个重要指标.因此,如何设计一种轻量、高效的数据索引结构,从而满足系统高吞吐率、低内存占用的需求,是当前数据库领域的研究热点之一.近期,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 using machine learning models instead of traditional B-tree indexes, and achieved remarkable results on real data sets. However, the proposed model assumes that the workload is static and read-only, failing to handle the index update problem. In this paper, we propose 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, we innovatively integrate the data access patterns into the neural network, which can improve the prediction accuracy of the model for hotspot data. For data insertion, we borrowed the idea of LSM tree, i.e., delay update mechanism, which greatly improved the data writing speed. In the index update phase, we propose a middle layer based mechanism for model decoupling, thus easing the problem of index updating cost. We evaluate Dabble model on two datasets, the Lognormal distribution dataset and the real-world Weblogs dataset. The experiment results demonstrate the effectiveness and efficiency of our 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
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利