Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction
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.
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}
}
EUVIMED