# RadixSpline: A Single-Pass Learned Index

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2020.

## Built on by (most cited first, 30 of 31)

- [CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm](https://mlsanity.com/paper/2103.00858/) (2021)
- [Bounding the Last Mile: Efficient Learned String Indexing](https://mlsanity.com/paper/2111.14905/) (2021)
- [WISK: A Workload-aware Learned Index for Spatial Keyword Queries](https://mlsanity.com/paper/2302.14287/) (2023)
- [Online List Labeling with Predictions](https://mlsanity.com/paper/2305.10536/) (2023)
- [Learned Sorted Table Search and Static Indexes in Small Model Space](https://mlsanity.com/paper/2107.09480/) (2021)
- [On the Choice of General Purpose Classifiers in Learned Bloom Filters: An Initial Analysis Within Basic Filters](https://mlsanity.com/paper/2112.06563/) (2021)
- [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)
- [Towards Practical Learned Indexing](https://mlsanity.com/paper/2108.05117/) (2021)
- [NFL: Robust Learned Index via Distribution Transformation](https://mlsanity.com/paper/2205.11807/) (2022)
- [LeCo: Lightweight Compression via Learning Serial Correlations](https://mlsanity.com/paper/2306.15374/) (2023)
- [A Reinforcement Learning Based R-Tree for Spatial Data Indexing in Dynamic Environments](https://mlsanity.com/paper/2103.04541/) (2021)
- [Micro-architectural Analysis of a Learned Index](https://mlsanity.com/paper/2109.08495/) (2021)
- [Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform](https://mlsanity.com/paper/2201.01554/) (2022)
- [A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach](https://mlsanity.com/paper/2502.05001/) (2025)
- [A Pluggable Learned Index Method via Sampling and Gap Insertion](https://mlsanity.com/paper/2101.00808/) (2021)
- [LSI: A Learned Secondary Index Structure](https://mlsanity.com/paper/2205.05769/) (2022)
- [Compressing (Multidimensional) Learned Bloom Filters](https://mlsanity.com/paper/2208.03029/) (2022)
- [UpLIF: An Updatable Self-Tuning Learned Index Framework](https://mlsanity.com/paper/2408.04113/) (2024)
- [Learned Compression of Nonlinear Time Series With Random Access](https://mlsanity.com/paper/2412.16266/) (2024)
- [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)
- [Testing the Robustness of Learned Index Structures](https://mlsanity.com/paper/2207.11575/) (2022)
- [A Critical Analysis of Classifier Selection in Learned Bloom Filters](https://mlsanity.com/paper/2211.15565/) (2022)
- [LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization](https://mlsanity.com/paper/2307.08637/) (2023)
- [From Specific to Generic Learned Sorted Set Dictionaries: A Theoretically Sound Paradigm Yelding Competitive Data Structural Boosters in Practice](https://mlsanity.com/paper/2309.00946/) (2023)
- [LearnedKV: Integrating LSM and Learned Index for Superior Performance on Storage](https://mlsanity.com/paper/2406.18892/) (2024)
- [Sig2Model: A Boosting-Driven Model for Updatable Learned Indexes](https://mlsanity.com/paper/2509.20781/) (2025)
- [Optimized Learned Count-Min Sketch](https://mlsanity.com/paper/2512.12252/) (2025)
- [Lower Bounds for the Algorithmic Complexity of Learned Indexes](https://mlsanity.com/paper/2601.06629/) (2026)

## Abstract (arXiv)

Recent research has shown that learned models can outperform state-of-the-art index structures in size and lookup performance. While this is a very promising result, existing learned structures are often cumbersome to implement and are slow to build. In fact, most approaches that we are aware of require multiple training passes over the data. We introduce RadixSpline (RS), a learned index that can be built in a single pass over the data and is competitive with state-of-the-art learned index models, like RMI, in size and lookup performance. We evaluate RS using the SOSD benchmark and show that it achieves competitive results on all datasets, despite the fact that it only has two parameters.