Height Optimized Tries

Binna R, Zangerle E, Pichl M, Specht G, Leis V (2022)

Publication Type: Journal article

Publication year: 2022

Journal

Acm Transactions on Database Systems Association for Computing Machinery (ACM)

Book Volume: 47

Journal Issue: 1

DOI: 10.1145/3506692

Abstract

We present the Height Optimized Trie (HOT), a fast and space-efficient 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. For a fixed maximum node fanout, the overall tree height is minimal and its structure is deterministically defined. Multiple carefully engineered node implementations using SIMD instructions or lightweight compression schemes provide compactness and fast search and optimize HOT structures for different usage scenarios. Our experiments, 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.

Authors with CRIS profile

Viktor Leis Chair for Computer Science 6 (Data Management)

Involved external institutions

Leopold-Franzens-Universität Innsbruck / University of Innsbruck AT Austria (AT)

How to cite

APA:

Binna, R., Zangerle, E., Pichl, M., Specht, G., & Leis, V. (2022). Height Optimized Tries. Acm Transactions on Database Systems, 47(1). https://dx.doi.org/10.1145/3506692

MLA:

Binna, Robert, et al. "Height Optimized Tries." Acm Transactions on Database Systems 47.1 (2022).

BibTeX: Download