EUVIMEDEUVIMED entdecken
Crossref

Learned Indices for String Keys with Optimized Performance and O(N) Space Cost

Yifan Yang, Shimin Chen

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →