Database Paper Browser

Back to papers

The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds

Summary: PGM-index is a dynamic, compressed learned index with provable bounds for predecessor, range queries and updates. Distribution-aware, repetition-based compression and multicriteria auto-tuning enable large space reductions with competitive times vs B+-trees. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
12035
Venue
VLDB
Year
2020
Pagerank
0.00015964123
Overall Rank
844 | 94.14%
DOI
10.14778/3389133.3389135

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 70 citing papers.

Rank Citing Paper Year Venue Pagerank
1,438 Benchmarking Learned Indexes 2021 VLDB 0.00011965956
1,887 Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads 2021 VLDB 0.00010201938
2,550 Updatable Learned Index with Precise Positions 2021 VLDB 8.5569576e-05
2,676 Effectively Learning Spatial Indices 2020 VLDB 8.326321e-05
3,136 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 7.4926368e-05
3,419 LeCo: Lightweight Compression via Learning Serial Correlations 2024 SIGMOD 7.1127752e-05
3,945 APEX: A High-Performance Learned Index on Persistent Memory 2022 VLDB 6.605467e-05
4,056 Are Updatable Learned Indexes Ready? 2022 VLDB 6.4905689e-05
4,404 TreeLine: An Update-In-Place Key-Value Store for Modern Storage 2023 VLDB 6.2052645e-05
4,592 Auto-WLM: Machine Learning Enhanced Workload Management in Amazon Redshift 2023 SIGMOD 6.056004e-05
4,830 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 5.8884997e-05
5,072 Learned Index: A Comprehensive Experimental Evaluation 2023 VLDB 5.7121108e-05
5,154 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 5.6548237e-05
5,310 The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures 2022 SIGMOD 5.5713508e-05
5,323 Can Learned Models Replace Hash Functions? 2023 VLDB 5.5671086e-05
5,327 DILI: A Distribution-Driven Learned Index 2023 VLDB 5.5660777e-05
5,463 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 5.4920768e-05
5,601 PLIN: A Persistent Learned Index for Non-Volatile Memory with High Performance and Instant Recovery 2023 VLDB 5.4158958e-05
5,655 NFL: Robust Learned Index via Distribution Transformation 2022 VLDB 5.3877506e-05
5,682 LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems 2022 SIGMOD 5.3752251e-05
5,769 Oasis: An Optimal Disjoint Segmented Learned Range Filter 2024 VLDB 5.3326049e-05
5,801 Dissecting, Designing, and Optimizing LSM-based Data Stores 2022 SIGMOD 5.3217858e-05
5,978 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 5.2424396e-05
6,298 Towards instance-optimized data systems 2021 VLDB 5.1182917e-05
6,442 Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices 2023 SIGMOD 5.0541252e-05
6,488 FILM: a Fully Learned Index for Larger-than-Memory Databases 2023 VLDB 5.0378878e-05
6,723 A Critical Analysis of Recursive Model Indexes 2022 VLDB 4.9449538e-05
6,806 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 4.917024e-05
7,389 Making In-Memory Learned Indexes Efficient on Disk 2024 SIGMOD 4.7386163e-05
7,654 LiteHST: A Tree Embedding based Method for Similarity Search 2023 SIGMOD 4.6831082e-05
7,870 SALI: A Scalable Adaptive Learned Index Framework based on Probability Models 2023 SIGMOD 4.6271153e-05
7,916 HINT: A Hierarchical Index for Intervals in Main Memory 2022 SIGMOD 4.6133471e-05
8,079 Accelerating String-key Learned Index Structures via Memoization-based Incremental Training 2024 VLDB 4.5873372e-05
8,100 Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction 2024 SIGMOD 4.5821762e-05
8,221 Sieve: A Learned Data-Skipping Index for Data Analytics 2023 VLDB 4.5511941e-05
8,408 The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures 2022 VLDB 4.5159669e-05
8,411 The Case for Learned In-Memory Joins 2023 VLDB 4.5151296e-05
8,624 Limousine: Blending Learned and Classical Indexes to Self-Design Larger-than-Memory Cloud Storage Engines 2024 SIGMOD 4.4786127e-05
8,636 WISK: A Workload-aware Learned Index for Spatial Keyword Queries 2023 SIGMOD 4.4758336e-05
8,648 HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle 2022 SIGMOD 4.4718808e-05
8,653 Adaptive Hybrid Indexes 2022 SIGMOD 4.4696663e-05
8,668 Algorithmic Complexity Attacks on Dynamic Learned Indexes 2024 VLDB 4.4671214e-05
8,811 Tuning Hierarchical Learned Indexes on Disk and Beyond 2022 SIGMOD 4.4398976e-05
9,093 AirIndex: Versatile Index Tuning Through Data and Storage 2023 SIGMOD 4.3932886e-05
9,290 PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy 2024 VLDB 4.358174e-05
9,322 Are Joins over LSM-trees Ready? Take RocksDB as an Example 2025 VLDB 4.351469e-05
9,351 Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs 2024 SIGMOD 4.3490308e-05
9,618 A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach 2025 SIGMOD 4.3131993e-05
9,745 Why Are Learned Indexes So Effective but Sometimes Ineffective? 2025 VLDB 4.2856385e-05
9,826 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 4.2710095e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
101 The Case for Learned Index Structures 2018 SIGMOD 0.00049778866
240 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00031526134
796 SageDB: A Learned Database System 2019 CIDR 0.00016541749
1,033 Bitmap Index Design and Evaluation 1998 SIGMOD 0.0001453376
1,365 FITing-Tree: A Data-aware Index Structure 2019 SIGMOD 0.00012379754
1,909 BF-Tree: Approximate Tree Indexing 2014 VLDB 0.00010123661
2,045 Indexable PLA for Efficient Similarity Search 2007 VLDB 9.6950855e-05
2,046 Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units 2011 VLDB 9.6922338e-05
2,313 Building a Bw-Tree Takes More Than Just Buzz Words 2018 SIGMOD 9.0546844e-05
2,821 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 8.0639288e-05
3,482 Optimal Column Layout for Hybrid Workloads 2019 VLDB 7.0514808e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,183 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013444058
6,226 When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories 2023 SIGMOD 5.1413982e-05
8,811 Tuning Hierarchical Learned Indexes on Disk and Beyond 2022 SIGMOD 4.4398976e-05
5,154 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 5.6548237e-05
1,438 Benchmarking Learned Indexes 2021 VLDB 0.00011965956
7,389 Making In-Memory Learned Indexes Efficient on Disk 2024 SIGMOD 4.7386163e-05
5,072 Learned Index: A Comprehensive Experimental Evaluation 2023 VLDB 5.7121108e-05
6,442 Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices 2023 SIGMOD 5.0541252e-05
8,764 Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes 2009 PODS 4.4520434e-05
9,745 Why Are Learned Indexes So Effective but Sometimes Ineffective? 2025 VLDB 4.2856385e-05