High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff
Proceedings of the ACM on Management of Data · 04.12.2025 · 3 (6) · 1-26
DOI: 10.1145/3769800 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 05.12.2025. Verfasst von Hui Wang und 5 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 53 Literaturangaben. Gefördert von: the National Key Research and Development Program of China, the National Natural Science Foundation of China, National Natural Science Foundation of China.
Abstract (Originalsprache)
The first generation of learned indexes inherently achieved lower space overhead than traditional index structures, establishing this advantage as one of the pivotal research directions in index optimization. However, in their pursuit of peak performance, designers often significantly increase space overhead, which becomes infeasible in scenarios with limited storage space. Furthermore, the design of current learned indexes optimized for time-space tradeoff is flawed, as they collapse catastrophically under prevalent dense or duplicate insertion workloads. To address these challenges, we first quantitatively analyze the time-space correlation characteristics of learned indexes from a theoretical perspective and identify the core influencing factors. Based on this, time-space cost minimization function models are established and an updatable learned index framework, LIFT, is constructed. Furthermore, LIFT incorporates specifically designed structural adjustment mechanisms to effectively counter existing poisoning attacks, significantly enhancing index robustness without increasing time-space cost. Evaluation results demonstrate that LIFT consistently achieves the optimal time-space tradeoff across various workloads and datasets, outperforming all other state-of-the-art indexes.
Förderung
- the National Key Research and Development Program of China
- the National Natural Science Foundation of China
- National Natural Science Foundation of China
- the Postdoctoral Fellowship Program of CPSF
Zitieren
APA
Wang, H., Wang, X., Ge, J., Chai, Y., Liang, L., & Yi, P. (2025). High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff. Proceedings of the ACM on Management of Data, 3(6), 1-26. https://doi.org/10.1145/3769800
Vancouver
Wang H, Wang X, Ge J, Chai Y, Liang L, Yi P. High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff. Proceedings of the ACM on Management of Data. 2025;3(6):1-26. doi:10.1145/3769800
BibTeX
@article{Wang2025,
author = {Wang, Hui and Wang, Xin and Ge, Jiake and Chai, Yunpeng and Liang, Lei and Yi, Peng},
title = {High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff},
journal = {Proceedings of the ACM on Management of Data},
year = {2025},
volume = {3},
number = {6},
pages = {1--26},
doi = {10.1145/3769800}
}
EUVIMED