mlsanityData to 7 Oct 2026

A Survey of Learned Indexes for the Multi-dimensional Space

arXiv 2403.06456 ↗First posted 11 Mar 2024cs.DB cs.LGcited by 4

Not on the map. Why?

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.

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

Builds on

52 of 232 references.

References · 52

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,016
  3. 2017The Case for Learned Index Structurescited by 188
  4. 2019Neo: A Learned Query Optimizercited by 80
  5. 2019A Model for Learned Bloom Filters, and Optimizing by Sandwichingcited by 64
  6. 2019ALEX: An Updatable Adaptive Learned Indexcited by 43
  7. 2020RadixSpline: A Single-Pass Learned Indexcited by 31
  8. 2018FITing-Tree: A Data-aware Index Structurecited by 30
  9. 2019Database Meets Deep Learning: Challenges and Opportunitiescited by 30
  10. 2019Learning Multi-dimensional Indexescited by 30
  11. 2020Benchmarking Learned Indexescited by 27
  12. 2020Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloadscited by 25
38 more
  1. 2019SOSD: A Benchmark for Learned Indexescited by 21
  2. 2020Qd-tree: Learning Data Layouts for Big Data Analyticscited by 18
  3. 2019The PGM-index: a multicriteria, compressed and learned approach to data indexingcited by 17
  4. 2023Machine Unlearning in Learned Databases: An Experimental Analysiscited by 17
  5. 2019Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifiercited by 15
  6. 2021Updatable Learned Index with Precise Positionscited by 13
  7. 2019Meta-Learning Neural Bloom Filterscited by 10
  8. 2020The Case for Learned Spatial Indexescited by 9
  9. 2020Learned Indexes for a Google-scale Disk-based Databasecited by 9
  10. 2021A Critical Analysis of Recursive Model Indexescited by 9
  11. 2021CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithmcited by 8
  12. 2021APEX: A High-Performance Learned Index on Persistent Memorycited by 6
  13. 2021Bounding the Last Mile: Efficient Learned String Indexingcited by 6
  14. 2023WISK: A Workload-aware Learned Index for Spatial Keyword Queriescited by 6
  15. 2023Updatable Learned Indexes Meet Disk-Resident DBMS -- From Evaluations to Design Choicescited by 6
  16. 2023Fast Partitioned Learned Bloom Filtercited by 6
  17. 2023On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexingcited by 6
  18. 2020The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structurescited by 5
  19. 2021Shift-Table: A Low-latency Learned Index for Range Queries using Model Correctioncited by 5
  20. 2022A Learned Index for Exact Similarity Search in Metric Spacescited by 4
  21. 2018LSM-based Storage Techniques: A Surveycited by 3
  22. 2019Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations (Extended Version)cited by 3
  23. 2022On the Suitability of Neural Networks as Building Blocks for The Design of Efficient Learned Indexescited by 3
  24. 2022NFL: Robust Learned Index via Distribution Transformationcited by 3
  25. 2023LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curvescited by 3
  26. 2023AirIndex: Versatile Index Tuning Through Data and Storagecited by 3
  27. 2023LeCo: Lightweight Compression via Learning Serial Correlationscited by 3
  28. 2023SALI: A Scalable Adaptive Learned Index Framework based on Probability Modelscited by 3
  29. 2019Learned Indexes for Dynamic Workloadscited by 2
  30. 2019A Scalable Learned Index Scheme in Storage Systemscited by 2
  31. 2020Hands-off Model Integration in Spatial Index Structurescited by 2
  32. 2020The Case for Distance-Bounded Spatial Approximationscited by 2
  33. 2021Micro-architectural Analysis of a Learned Indexcited by 2
  34. 2018The Potential of Learned Index Structures for Index Compressioncited by 1
  35. 2020PolyFit: Polynomial-based Indexing Approach for Fast Approximate Range Aggregate Queriescited by 1
  36. 2021When Are Learned Models Better Than Hash Functions?cited by 1
  37. 2022LSI: A Learned Secondary Index Structurecited by 1
  38. 2022The "AI+R"-tree: An Instance-optimized R-treecited by 1

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 0; 2026: 3.

4 papers.

  1. 2024Incremental IVF Index Maintenance for Streaming Vector Searchcited by 7
  2. 2026Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functionscited by 1
  3. 2026M-CTX: Exact and Scalable Spatial Context Retrieval for Trajectory Analyticscited by 0
  4. 2026Poisoning Attacks on the PGM-indexcited by 0