Page 346 - 《软件学报》2025年第8期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(8):3769−3786 [doi: 10.13328/j.cnki.jos.007220] [CSTR: 32375.14.jos.007220] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
DRAMA: 更新分布感知的学习型索引

郭 娜 1,2 , 王雅琪 2 , 姜皓南 2 , 谷 峪 1 , 夏秀峰 2

1
(东北大学 计算机科学与工程学院, 辽宁 沈阳 110167)
2
(沈阳航空航天大学 计算机学院, 辽宁 沈阳 110136)
通信作者: 谷峪, E-mail: guyu@mail.neu.edu.cn

摘 要: 学习型索引因其低内存占用和高查询性能的特点, 正辅助或逐步取代传统的索引结构. 然而, 数据更新导
致的在线重新训练使其无法适应数据频繁更新的场景. 为了在不过多消耗内存的前提下尽量避免由于数据频繁更
新导致的索引重构, 提出了一种自适应的感知更新分布学习型索引结构 DRAMA. 使用类 LSM-Tree 的延迟学习方
式主动学习数据更新的分布特征; 利用近似拟合技术快速建立更新分布模型; 采用模型合并策略代替频繁的重训
练过程; 采用一种混合压缩技术降低索引中模型参数的内存占用率. 在真实和合成的数据集上构建了索引并进行
验证. 结果表明, 相比于传统索引和最先进的学习型索引, 该索引可以在不额外消耗过多内存的情况下, 有效降低
数据更新环境下的查询延迟.
关键词: 学习型索引; 更新分布; 压缩策略; 延迟学习; 近似拟合; 模型合并
中图法分类号: TP311

中文引用格式: 郭娜, 王雅琪, 姜皓南, 谷峪, 夏秀峰. DRAMA: 更新分布感知的学习型索引. 软件学报, 2025, 36(8): 3769–3786.
http://www.jos.org.cn/1000-9825/7220.htm
英文引用格式: Guo N, Wang YQ, Jiang HN, Gu Y, Xia XF. DRAMA: Update-distribution-aware Learned Index. Ruan Jian Xue
Bao/Journal of Software, 2025, 36(8): 3769–3786 (in Chinese). http://www.jos.org.cn/1000-9825/7220.htm

DRAMA: Update-distribution-aware Learned Index
2
2
1,2
1
GUO Na , WANG Ya-Qi , JIANG Hao-Nan , GU Yu , XIA Xiu-Feng 2
1
(School of Computer Science and Engineering, Northeastern University, Shenyang 110167, China)
2
(School of Computer Science, Shenyang Aerospace University, Shenyang 110136, China)
Abstract: Learned indexes are assisting or gradually replacing traditional index structures due to their low memory usage and high query
performance. However, the online retraining caused by data updates makes it unable to adapt to the scenario of frequent data updates. To
avoid index reconstruction due to frequent data updates without significantly increasing memory consumption, this study proposes an
adaptive update-distribution-aware learned index named DRAMA. It uses an LSM-Tree-like delayed learning method to actively learn the
characteristics of the data update distribution, approximate fitting techniques to quickly establish the update-distribution model, a model
merging strategy to replace the frequent retraining, and a hybrid compression technique to reduce the memory usage of model parameters
in the index. The index is constructed and validated on both real and synthetic datasets. The results show that, compared to traditional
indexes and state-of-the-art learned indexes, the proposed index can effectively reduce query delay in a data update environment without
additional memory consumption.
Key words: learned index; update-distribution; compression strategy; delayed learning; approximate fitting; model merging

大数据时代的今天, 数据呈爆炸性增长的趋势, 高效处理频繁更新的数据迫切又棘手. 特别是在目标跟踪服务、
移动导航、公共交通系统等对实时性要求较高的应用中显得尤为重要. 在高峰期的地铁进出站, 大量地铁卡数据
(如卡片编号、行程的起始站与终点站、卡内金额核验计算与更新等) 需要被实时更新到数据库, 而且这些数据的

* 基金项目: 国家自然科学基金 (U23B2019); 中央高校基本科研业务费专项资金 (N2216017)
收稿时间: 2023-09-03; 修改时间: 2023-12-05, 2024-02-11; 采用时间: 2024-05-11; jos 在线出版时间: 2024-07-03
CNKI 网络首发时间: 2024-07-11