EUVIMEDEUVIMED entdecken
Crossref

High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff

Hui Wang, Xin Wang, Jiake Ge, Yunpeng Chai, Lei Liang, Peng Yi

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →