# Learning Multi-dimensional Indexes

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2019.

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

- [A Unified Transferable Model for ML-Enhanced DBMS](https://mlsanity.com/paper/2105.02418/) (2021)
- [CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm](https://mlsanity.com/paper/2103.00858/) (2021)
- [Detect, Distill and Update: Learned DB Systems Facing Out of Distribution Data](https://mlsanity.com/paper/2210.05508/) (2022)
- [WISK: A Workload-aware Learned Index for Spatial Keyword Queries](https://mlsanity.com/paper/2302.14287/) (2023)
- [A Learned Index for Exact Similarity Search in Metric Spaces](https://mlsanity.com/paper/2204.10028/) (2022)
- [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)
- [A Learning-Based Caching Mechanism for Edge Content Delivery](https://mlsanity.com/paper/2402.02795/) (2024)
- [Towards Effective Next POI Prediction: Spatial and Semantic Augmentation with Remote Sensing Data](https://mlsanity.com/paper/2404.04271/) (2024)
- [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)
- [Learned-Database Systems Security](https://mlsanity.com/paper/2212.10318/) (2022)
- [A Pluggable Learned Index Method via Sampling and Gap Insertion](https://mlsanity.com/paper/2101.00808/) (2021)
- [Unsupervised Space Partitioning for Nearest Neighbor Search](https://mlsanity.com/paper/2206.08091/) (2022)
- [The "AI+R"-tree: An Instance-optimized R-tree](https://mlsanity.com/paper/2207.00550/) (2022)
- [Dynamic Data Layout Optimization with Worst-case Guarantees](https://mlsanity.com/paper/2405.04984/) (2024)
- [LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table](https://mlsanity.com/paper/2506.04790/) (2025)
- [Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions](https://mlsanity.com/paper/2603.00537/) (2026)
- [Baihe: SysML Framework for AI-driven Databases](https://mlsanity.com/paper/2112.14460/) (2021)
- [Learning-Based Data Storage [Vision] (Technical Report)](https://mlsanity.com/paper/2206.05778/) (2022)
- [Testing the Robustness of Learned Index Structures](https://mlsanity.com/paper/2207.11575/) (2022)
- [Learned Indexing in Proteins: Extended Work on Substituting Complex Distance Calculations with Embedding and Clustering Techniques](https://mlsanity.com/paper/2208.08910/) (2022)
- [Learned k-NN Distance Estimation](https://mlsanity.com/paper/2208.14210/) (2022)
- [Learned spatial data partitioning](https://mlsanity.com/paper/2306.04846/) (2023)
- [Sig2Model: A Boosting-Driven Model for Updatable Learned Indexes](https://mlsanity.com/paper/2509.20781/) (2025)
- [Privacy-Preserving Learning-Augmented Data Structures](https://mlsanity.com/paper/2510.00165/) (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)
- [M-CTX: Exact and Scalable Spatial Context Retrieval for Trajectory Analytics](https://mlsanity.com/paper/2606.15244/) (2026)

## Abstract (arXiv)

Scanning and filtering over multi-dimensional tables are key operations in modern analytical database engines. To optimize the performance of these operations, databases often create clustered indexes over a single dimension or multi-dimensional indexes such as R-trees, or use complex sort orders (e.g., Z-ordering). However, these schemes are often hard to tune and their performance is inconsistent across different datasets and queries. In this paper, we introduce Flood, a multi-dimensional in-memory index that automatically adapts itself to a particular dataset and workload by jointly optimizing the index structure and data storage. Flood achieves up to three orders of magnitude faster performance for range scans with predicates than state-of-the-art multi-dimensional indexes or sort orders on real-world datasets and workloads. Our work serves as a building block towards an end-to-end learned database system.