Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs

Summary: Build-time bottleneck in learned indexes tackled via sampled learning: Sample EB-PLA and Sample EB-Histogram, both error-bounded. Shows >10x faster construction while exposing new trade-offs among sampling rate, model error, size, and lookup latency. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID: 6883
Venue: SIGMOD
Year: 2024
Pagerank: 4.3490308e-05
Overall Rank: 9,351 | 35.02%
DOI: 10.1145/3654919

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,038	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,169	From Learning to Recycling: A Log-Structured Learned-Less Index	2026	SIGMOD	4.1905499e-05
10,172	HIRE: A Hybrid Learned Index for Robust and Efficient Performance under Mixed Workloads	2026	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
101	The Case for Learned Index Structures	2018	SIGMOD	0.00049778866
819	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00016237497
844	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00015964123
1,365	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00012379754
1,438	Benchmarking Learned Indexes	2021	VLDB	0.00011965956
1,464	Learning Multi-dimensional Indexes	2020	SIGMOD	0.0001184772
1,887	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00010201938
2,108	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	9.5283642e-05
2,550	Updatable Learned Index with Precise Positions	2021	VLDB	8.5569576e-05
3,136	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	7.4926368e-05
3,945	APEX: A High-Performance Learned Index on Persistent Memory	2022	VLDB	6.605467e-05
4,056	Are Updatable Learned Indexes Ready?	2022	VLDB	6.4905689e-05
4,069	CDFShop: Exploring and Optimizing Learned Index Structures	2020	SIGMOD	6.4744708e-05
4,086	The Case for a Learned Sorting Algorithm	2020	SIGMOD	6.4579358e-05
4,404	TreeLine: An Update-In-Place Key-Value Store for Modern Storage	2023	VLDB	6.2052645e-05
5,072	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	5.7121108e-05
5,154	Hist-Tree: Those Who Ignore It Are Doomed to Learn	2021	CIDR	5.6548237e-05
6,298	Towards instance-optimized data systems	2021	VLDB	5.1182917e-05
6,442	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD	5.0541252e-05
6,488	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	5.0378878e-05
6,723	A Critical Analysis of Recursive Model Indexes	2022	VLDB	4.9449538e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,754	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.1905499e-05
7,389	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	4.7386163e-05
8,811	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD	4.4398976e-05
10,087	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	4.1905499e-05
101	The Case for Learned Index Structures	2018	SIGMOD	0.00049778866
9,760	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2838028e-05
4,056	Are Updatable Learned Indexes Ready?	2022	VLDB	6.4905689e-05
1,438	Benchmarking Learned Indexes	2021	VLDB	0.00011965956
5,072	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	5.7121108e-05
7,770	Modeling High-Dimensional Index Structures using Sampling	2001	SIGMOD	4.6515743e-05