# Bounding the Last Mile: Efficient Learned String Indexing

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 18 references that are in the map.
- First posted on arXiv 29 Nov 2021.

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

- [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)
- [Order-Preserving Key Compression for In-Memory Search Trees](https://mlsanity.com/paper/2003.02391/) (2020)

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

- [A Survey of Learned Indexes for the Multi-dimensional Space](https://mlsanity.com/paper/2403.06456/) (2024)
- [Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training](https://mlsanity.com/paper/2403.11472/) (2024)
- [LSI: A Learned Secondary Index Structure](https://mlsanity.com/paper/2205.05769/) (2022)
- [DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees](https://mlsanity.com/paper/2502.05369/) (2025)
- [Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions](https://mlsanity.com/paper/2603.00537/) (2026)
- [LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization](https://mlsanity.com/paper/2307.08637/) (2023)

## Abstract (arXiv)

We introduce the RadixStringSpline (RSS) learned index structure for efficiently indexing strings. RSS is a tree of radix splines each indexing a fixed number of bytes. RSS approaches or exceeds the performance of traditional string indexes while using 7-70× less memory. RSS achieves this by using the minimal string prefix to sufficiently distinguish the data unlike most learned approaches which index the entire string. Additionally, the bounded-error nature of RSS accelerates the last mile search and also enables a memory-efficient hash-table lookup accelerator. We benchmark RSS on several real-world string datasets against ART and HOT. Our experiments suggest this line of research may be promising for future memory-intensive database applications.