# LSI: A Learned Secondary Index Structure

arXiv: https://arxiv.org/abs/2205.05769 · HTML: https://mlsanity.com/paper/2205.05769/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 28 references that are in the map.
- First posted on arXiv 11 May 2022.

## Builds on (most cited first, 15 of 15)

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [RadixSpline: A Single-Pass Learned Index](https://mlsanity.com/paper/2004.14541/) (2020)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [SOSD: A Benchmark for Learned Indexes](https://mlsanity.com/paper/1911.13014/) (2019)
- [The PGM-index: a multicriteria, compressed and learned approach to data indexing](https://mlsanity.com/paper/1910.06169/) (2019)
- [Updatable Learned Index with Precise Positions](https://mlsanity.com/paper/2104.05520/) (2021)
- [The Case for Learned Spatial Indexes](https://mlsanity.com/paper/2008.10349/) (2020)
- [Learned Indexes for a Google-scale Disk-based Database](https://mlsanity.com/paper/2012.12501/) (2020)
- [A Critical Analysis of Recursive Model Indexes](https://mlsanity.com/paper/2106.16166/) (2021)
- [Bounding the Last Mile: Efficient Learned String Indexing](https://mlsanity.com/paper/2111.14905/) (2021)
- [Shift-Table: A Low-latency Learned Index for Range Queries using Model Correction](https://mlsanity.com/paper/2101.10457/) (2021)
- [Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations (Extended Version)](https://mlsanity.com/paper/1903.11203/) (2019)
- [The Case for Distance-Bounded Spatial Approximations](https://mlsanity.com/paper/2010.12548/) (2020)
- [Cortex: Harnessing Correlations to Boost Query Performance](https://mlsanity.com/paper/2012.06683/) (2020)

## Built on by (most cited first, 1 of 1)

- [A Survey of Learned Indexes for the Multi-dimensional Space](https://mlsanity.com/paper/2403.06456/) (2024)

## Abstract (arXiv)

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.