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: 12222
Venue: VLDB
Year: 2020
Pagerank: 0.00017851226
Overall Rank: 477 | 96.73%
DOI: 10.14778/3389133.3389135

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 25 of 75 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,465	Are Joins over LSM-trees Ready? Take RocksDB as an Example	2025	VLDB	5.2634238e-05
9,599	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	5.2492748e-05
9,892	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB	5.1997534e-05
9,974	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.1845938e-05
9,998	SWIX: A Memory-efficient Sliding Window Learned Index	2024	SIGMOD	5.1814573e-05
10,097	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.1502319e-05
10,260	L3: A GPU-Native Co-Designed Data Format for Learned Lossless Lightweight Compression	2026	SIGMOD	5.093636e-05
10,261	LICO: An SIMD-Aware High-Performance Learned Inverted Index Compression Framework	2026	SIGMOD	5.093636e-05
10,262	LINE: A Learned Index with Group-Enhanced Leaves and Cache-Optimized Inner Tree	2026	SIGMOD	5.093636e-05
10,267	Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions	2026	SIGMOD	5.093636e-05
10,277	On Self-Designing Learned Indexes	2026	SIGMOD	5.093636e-05
10,315	Fast Indexing for Temporal Information Retrieval	2026	SIGMOD	5.093636e-05
10,378	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	5.093636e-05
10,458	From Learning to Recycling: A Log-Structured Learned-Less Index	2026	SIGMOD	5.093636e-05
10,461	HIRE: A Hybrid Learned Index for Robust and Efficient Performance under Mixed Workloads	2026	SIGMOD	5.093636e-05
10,569	Toward Drift-Aware Database Benchmarking	2026	VLDB	5.093636e-05
10,591	Vodka: Rethink Benchmarking Philosophy in HTAP Systems	2026	VLDB	5.093636e-05
10,617	LiBox: A Learned Index as an Array to Minimize Last-Mile Search	2026	VLDB	5.093636e-05
10,624	Learned Static Function Data Structures	2026	VLDB	5.093636e-05
10,682	VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity	2025	SIGMOD	5.093636e-05
10,944	Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks	2025	VLDB	5.093636e-05
10,955	DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees	2025	VLDB	5.093636e-05
11,051	LETIndex: A Secure Learned Index with TEE	2025	VLDB	5.093636e-05
11,059	Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects	2025	VLDB	5.093636e-05
11,475	Route Travel Time Estimation on A Road Network Revisited: Heterogeneity, Proximity, Periodicity and Dynamicity	2023	VLDB	5.093636e-05

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

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