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)
Incoming Non-self Citations Over Time
Authors
- 1. Paolo Ferragina (University of Pisa)
- 2. Giorgio Vinciguerra (University of Pisa)
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 50 of 75 citing papers.
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 |
|---|---|---|---|---|
| 43 | The Case for Learned Index Structures | 2018 | SIGMOD | 0.00046060254 |
| 204 | Cache Conscious Indexing for Decision-Support in Main Memory | 1999 | VLDB | 0.00025342994 |
| 568 | SageDB: A Learned Database System | 2019 | CIDR | 0.0001641553 |
| 790 | FITing-Tree: A Data-aware Index Structure | 2019 | SIGMOD | 0.0001401445 |
| 794 | Bitmap Index Design and Evaluation | 1998 | SIGMOD | 0.00013969303 |
| 1,390 | Building a Bw-Tree Takes More Than Just Buzz Words | 2018 | SIGMOD | 0.00010942775 |
| 1,492 | BF-Tree: Approximate Tree Indexing | 2014 | VLDB | 0.00010588267 |
| 1,655 | Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units | 2011 | VLDB | 0.00010103504 |
| 1,722 | Indexable PLA for Efficient Similarity Search | 2007 | VLDB | 9.9227051e-05 |
| 2,224 | An Experimental Study of Bitmap Compression vs. Inverted List Compression | 2017 | SIGMOD | 8.9183396e-05 |
| 2,866 | Optimal Column Layout for Hybrid Workloads | 2019 | VLDB | 8.0175489e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 1,529 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS |
| 2 | 5,954 | When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories | 2023 | SIGMOD |
| 3 | 8,214 | Tuning Hierarchical Learned Indexes on Disk and Beyond | 2022 | SIGMOD |
| 4 | 4,660 | Hist-Tree: Those Who Ignore It Are Doomed to Learn | 2021 | CIDR |
| 5 | 847 | Benchmarking Learned Indexes | 2021 | VLDB |
| 6 | 6,687 | Making In-Memory Learned Indexes Efficient on Disk | 2024 | SIGMOD |
| 7 | 3,792 | Learned Index: A Comprehensive Experimental Evaluation | 2023 | VLDB |
| 8 | 5,423 | Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices | 2023 | SIGMOD |
| 9 | 8,937 | Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes | 2009 | PODS |
| 10 | 8,709 | Why Are Learned Indexes So Effective but Sometimes Ineffective? | 2025 | VLDB |