HOT: A height optimized trie index for main-memory database systems
Binna R, Zangerle E, Pichl M, Specht G, Leis V (2018)
Publication Type: Conference contribution
Publication year: 2018
Publisher: Association for Computing Machinery
Pages Range: 521-534
Conference Proceedings Title: Proceedings of the ACM SIGMOD International Conference on Management of Data
Event location: Houston, TX
ISBN: 9781450317436
Abstract
We present the Height Optimized Trie (HOT), a fast and spaceefficient in-memory index structure. The core algorithmic idea of HOT is to dynamically vary the number of bits considered at each node, which enables a consistently high fanout and thereby good cache efficiency. The layout of each node is carefully engineered for compactness and fast search using SIMD instructions. Our experimental results, which use a wide variety of workloads and data sets, show that HOT outperforms other state-of-the-art index structures for string keys both in terms of search performance and memory footprint, while being competitive for integer keys. We believe that these properties make HOT highly useful as a general-purpose index structure for main-memory databases.
Authors with CRIS profile
Involved external institutions
Leopold-Franzens-Universität Innsbruck / University of Innsbruck
Austria (AT)
Technische Universität München (TUM)
Germany (DE)
Austria (AT)
Technische Universität München (TUM)
Germany (DE)
How to cite
APA:
Binna, R., Zangerle, E., Pichl, M., Specht, G., & Leis, V. (2018). HOT: A height optimized trie index for main-memory database systems. In Gautam Das, Christopher Jermaine, Ahmed Eldawy, Philip Bernstein (Eds.), Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 521-534). Houston, TX, US: Association for Computing Machinery.
MLA:
Binna, Robert, et al. "HOT: A height optimized trie index for main-memory database systems." Proceedings of the 44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018, Houston, TX Ed. Gautam Das, Christopher Jermaine, Ahmed Eldawy, Philip Bernstein, Association for Computing Machinery, 2018. 521-534.
BibTeX: Download