# The PGM-index: a multicriteria, compressed and learned approach to data indexing

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

## Key facts

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

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

- [CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm](https://mlsanity.com/paper/2103.00858/) (2021)
- [WISK: A Workload-aware Learned Index for Spatial Keyword Queries](https://mlsanity.com/paper/2302.14287/) (2023)
- [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)
- [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)
- [Towards Effective Next POI Prediction: Spatial and Semantic Augmentation with Remote Sensing Data](https://mlsanity.com/paper/2404.04271/) (2024)
- [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)
- [LSI: A Learned Secondary Index Structure](https://mlsanity.com/paper/2205.05769/) (2022)
- [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)
- [LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization](https://mlsanity.com/paper/2307.08637/) (2023)
- [LearnedKV: Integrating LSM and Learned Index for Superior Performance on Storage](https://mlsanity.com/paper/2406.18892/) (2024)
- [Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2506.20139/) (2025)
- [Learned Static Function Data Structures](https://mlsanity.com/paper/2510.27588/) (2025)

## Abstract (arXiv)

The recent introduction of learned indexes has shaken the foundations of the decades-old field of indexing data structures. Combining, or even replacing, classic design elements such as B-tree nodes with machine learning models has proven to give outstanding improvements in the space footprint and time efficiency of data systems. However, these novel approaches are based on heuristics, thus they lack any guarantees both in their time and space requirements. We propose the Piecewise Geometric Model index (shortly, PGM-index), which achieves guaranteed I/O-optimality in query operations, learns an optimal number of linear models, and its peculiar recursive construction makes it a purely learned data structure, rather than a hybrid of traditional and learned indexes (such as RMI and FITing-tree). We show that the PGM-index improves the space of the FITing-tree by 63.3% and of the B-tree by more than four orders of magnitude, while achieving their same or even better query time efficiency. We complement this result by proposing three variants of the PGM-index. First, we design a compressed PGM-index that further reduces its space footprint by exploiting the repetitiveness at the level of the learned linear models it is composed of. Second, we design a PGM-index that adapts itself to the distribution of the queries, thus resulting in the first known distribution-aware learned index to date. Finally, given its flexibility in the offered space-time trade-offs, we propose the multicriteria PGM-index that efficiently auto-tune itself in a few seconds over hundreds of millions of keys to the possibly evolving space-time constraints imposed by the application of use. We remark to the reader that this paper is an extended and improved version of our previous paper titled "Superseding traditional indexes by orchestrating learning and geometry" (arXiv:1903.00507).