EUVIMEDEUVIMED entdecken
Crossref

LITS: An Optimized Learned Index for Strings

Yifan Yang, Shimin Chen

Proceedings of the VLDB Endowment · 2024-07 · 17 (11) · 3415-3427

DOI: 10.14778/3681954.3682010 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 30.08.2024. Verfasst von Yifan Yang und 1 weiteren Autor:innen. Die Arbeit wurde bisher 21-mal zitiert (Crossref) und nennt 30 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Index is an important component in database systems. Learned indexes 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 indexes for strings fail to outperform traditional string indexes, 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 (Learned Index with Hash-enhanced Prefix Table and Subtries). We propose an optimized learned model, combining a global Hash-enhanced Prefix Table (HPT) and a per-node local linear model to better distinguish string keys. Moreover, LITS exploits compact leaf nodes and hybrid structures with a PMSS model for efficient point and range operations. Our experimental results using eleven string data sets show that LITS achieves up to 2.43x and 2.27x improvement over HOT and ART for point operations, and attains comparable scan performance.

Zitieren

APA

Yang, Y., & Chen, S. (2024). LITS: An Optimized Learned Index for Strings. Proceedings of the VLDB Endowment, 17(11), 3415-3427. https://doi.org/10.14778/3681954.3682010

Vancouver

Yang Y, Chen S. LITS: An Optimized Learned Index for Strings. Proceedings of the VLDB Endowment. 2024;17(11):3415-3427. doi:10.14778/3681954.3682010

BibTeX
@article{Yang2024,
  author = {Yang, Yifan and Chen, Shimin},
  title = {LITS: An Optimized Learned Index for Strings},
  journal = {Proceedings of the VLDB Endowment},
  year = {2024},
  volume = {17},
  number = {11},
  pages = {3415--3427},
  doi = {10.14778/3681954.3682010}
}
Kostenlos starten →