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
12034
Venue
VLDB
Year
2020
Pagerank
0.00015882892
Overall Rank
857 | 94.04%
DOI
10.14778/3389133.3389135

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 69 citing papers.

Rank Citing Paper Year Venue Pagerank
1,460 Benchmarking Learned Indexes 2021 VLDB 0.00011887068
1,889 Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads 2021 VLDB 0.00010200865
2,552 Updatable Learned Index with Precise Positions 2021 VLDB 8.5530411e-05
2,678 Effectively Learning Spatial Indices 2020 VLDB 8.3252088e-05
3,131 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 7.4985793e-05
3,416 LeCo: Lightweight Compression via Learning Serial Correlations 2024 SIGMOD 7.1196234e-05
4,084 APEX: A High-Performance Learned Index on Persistent Memory 2022 VLDB 6.4622113e-05
4,128 Are Updatable Learned Indexes Ready? 2022 VLDB 6.4292373e-05
4,427 TreeLine: An Update-In-Place Key-Value Store for Modern Storage 2023 VLDB 6.1965873e-05
4,593 Auto-WLM: Machine Learning Enhanced Workload Management in Amazon Redshift 2023 SIGMOD 6.0606891e-05
4,646 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 6.0250374e-05
5,074 Learned Index: A Comprehensive Experimental Evaluation 2023 VLDB 5.7175726e-05
5,157 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 5.6589595e-05
5,314 Can Learned Models Replace Hash Functions? 2023 VLDB 5.5724608e-05
5,319 DILI: A Distribution-Driven Learned Index 2023 VLDB 5.5713974e-05
5,428 The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures 2022 SIGMOD 5.5091613e-05
5,572 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 5.4277273e-05
5,592 PLIN: A Persistent Learned Index for Non-Volatile Memory with High Performance and Instant Recovery 2023 VLDB 5.4210633e-05
5,642 NFL: Robust Learned Index via Distribution Transformation 2022 VLDB 5.3929294e-05
5,671 LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems 2022 SIGMOD 5.3803919e-05
5,762 Oasis: An Optimal Disjoint Segmented Learned Range Filter 2024 VLDB 5.3377299e-05
5,791 Dissecting, Designing, and Optimizing LSM-based Data Stores 2022 SIGMOD 5.3268999e-05
5,972 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 5.2474768e-05
6,297 Towards instance-optimized data systems 2021 VLDB 5.1227886e-05
6,445 Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices 2023 SIGMOD 5.0589805e-05
6,492 FILM: a Fully Learned Index for Larger-than-Memory Databases 2023 VLDB 5.042727e-05
6,724 A Critical Analysis of Recursive Model Indexes 2022 VLDB 4.9484506e-05
7,042 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 4.8541986e-05
7,390 Making In-Memory Learned Indexes Efficient on Disk 2024 SIGMOD 4.7431654e-05
7,654 LiteHST: A Tree Embedding based Method for Similarity Search 2023 SIGMOD 4.687476e-05
7,869 SALI: A Scalable Adaptive Learned Index Framework based on Probability Models 2023 SIGMOD 4.6315248e-05
7,915 HINT: A Hierarchical Index for Intervals in Main Memory 2022 SIGMOD 4.617775e-05
8,076 Accelerating String-key Learned Index Structures via Memoization-based Incremental Training 2024 VLDB 4.5917398e-05
8,101 Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction 2024 SIGMOD 4.5854141e-05
8,222 Sieve: A Learned Data-Skipping Index for Data Analytics 2023 VLDB 4.5555621e-05
8,414 The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures 2022 VLDB 4.5203005e-05
8,417 The Case for Learned In-Memory Joins 2023 VLDB 4.5194164e-05
8,627 Limousine: Blending Learned and Classical Indexes to Self-Design Larger-than-Memory Cloud Storage Engines 2024 SIGMOD 4.4829101e-05
8,636 WISK: A Workload-aware Learned Index for Spatial Keyword Queries 2023 SIGMOD 4.4801284e-05
8,650 HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle 2022 SIGMOD 4.4761716e-05
8,655 Adaptive Hybrid Indexes 2022 SIGMOD 4.4739554e-05
8,671 Algorithmic Complexity Attacks on Dynamic Learned Indexes 2024 VLDB 4.4714076e-05
8,811 Tuning Hierarchical Learned Indexes on Disk and Beyond 2022 SIGMOD 4.4441574e-05
9,095 AirIndex: Versatile Index Tuning Through Data and Storage 2023 SIGMOD 4.3975034e-05
9,285 PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy 2024 VLDB 4.3623546e-05
9,317 Are Joins over LSM-trees Ready? Take RocksDB as an Example 2025 VLDB 4.3556432e-05
9,346 Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs 2024 SIGMOD 4.3532026e-05
9,618 A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach 2025 SIGMOD 4.3173366e-05
9,746 Why Are Learned Indexes So Effective but Sometimes Ineffective? 2025 VLDB 4.2897489e-05
9,827 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 4.2751057e-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
102 The Case for Learned Index Structures 2018 SIGMOD 0.00049545203
238 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00031642425
801 SageDB: A Learned Database System 2019 CIDR 0.00016505496
1,035 Bitmap Index Design and Evaluation 1998 SIGMOD 0.00014532778
1,375 FITing-Tree: A Data-aware Index Structure 2019 SIGMOD 0.00012303141
1,913 BF-Tree: Approximate Tree Indexing 2014 VLDB 0.00010113937
2,041 Indexable PLA for Efficient Similarity Search 2007 VLDB 9.6992894e-05
2,051 Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units 2011 VLDB 9.686731e-05
2,394 Building a Bw-Tree Takes More Than Just Buzz Words 2018 SIGMOD 8.9001843e-05
2,862 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 7.9898539e-05
3,488 Optimal Column Layout for Hybrid Workloads 2019 VLDB 7.0479329e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,182 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013455963
6,229 When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories 2023 SIGMOD 5.1463389e-05
8,811 Tuning Hierarchical Learned Indexes on Disk and Beyond 2022 SIGMOD 4.4441574e-05
5,157 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 5.6589595e-05
1,460 Benchmarking Learned Indexes 2021 VLDB 0.00011887068
7,390 Making In-Memory Learned Indexes Efficient on Disk 2024 SIGMOD 4.7431654e-05
5,074 Learned Index: A Comprehensive Experimental Evaluation 2023 VLDB 5.7175726e-05
6,445 Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices 2023 SIGMOD 5.0589805e-05
8,767 Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes 2009 PODS 4.456315e-05
9,746 Why Are Learned Indexes So Effective but Sometimes Ineffective? 2025 VLDB 4.2897489e-05