| 本文已被：浏览 1633次 下载 4003次 |
码上扫一扫！ |
|
|
| 基于区域划分与降维的高维学习型索引 |
|
张少敏1,2, 蔡盼1,2, 李翠平1,2, 陈红1,2
|
|
1.数据工程与知识工程教育部重点实验室 (中国人民大学), 北京 100872;2.中国人民大学 信息学院, 北京 100872
|
|
| 摘要: |
| 在数据量与数据复杂度不断增加的时代，大数据处理与分析成为当前的热门研究内容，高维空间数据的使用越来越频繁，数据检索和访问速度成了衡量数据处理系统性能的重要指标.因此，如何设计实现一种高效的高维索引结构，提高查询访问速率、降低内存占用，变得至关重要.近年，Kraska等人提出了学习型索引的方法.实验证明该方法在真实数据集上表现良好.之后机器学习与深度学习在数据库系统中的运用越来越广泛.众多研究者尝试在高维数据上构建学习型索引，来提升高维数据的查询速度.但是目前的高维学习型索引采用的方法并不能将数据分布的信息有效利用起来，而且过于复杂的深度学习模型使得索引初始化开销过大.结合空间区域划分与降维两种技术，提出一种新颖的高维学习型索引.它能更有效地利用数据分布信息提高索引的查询效率，并利用多段线性模型在保证查找精确度的前提下尽可能减少索引初始化的开销.分别在随机生成的数据集和开源街区地图数据集上进行实验验证.结果表明，与现有的高维索引相比，其在索引构建、查询效率、以及内存占用方面都有显著提高. |
| 关键词: 学习型索引 高维数据 希尔伯特曲线 机器学习 |
| DOI：10.13328/j.cnki.jos.006414 |
| 分类号:TP311 |
| 基金项目:国家重点研发计划（2018YFB1004401）；国家自然科学基金（61772537，61772536，62076245，62072460） |
|
| High-dimensional Learned Index Based on Space Division and Dimension Reduction |
|
ZHANG Shao-Min1,2, CAI Pan1,2, LI Cui-Ping1,2, CHEN Hong1,2
|
|
1.Key Laboratory of Data Engineering and Knowledge Engineering of the Ministry of Education (Renmin University of China), Beijing 100872, China;2.School of Information, Renmin University of China, Beijing 100872, China
|
| 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. |
| Key words: learned index high-dimensional index Hilbert curve machine learning |
