Page 6 - 《软件学报》2026年第2期
P. 6
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(2):485−507 [doi: 10.13328/j.cnki.jos.007570] [CSTR: 32375.14.jos.007570] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
*
LA-tree: 查询感知的自适应学习型多维索引
刘佳伟 1,2 , 范 举 2,1 , 张 超 1 , 杜小勇 1,2
1
(中国人民大学 信息学院, 北京 100872)
2
(数据工程与知识工程教育部重点实验室 (中国人民大学), 北京 100872)
通信作者: 范举, E-mail: fanj@ruc.edu.cn
摘 要: 结构化数据分析通常需要在表格数据的多维属性上执行联合范围查询, 高效的多维索引因此成为数据库
系统的关键支撑. 然而, 现有多维索引方法在高维场景下存在局限: 传统多维索引仅按数据分布进行均匀划分, 缺
乏对查询特征的感知, 导致筛选效果有限; 而现有学习型多维索引虽引入查询感知, 但划分往往极不均匀, 使部分
单元过大, 扫描成本显著增加. 为了解决上述问题, 提出一种新型的 LA-tree 学习型树形多维索引, 同时兼顾数据分
布与查询负载感知. 在离线构建阶段, LA-tree 将节点维度选择建模为最小化查询扫描比的问题, 并提出分层贪心
搜索算法, 实现了均匀划分与查询感知的统一. 在在线查询阶段, 引入轻量线性模型与分段线性模型, 将传统的数
值比较转化为快速映射计算, 在保证结果完整性的同时显著降低筛选延迟. 在动态场景中, 提出基于扫描量监控的
自适应增量更新机制, 通过局部子树重构高效适配数据与查询负载的变化, 避免了整体索引重建的高昂代价. 实验
结果表明, LA-tree 在多个真实和基准数据集上均显著优于现有方法: 在静态场景中查询用时较最佳基准方法平均
降低 52%, 在动态场景中更新开销较重构方法减少 97%, 同时保持低查询延迟与轻量级索引规模.
关键词: 学习型多维索引; 查询感知; 索引更新
中图法分类号: TP311
中文引用格式: 刘佳伟, 范举, 张超, 杜小勇. LA-tree: 查询感知的自适应学习型多维索引. 软件学报, 2026, 37(2): 485–507. http://
www.jos.org.cn/1000-9825/7570.htm
英文引用格式: Liu JW, Fan J, Zhang C, Du XY. LA-tree: Query-aware Adaptive Learned Multi-dimensional Index. Ruan Jian Xue
Bao/Journal of Software, 2026, 37(2): 485–507 (in Chinese). http://www.jos.org.cn/1000-9825/7570.htm
LA-tree: Query-aware Adaptive Learned Multi-dimensional Index
1
1,2
2,1
LIU Jia-Wei , FAN Ju , ZHANG Chao , DU Xiao-Yong 1,2
1
(School of Information, Renmin University of China, Beijing 100872, China)
2
(Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University), Ministry of Education, Beijing 100872, China)
Abstract: Structured data analysis typically requires performing multi-attribute queries over tabular data, making efficient multi-
dimensional indexes key support for database systems. However, existing multi-dimensional indexing methods face limitations in high-
dimensional scenarios. Traditional multi-dimensional indexing methods partition data uniformly based on data distribution but lack the
awareness of query features, resulting in limited filtering effectiveness. In contrast, although existing learned multi-dimensional indexes
introduce query-awareness, they often produce highly unbalanced partitions, thereby resulting in some oversized partitions and substantially
increased scanning costs. To this end, this study proposes LA-tree, a novel learned tree-based multi-dimensional index that balances both
data distribution and query workload awareness. In the offline construction phase, LA-tree formulates the selection of partitioning
dimensions at each node as an optimization problem of minimizing the overall scan ratio of the query workload, and puts forward a
hierarchical greedy search algorithm to achieve the unity of uniform partitioning and query-awareness. In the online query phase, the
* 基金项目: 国家自然科学基金 (62436010, 62502520); 北京市自然科学基金-海淀原始创新联合基金 (L222006)
收稿时间: 2025-09-01; 修改时间: 2025-10-07; 采用时间: 2025-10-30; jos 在线出版时间: 2025-12-10
CNKI 网络首发时间: 2025-12-11
