# A Survey of Learned Indexes for the Multi-dimensional Space

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 232 references that are in the map.
- First posted on arXiv 11 Mar 2024.

## Builds on (most cited first, 30 of 52)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Neo: A Learned Query Optimizer](https://mlsanity.com/paper/1904.03711/) (2019)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [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)
- [FITing-Tree: A Data-aware Index Structure](https://mlsanity.com/paper/1801.10207/) (2018)
- [Database Meets Deep Learning: Challenges and Opportunities](https://mlsanity.com/paper/1906.08986/) (2019)
- [Learning Multi-dimensional Indexes](https://mlsanity.com/paper/1912.01668/) (2019)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads](https://mlsanity.com/paper/2006.13282/) (2020)
- [SOSD: A Benchmark for Learned Indexes](https://mlsanity.com/paper/1911.13014/) (2019)
- [Qd-tree: Learning Data Layouts for Big Data Analytics](https://mlsanity.com/paper/2004.10898/) (2020)
- [Machine Unlearning in Learned Databases: An Experimental Analysis](https://mlsanity.com/paper/2311.17276/) (2023)
- [The PGM-index: a multicriteria, compressed and learned approach to data indexing](https://mlsanity.com/paper/1910.06169/) (2019)
- [Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier](https://mlsanity.com/paper/1910.09131/) (2019)
- [Updatable Learned Index with Precise Positions](https://mlsanity.com/paper/2104.05520/) (2021)
- [Meta-Learning Neural Bloom Filters](https://mlsanity.com/paper/1906.04304/) (2019)
- [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)
- [CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm](https://mlsanity.com/paper/2103.00858/) (2021)
- [APEX: A High-Performance Learned Index on Persistent Memory](https://mlsanity.com/paper/2105.00683/) (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)
- [Updatable Learned Indexes Meet Disk-Resident DBMS -- From Evaluations to Design Choices](https://mlsanity.com/paper/2305.01237/) (2023)
- [Fast Partitioned Learned Bloom Filter](https://mlsanity.com/paper/2306.02846/) (2023)
- [On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing](https://mlsanity.com/paper/2306.10651/) (2023)
- [The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures](https://mlsanity.com/paper/2008.00297/) (2020)

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

- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions](https://mlsanity.com/paper/2603.00537/) (2026)
- [M-CTX: Exact and Scalable Spatial Context Retrieval for Trajectory Analytics](https://mlsanity.com/paper/2606.15244/) (2026)
- [Poisoning Attacks on the PGM-index](https://mlsanity.com/paper/2609.02328/) (2026)

## Abstract (arXiv)

A recent research trend involves treating database index structures as Machine Learning (ML) models. In this domain, single or multiple ML models are trained to learn the mapping from keys to positions inside a data set. This class of indexes is known as "Learned Indexes." Learned indexes have demonstrated improved search performance and reduced space requirements for one-dimensional data. The concept of one-dimensional learned indexes has naturally been extended to multi-dimensional (e.g., spatial) data, leading to the development of "Learned Multi-dimensional Indexes". This survey focuses on learned multi-dimensional index structures. Specifically, it reviews the current state of this research area, explains the core concepts behind each proposed method, and classifies these methods based on several well-defined criteria. We present a taxonomy that classifies and categorizes each learned multi-dimensional index, and survey the existing literature on learned multi-dimensional indexes according to this taxonomy. Additionally, we present a timeline to illustrate the evolution of research on learned indexes. Finally, we highlight several open challenges and future research directions in this emerging and highly active field.