Learned Indices for String Keys with Optimized Performance and O(N) Space Cost
ACM Transactions on Database Systems · 17.08.2026
DOI: 10.1145/3841175 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 17.08.2026. Verfasst von Yifan Yang und 1 weiteren Autor:innen. Die Arbeit nennt 47 Literaturangaben.
Abstract (Originalsprache)
Index is an important component in database systems. Learned indices have been shown to outperform traditional tree-based index structures for fixed-sized integer or floating point keys. However, the application of the learned solution to variable-length string keys is under-researched. Our experiments show that existing learned indices for strings fail to outperform traditional string indices, such as HOT and ART. String keys are long and variable sized, and often contain skewed prefixes, which make the last-mile search expensive, and adversely impact the capability of learned models to capture the skewed distribution of string keys. In this paper, we propose a novel learned index for string keys, LITS ( L earned I ndex with Hash-enhanced Prefix T able and S ub-tries). We design an optimized learned model that combines a global Hash-enhanced Prefix Table (HPT) with per-node local linear models to better distinguish string keys. Moreover, we exploit two techniques, i.e., dynamic scale factor and cell-based root, to improve the space efficiency. We prove that the resulting design is guaranteed to have O ( N ) space cost. Furthermore, we leverage compact leaf nodes and hybrid structures with a PMSS model to support efficient point and range queries. Our experimental results using eleven string data sets show that LITS achieves up to 2.19 × and 1.85 × improvement over HOT and ART for point operations with comparable scan performance and space cost.
Zitieren
APA
Yang, Y., & Chen, S. (2026). Learned Indices for String Keys with Optimized Performance and O(N) Space Cost. ACM Transactions on Database Systems. https://doi.org/10.1145/3841175
Vancouver
Yang Y, Chen S. Learned Indices for String Keys with Optimized Performance and O(N) Space Cost. ACM Transactions on Database Systems. 2026. doi:10.1145/3841175
BibTeX
@article{Yang2026,
author = {Yang, Yifan and Chen, Shimin},
title = {Learned Indices for String Keys with Optimized Performance and O(N) Space Cost},
journal = {ACM Transactions on Database Systems},
year = {2026},
doi = {10.1145/3841175}
}
EUVIMED