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: 12778
Venue: VLDB
Year: 2021
Pagerank: 0.00011817414
Overall Rank: 1,174 | 91.95%
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
9,974	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.1845938e-05
10,066	Check Out the Big Brain on BRAD: Simplifying Cloud Data Processing with Learned Automated Data Meshes	2023	VLDB	5.1643809e-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,378	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	5.093636e-05
10,469	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	5.093636e-05
10,610	A Workload-Aware Encrypted Index for Efficient Privacy-Preserving Range Queries	2026	VLDB	5.093636e-05
10,672	Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve	2025	SIGMOD	5.093636e-05
10,984	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	5.093636e-05
11,193	BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data	2024	SIGMOD	5.093636e-05
11,282	KGFabric: A Scalable Knowledge Graph Warehouse for Enterprise Data Interconnection	2024	VLDB	5.093636e-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.001157935
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00069513174
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
59	Differential Files: Their Application To The Maintenance Of Large Data Bases	1976	SIGMOD	0.00040060625
156	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00028636811
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
447	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018322593
461	Query-based Workload Forecasting for Self-Driving Database Management Systems	2018	SIGMOD	0.00018068441
477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017851226
790	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.0001401445
873	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013481915
1,135	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00012032847
1,418	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010835539
1,500	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010561098
1,648	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	0.00010120668
2,155	Integrating the UB-Tree into a Database System Kernel	2000	VLDB	9.0713545e-05
2,213	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.9410226e-05
2,302	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.7808696e-05
3,449	CORADD: Correlation Aware Database Designer for Materialized Views and Indexes	2010	VLDB	7.4074656e-05

Semantically Similar Papers

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