2022/05/11 by Andreas Kipf, Kipf, Andreas, Dominik Horn +7 · 2 voices · 1 citation
Computer Science · #Advanced Image and Video Retrieval Techniques #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Text and Document Classification Technologies #cs.DB #cs.LG
paper · pdf · doi:10.48550/arxiv.2205.05769
openalex publication_date 2022/05/11 · arxiv published 2022/05/11 · arxiv updated 2022/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Learned index structures have been shown to achieve favorable lookup performance and space consumption compared to their traditional counterparts such as B-trees. However, most learned index studies have focused on the primary indexing setting, where the base data is sorted. In this work, we investigate whether learned indexes sustain their advantage in the secondary indexing setting. We introduce Learned Secondary Index (LSI), a first attempt to use learned indexes for indexing unsorted data. LSI works by building a learned index over a permutation vector, which allows binary search to performed on the unsorted base data using random access. We additionally augment LSI with a fingerprint vector to accelerate equality lookups. We show that LSI achieves comparable lookup performance to state-of-the-art secondary indexes while being up to 6x more space efficient.