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.00017804544
Overall Rank
463 | 96.89%
DOI
10.14778/3389133.3389135

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 27 of 77 citing papers.

Rank Citing Paper Year Venue Pagerank
9,646 Are Joins over LSM-trees Ready? Take RocksDB as an Example 2025 VLDB 5.1453267e-05
9,777 Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis] 2026 SIGMOD 5.1314952e-05
9,910 Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects 2025 VLDB 5.1103839e-05
9,918 Route Travel Time Estimation on A Road Network Revisited: Heterogeneity, Proximity, Periodicity and Dynamicity 2023 VLDB 5.1103839e-05
10,078 Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts 2025 VLDB 5.0830849e-05
10,168 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 5.0682654e-05
10,185 SWIX: A Memory-efficient Sliding Window Learned Index 2024 SIGMOD 5.0651993e-05
10,322 SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index 2026 SIGMOD 5.0346745e-05
10,473 L3: A GPU-Native Co-Designed Data Format for Learned Lossless Lightweight Compression 2026 SIGMOD 4.9793485e-05
10,474 LICO: An SIMD-Aware High-Performance Learned Inverted Index Compression Framework 2026 SIGMOD 4.9793485e-05
10,475 LINE: A Learned Index with Group-Enhanced Leaves and Cache-Optimized Inner Tree 2026 SIGMOD 4.9793485e-05
10,480 Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions 2026 SIGMOD 4.9793485e-05
10,489 On Self-Designing Learned Indexes 2026 SIGMOD 4.9793485e-05
10,525 Fast Indexing for Temporal Information Retrieval 2026 SIGMOD 4.9793485e-05
10,575 High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff 2026 SIGMOD 4.9793485e-05
10,645 From Learning to Recycling: A Log-Structured Learned-Less Index 2026 SIGMOD 4.9793485e-05
10,648 HIRE: A Hybrid Learned Index for Robust and Efficient Performance under Mixed Workloads 2026 SIGMOD 4.9793485e-05
10,751 Toward Drift-Aware Database Benchmarking 2026 VLDB 4.9793485e-05
10,764 Kirin: Efficient In-Storage Learned Compaction for LSM-Trees via System-Algorithm Co-Design 2026 VLDB 4.9793485e-05
10,844 Rethinking Learned Index and LSM-tree Integration 2026 VLDB 4.9793485e-05
11,015 Vodka: Rethink Benchmarking Philosophy in HTAP Systems 2026 VLDB 4.9793485e-05
11,064 LiBox: A Learned Index as an Array to Minimize Last-Mile Search 2026 VLDB 4.9793485e-05
11,070 Learned Static Function Data Structures 2026 VLDB 4.9793485e-05
11,122 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 4.9793485e-05
11,332 Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks 2025 VLDB 4.9793485e-05
11,342 DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees 2025 VLDB 4.9793485e-05
11,414 LETIndex: A Secure Learned Index with TEE 2025 VLDB 4.9793485e-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.00046284649
207 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00024970987
555 SageDB: A Learned Database System 2019 CIDR 0.00016506678
773 Bitmap Index Design and Evaluation 1998 SIGMOD 0.00014084831
779 FITing-Tree: A Data-aware Index Structure 2019 SIGMOD 0.00014030069
1,320 Building a Bw-Tree Takes More Than Just Buzz Words 2018 SIGMOD 0.00011045319
1,510 BF-Tree: Approximate Tree Indexing 2014 VLDB 0.00010438563
1,671 Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units 2011 VLDB 9.9310625e-05
1,731 Indexable PLA for Efficient Similarity Search 2007 VLDB 9.7639519e-05
2,201 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 8.8726671e-05
2,882 Optimal Column Layout for Hybrid Workloads 2019 VLDB 7.9116043e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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