{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T16:08:09Z","timestamp":1781194089549,"version":"3.54.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.14778\/3681954.3682010","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"3415-3427","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["LITS: An Optimized Learned Index for Strings"],"prefix":"10.14778","volume":"17","author":[{"given":"Yifan","family":"Yang","sequence":"first","affiliation":[{"name":"SKLP, ACS, Institute of Computing Technology, CAS, University of Chinese Academy of Sciences"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shimin","family":"Chen","sequence":"additional","affiliation":[{"name":"SKLP, ACS, Institute of Computing Technology, CAS, University of Chinese Academy of Sciences"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2017. reddit. https:\/\/www.kaggle.com\/datasets\/colinmorris\/reddit-usernames"},{"key":"e_1_2_1_2_1","unstructured":"2018. geoname. https:\/\/www.kaggle.com\/datasets\/geonames\/geonames-database"},{"key":"e_1_2_1_3_1","unstructured":"2023. address. https:\/\/v2.openaddresses.io\/batch-prod\/collection-us-west.zip"},{"key":"e_1_2_1_4_1","unstructured":"2023. dblp. https:\/\/dblp.org\/xml\/dblp.xml.gz"},{"key":"e_1_2_1_5_1","unstructured":"2023. imdb. https:\/\/datasets.imdbws.com\/name.basics.tsv.gz"},{"key":"e_1_2_1_6_1","unstructured":"2023. url. https:\/\/data.commoncrawl.org\/CC-MAIN-2023-14\/"},{"key":"e_1_2_1_7_1","unstructured":"2023. wiki. https:\/\/dumps.wikimedia.org\/enwiki\/"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00521-023-08841-1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254766"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196896"},{"key":"e_1_2_1_11_1","volume-title":"18th USENIX Conference on File and Storage Technologies, FAST 2020","author":"Cao Zhichao","year":"2020","unstructured":"Zhichao Cao, Siying Dong, Sagar Vemuri, and David H. C. Du. 2020. Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. In 18th USENIX Conference on File and Storage Technologies, FAST 2020, Santa Clara, CA, USA, February 24--27, 2020. USENIX Association, 209--223."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2023.3295434"},{"key":"e_1_2_1_15_1","volume-title":"2nd International Workshop on Applied AI for Database Systems and Applications, Held with VLDB 2020","author":"Hadian Ali","year":"2020","unstructured":"Ali Hadian and Thomas Heinis. 2020. MADEX: Learning-augmented Algorithmic Index Structures. In AIDB@VLDB 2020, 2nd International Workshop on Applied AI for Database Systems and Applications, Held with VLDB 2020, Monday, August 31, 2020, Online Event \/ Tokyo, Japan."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389752"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489512"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598593"},{"key":"e_1_2_1_22_1","volume-title":"Umar Farooq Minhas, and Tim Kraska","author":"Spector Benjamin","year":"2021","unstructured":"Benjamin Spector, Andreas Kipf, Kapil Vaidya, Chi Wang, Umar Farooq Minhas, and Tim Kraska. 2021. Bounding the Last Mile: Efficient Learned String Indexing. CoRR abs\/2111.14905 (2021). arXiv:2111.14905"},{"key":"e_1_2_1_23_1","volume-title":"PLEX: Towards Practical Learned Indexing. CoRR abs\/2108.05117","author":"Stoian Mihail","year":"2021","unstructured":"Mihail Stoian, Andreas Kipf, Ryan Marcus, and Tim Kraska. 2021. PLEX: Towards Practical Learned Indexing. CoRR abs\/2108.05117 (2021). arXiv:2108.05117"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588959"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409963.3410496"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551848"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457393"},{"key":"e_1_2_1_29_1","volume-title":"LITS: An Optimized Learned Index for Strings (An Extended Version). In Technical Report. arXiv:2407.11556","author":"Yang Yifan","year":"2024","unstructured":"Yifan Yang and Shimin Chen. 2024. LITS: An Optimized Learned Index for Strings (An Extended Version). In Technical Report. arXiv:2407.11556"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380583"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3682010","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:33:07Z","timestamp":1725474787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3682010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":30,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3682010"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3682010","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}