DBScholar

Back to papers

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

Summary: Introduces PGM-index, the first fully dynamic learned index with provable worst-case bounds and optimal static predecessor/range performance. Distribution-aware, repetitive-model compression, and multicriteria variants yield orders-of-magnitude space savings over B+-trees. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h5389ed8b56536601
Venue
VLDB
Year
2020
Pagerank
0.00017835351
Overall Rank
461 | 96.92%
DOI
10.14778/3389133.3389135
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{ferragina_vldb20,
        title = {{The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds}},
        author = {Ferragina, Paolo and Vinciguerra, Giorgio},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {8},
        pages = {1162--1175},
        doi = {10.14778/3389133.3389135},
        url = {https://doi.org/10.14778/3389133.3389135},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 78 citing papers.

Rank Citing Paper Year Venue Pagerank
9,681 Are Joins over LSM-trees Ready? Take RocksDB as an Example 2025 VLDB 5.1258854e-05
9,814 Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis] 2026 SIGMOD 5.1121061e-05
9,952 Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects 2025 VLDB 5.0910746e-05
9,960 Route Travel Time Estimation on A Road Network Revisited: Heterogeneity, Proximity, Periodicity and Dynamicity 2023 VLDB 5.0910746e-05
10,117 Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts 2025 VLDB 5.0638787e-05
10,206 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 5.0491152e-05
10,222 SWIX: A Memory-efficient Sliding Window Learned Index 2024 SIGMOD 5.0460607e-05
10,335 DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees 2025 VLDB 5.0225409e-05
10,355 SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index 2026 SIGMOD 5.0156513e-05
10,417 Replace or Augment: Rethinking the Role of Learned Indexes in Relational Databases 2027 VLDB 4.9605343e-05
10,550 L3: A GPU-Native Co-Designed Data Format for Learned Lossless Lightweight Compression 2026 SIGMOD 4.9605343e-05
10,551 LICO: An SIMD-Aware High-Performance Learned Inverted Index Compression Framework 2026 SIGMOD 4.9605343e-05
10,552 LINE: A Learned Index with Group-Enhanced Leaves and Cache-Optimized Inner Tree 2026 SIGMOD 4.9605343e-05
10,557 Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions 2026 SIGMOD 4.9605343e-05
10,566 On Self-Designing Learned Indexes 2026 SIGMOD 4.9605343e-05
10,602 Fast Indexing for Temporal Information Retrieval 2026 SIGMOD 4.9605343e-05
10,649 High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff 2026 SIGMOD 4.9605343e-05
10,717 From Learning to Recycling: A Log-Structured Learned-Less Index 2026 SIGMOD 4.9605343e-05
10,720 HIRE: A Hybrid Learned Index for Robust and Efficient Performance under Mixed Workloads 2026 SIGMOD 4.9605343e-05
10,822 Toward Drift-Aware Database Benchmarking 2026 VLDB 4.9605343e-05
10,835 Kirin: Efficient In-Storage Learned Compaction for LSM-Trees via System-Algorithm Co-Design 2026 VLDB 4.9605343e-05
10,915 Rethinking Learned Index and LSM-tree Integration 2026 VLDB 4.9605343e-05
11,085 Vodka: Rethink Benchmarking Philosophy in HTAP Systems 2026 VLDB 4.9605343e-05
11,134 LiBox: A Learned Index as an Array to Minimize Last-Mile Search 2026 VLDB 4.9605343e-05
11,140 Learned Static Function Data Structures 2026 VLDB 4.9605343e-05
11,191 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 4.9605343e-05
11,393 Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks 2025 VLDB 4.9605343e-05
11,473 LETIndex: A Secure Learned Index with TEE 2025 VLDB 4.9605343e-05
Previous Page 2 / 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
40 The Case for Learned Index Structures 2018 SIGMOD 0.00046249672
209 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00024915373
550 SageDB: A Learned Database System 2019 CIDR 0.00016525249
774 FITing-Tree: A Data-aware Index Structure 2019 SIGMOD 0.00014063511
776 Bitmap Index Design and Evaluation 1998 SIGMOD 0.0001406101
1,328 Building a Bw-Tree Takes More Than Just Buzz Words 2018 SIGMOD 0.00011013165
1,507 BF-Tree: Approximate Tree Indexing 2014 VLDB 0.0001041737
1,658 Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units 2011 VLDB 9.945593e-05
1,738 Indexable PLA for Efficient Similarity Search 2007 VLDB 9.7335994e-05
2,017 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 9.169662e-05
2,891 Optimal Column Layout for Hybrid Workloads 2019 VLDB 7.887378e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,514 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS
2 6,075 When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories 2023 SIGMOD
3 8,401 Tuning Hierarchical Learned Indexes on Disk and Beyond 2022 SIGMOD
4 4,727 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR
5 834 Benchmarking Learned Indexes 2021 VLDB
6 6,622 Making In-Memory Learned Indexes Efficient on Disk 2024 SIGMOD
7 3,632 Learned Index: A Comprehensive Experimental Evaluation 2023 VLDB
8 5,397 Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices 2023 SIGMOD
9 9,129 Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes 2009 PODS
10 8,903 Why Are Learned Indexes So Effective but Sometimes Ineffective? 2025 VLDB