LIVAK: A High-Performance In-Memory Learned Index for Variable-Length Keys
Authors: 
Zhaole Chu, Zhou Zhang, Peiquan Jin, Xiaoliang Wang, Yongping Luo, Xujian ZhaoAuthors Info & Claims
Article No.: 174, Pages 1 - 6
Abstract
In-memory learned index has been an efficient approach supporting in-memory fast data access. However, existing learned indexes are inefficient in supporting variable-length keys. To address this issue, we propose a new in-memory learned index called LIVAK that adopts a hybrid structure involving trie, learned index, and B+-tree. Each node indexes an 8-byte slice of keys, and we use learned indexes for large nodes but B+-trees for small nodes. Also, LIVAK presents a character re-encoding mechanism to avoid performance degradation. We compare LIVAK with B+-tree, Masstree, and SIndex on various datasets and workloads, and the results suggest the efficiency of LIVAK.
References
[1]
Robert Binna, Eva Zangerle, and et al. 2018. HOT: A height optimized trie index for main-memory database systems. In SIGMOD. 521--534.
[2]
Philip Bohannon, Peter McIlroy, and et al. 2001. Main-memory index structures with fixed-size partial keys. In SIGMOD. 163--174.
[3]
Jialin Ding, Umar Farooq Minhas, and et al. 2020. ALEX: An updatable adaptive learned index. In SIGMOD. 969--984.
[4]
Paolo Ferragina and Giorgio Vinciguerra. 2020. The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds. Proc. VLDB Endow. 13, 8 (2020), 1162--1175.
[5]
Tim Kraska, Alex Beutel, and et al. 2018. The case for learned index structures. In SIGMOD. 489--504.
[6]
Viktor Leis, Alfons Kemper, and et al. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. In ICDE. 38--49.
[7]
Yandong Mao, Eddie Kohler, and et al. 2012. Cache craftiness for fast multicore key-value storage. In EuroSys. 183--196.
[8]
Ryan Marcus, Andreas Kipf, and et al. 2020. Benchmarking learned indexes. Proc. VLDB Endow. 14, 1 (2020), 1--13.
[9]
Markus Mäsker, Tim Süß, and et al. 2019. Hyperion: Building the largest inmemory search tree. In SIGMOD. 1207--1222.
[10]
Ajit Mathew and Changwoo Min. 2020. HydraList: A scalable in-memory index using asynchronous updates and partial replication. Proc. VLDB Endow. 13, 9 (2020), 1332--1345.
[11]
Benjamin Spector, Andreas Kipf, and et al. 2021. Bounding the last mile: Efficient learned string indexing. In AIDB@VLDB.
[12]
Zhaoyan Sun, Xuanhe Zhou, and et al. 2023. Learned Index: A Comprehensive Experimental Evaluation. Proc. VLDB Endow. 16, 8 (2023), 1992--2004.
[13]
Youyun Wang, Chuzhe Tang, and et al. 2020. SIndex: A scalable learned index for string keys. In APSys. 17--24.
[14]
Xingbo Wu, Fan Ni, and et al. 2019. Wormhole: A fast ordered index for inmemory data management. In EuroSys. 18:1--18:16.
[15]
Adar Zeitak and Adam Morrison. 2021. Cuckoo trie: Exploiting memory-level parallelism for efficient DRAM indexing. In SOSP. 147--162.
[16]
Zhou Zhang, Zhaole Chu, and et al. 2022. PLIN: A Persistent Learned Index for Non-Volatile Memory with High Performance and Instant Recovery. Proc. VLDB Endow. 16, 2 (2022), 243--255.
[17]
Zhou Zhang, Peiquan Jin, and et al. 2021. COLIN: A cache-conscious dynamic learned index with high read/write performance. J. Comput. Sci. Technol. 36, 4 (2021), 721--740.
Index Terms
- LIVAK: A High-Performance In-Memory Learned Index for Variable-Length Keys
Recommendations
Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction
SIGMODLearned 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. ...
The Case for Learned Index Structures
SIGMOD '18: Proceedings of the 2018 International Conference on Management of DataIndexes are models: a \btree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate ...
DiffLex: A High-Performance, Memory-Efficient and NUMA-Aware Learned Index using Differentiated Management
ICPP '23: Proceedings of the 52nd International Conference on Parallel ProcessingLearned indexes that utilize machine learning models can offer significant performance advantages over traditional indexes. However, existing learned indexes suffer from space-performance tradeoffs and they cannot scale well in multiple NUMA-nodes ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 November 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Science Foundation of China
- CCF-Huawei Populus Grove Challenge Fund
Conference
DAC '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,770 of 5,499 submissions, 32%
Upcoming Conference
DAC '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 55Total Downloads
- Downloads (Last 12 months)55
- Downloads (Last 6 weeks)55
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in