基于区域划分与降维的高维学习型索引
作者:
作者单位:

作者简介:

张少敏(1996-),男,硕士生,主要研究领域为索引技术与机器学习;蔡盼(1994-),女,博士生,主要研究领域为数据库系统与学习型索引;李翠平(1971-),女,博士,教授,博士生导师,CCF杰出会员,主要研究领域为社交网络分析,社会推荐,大数据分析及挖掘;陈红(1965-),女,博士,教授,博士生导师,CCF杰出会员,主要研究领域为数据库技术,新硬件平台下的高性能计算

通讯作者:

李翠平,licuiping@ruc.edu.cn

中图分类号:

TP311

基金项目:

国家重点研发计划(2018YFB1004401);国家自然科学基金(61772537,61772536,62076245,62072460)


High-dimensional Learned Index Based on Space Division and Dimension Reduction
Author:
Affiliation:

Fund Project:

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

    在数据量与数据复杂度不断增加的时代,大数据处理与分析成为当前的热门研究内容,高维空间数据的使用越来越频繁,数据检索和访问速度成了衡量数据处理系统性能的重要指标.因此,如何设计实现一种高效的高维索引结构,提高查询访问速率、降低内存占用,变得至关重要.近年,Kraska等人提出了学习型索引的方法.实验证明该方法在真实数据集上表现良好.之后机器学习与深度学习在数据库系统中的运用越来越广泛.众多研究者尝试在高维数据上构建学习型索引,来提升高维数据的查询速度.但是目前的高维学习型索引采用的方法并不能将数据分布的信息有效利用起来,而且过于复杂的深度学习模型使得索引初始化开销过大.结合空间区域划分与降维两种技术,提出一种新颖的高维学习型索引.它能更有效地利用数据分布信息提高索引的查询效率,并利用多段线性模型在保证查找精确度的前提下尽可能减少索引初始化的开销.分别在随机生成的数据集和开源街区地图数据集上进行实验验证.结果表明,与现有的高维索引相比,其在索引构建、查询效率、以及内存占用方面都有显著提高.

    Abstract:

    In recent years, the prevalent research on big-data processing often deals with increased data scale and high data complexity. The frequent usage of high-dimensional data poses challenges during application, such as efficient query and fast access of database in the system. Hence, it is critical to design an effective high-dimensional index to increase query throughput and decrease memory footage. Kraska et al. proposed learned index, which has been proved superior in real-world low-dimensional datasets. With the success of wide adoption of machine learning and deep learning on database management system, more and more researchers aim to set up learned index on high-dimensional datasets so as to improve the query efficiency. However, current solutions fail to effectively utilize the distribution information of data, and sometimes incur high overhead on the initialization of complex deep learning models. In this work, an improved high-dimensional learned index (IHDL index) is proposed based on the division of data space and dimension reduction. Specifically, the index utilizes multiple linear models on the dataset, and decreases the initialization overhead while maintains high query accuracy. Experiments on the synthetic dataset and the OSM dataset verifyits superiority in terms of initialization overhead, query throughput, and memory footage.

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

张少敏,蔡盼,李翠平,陈红.基于区域划分与降维的高维学习型索引.软件学报,2023,34(5):2413-2426

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

京公网安备 11040202500063号