Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads

Summary: Tsunami, a learned multi-dimensional index for correlated data and skewed workloads, addresses tuning gaps in prior learned MDIs. It delivers up to 6x faster queries and 8x smaller index than prior learned MDI, and up to 11x faster and 170x smaller than optimally-tuned traditional indexes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h1c4dfa96dd19d858
Venue: VLDB
Year: 2021
Pagerank: 0.00011590153
Overall Rank: 1,191 | 92.00%
DOI: 10.14778/3425879.3425880

Incoming Non-self Citations Over Time

Authors

1. Jialin Ding (Massachusetts Institute of Technology)
2. Vikram Nathan (Massachusetts Institute of Technology)
3. Mohammad Alizadeh (Massachusetts Institute of Technology)
4. Tim Kraska (Massachusetts Institute of Technology)

BibTeX Citation

@article{ding_vldb21,
        title = {{Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads}},
        author = {Ding, Jialin and Nathan, Vikram and Alizadeh, Mohammad and Kraska, Tim},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {2},
        pages = {74--86},
        doi = {10.14778/3425879.3425880},
        url = {https://doi.org/10.14778/3425879.3425880},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 61 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,043	The Image Calculator: 10x Faster Image-AI Inference by Replacing JPEG with Self-designing Storage Format	2024	SIGMOD	5.0921006e-05
10,048	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	5.0899328e-05
10,168	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.0682654e-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,575	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	4.9793485e-05
10,656	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	4.9793485e-05
11,057	A Workload-Aware Encrypted Index for Efficient Privacy-Preserving Range Queries	2026	VLDB	4.9793485e-05
11,113	Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve	2025	SIGMOD	4.9793485e-05
11,365	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.9793485e-05
11,606	KGFabric: A Scalable Knowledge Graph Warehouse for Enterprise Data Interconnection	2024	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00068998927
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
59	Differential Files: Their Application To The Maintenance Of Large Data Bases	1976	SIGMOD	0.00039605949
151	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00028672526
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027837289
430	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018409112
460	Query-based Workload Forecasting for Self-Driving Database Management Systems	2018	SIGMOD	0.00017842695
463	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017804544
779	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014030069
868	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013354403
1,132	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00011898257
1,446	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010629222
1,488	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010517437
1,662	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.9465656e-05
2,198	Integrating the UB-Tree into a Database System Kernel	2000	VLDB	8.8759215e-05
2,238	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7751619e-05
2,329	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.6292256e-05
3,500	CORADD: Correlation Aware Database Designer for Materialized Views and Indexes	2010	VLDB	7.2534237e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,711	Learned Index Benefits: Machine Learning Based Index Performance Estimation	2022	VLDB
2	7,900	DISTILL: Low-Overhead Data-Driven Techniques for Filtering and Costing Indexes for Scalable Index Tuning	2022	VLDB
3	2,238	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD
4	3,697	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB
5	4,374	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS
6	10,185	SWIX: A Memory-efficient Sliding Window Learned Index	2024	SIGMOD
7	5,630	ISUM: Efficiently Compressing Large and Complex Workloads for Scalable Index Tuning	2022	SIGMOD
8	6,607	Wave-Indices: Indexing Evolving Databases	1997	SIGMOD
9	11,365	Benchmarking Adaptive Multidimensional Indices	2025	VLDB
10	868	Learning Multi-dimensional Indexes	2020	SIGMOD