EUVIMEDEUVIMED entdecken
Crossref

Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction

Shunkang Zhang, Ji Qi, Xin Yao, André Brinkmann

Proceedings of the ACM on Management of Data · 29.05.2024 · 2 (3) · 1-26

DOI: 10.1145/3654948 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2024. Verfasst von Shunkang Zhang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 50 Literaturangaben. Gefördert von: National Key R&D Program of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Learned indexes use machine learning techniques to improve index construction. However, they often face a fundamental trade-off between performance and memory consumption, especially in dynamic environments with frequent insert and delete operations. This trade-off stems from the construction approaches used in learned indexes: The top-down approach increases performance at the cost of significant memory overhead, while the bottom-up approach focuses on memory efficiency but introduces performance issues due to prediction errors. % A unified solution that simultaneously optimizes performance and memory consumption in dynamic data management scenarios is therefore highly desirable. We propose Hyper, a highly efficient learned index with a novel two-phase hybrid construction approach. Our approach combines bottom-up construction for leaf nodes with top-down construction for inner nodes to achieve an optimal balance between performance and memory consumption. Hyper effectively handles concurrent writes and structure adjustments without sacrificing query performance. We evaluated Hyper on both simple and complex real-world datasets and compared it to seven state-of-the-art learned indexes and several traditional data structures for dynamic workloads. The evaluation results show that Hyper achieves a remarkable performance boost of up to 3.75× with significantly reduced index memory consumption of up to 1610× in the single-thread evaluation. In high concurrency scenarios, Hyper even achieves improvements up to 5.73×, 3.72×, and 3.99× in read-only, read-write, and write-only workloads.

Förderung

  • National Key R&D Program of China

Zitieren

APA

Zhang, S., Qi, J., Yao, X., & Brinkmann, A. (2024). Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction. Proceedings of the ACM on Management of Data, 2(3), 1-26. https://doi.org/10.1145/3654948

Vancouver

Zhang S, Qi J, Yao X, Brinkmann A. Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction. Proceedings of the ACM on Management of Data. 2024;2(3):1-26. doi:10.1145/3654948

BibTeX
@article{Zhang2024,
  author = {Zhang, Shunkang and Qi, Ji and Yao, Xin and Brinkmann, André},
  title = {Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2024},
  volume = {2},
  number = {3},
  pages = {1--26},
  doi = {10.1145/3654948}
}
Kostenlos starten →