Hyper: Achieving High-Performance and Memory-Efficient Learned Index Via Hybrid Construction
- Publikationstyp:
- Konferenzbeitrag
- Metadaten:
-
- Abstract
- <jats:p>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.</jats:p> <jats:p>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.</jats:p>
- Autoren
- Shunkang Zhang
- Ji Qi
- Xin Yao
- André Brinkmann
- DOI
- 10.1145/3654948
- eISSN
- 2836-6573
- Ausgabe der Veröffentlichung
- 3
- Zeitschrift
- Proceedings of the ACM on Management of Data
- Online publication date
- 2024
- Paginierung
- 1 - 26
- Datum der Veröffentlichung
- 2024
- Status
- Published
- Herausgeber
- Association for Computing Machinery (ACM)
- Herausgeber URL
- http://dx.doi.org/10.1145/3654948
- Datum der Datenerfassung
- 2024
- Titel
- Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction
- Ausgabe der Zeitschrift
- 2
Datenquelle: Crossref
- Andere Metadatenquellen:
-
- Autoren
- Shunkang Zhang
- Ji Qi
- Xin Yao
- André Brinkmann
- Conference finish date
- 2024
- Zeitschrift
- To appear in International Conference on Management of Data (SIGMOD), Santiago, Chile, June 09 - 15
- Conference place
- Santiago, Chile
- Name of conference
- International Conference on Management of Data (SIGMOD)
- Datum der Veröffentlichung
- 2024
- Datum der Datenerfassung
- 2024
- Conference start date
- 2024
- Titel
- Hyper: Achieving High-Performance and Memory-Efficient Learned Index Via Hybrid Construction
Datenquelle: Manual
- Beziehungen:
-