DBScholar

Back to papers

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.00011564169
Overall Rank
1,190 | 92.03%
DOI
10.14778/3425879.3425880
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

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 50 of 61 citing papers.

Rank Citing Paper Year Venue Pagerank
1,791 Why TPC Is Not Enough: An Analysis of the Amazon Redshift Fleet 2024 VLDB 9.6212919e-05
2,254 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 8.7429699e-05
2,590 Are Updatable Learned Indexes Ready? 2022 VLDB 8.2368464e-05
2,772 Instance-Optimized Data Layouts for Cloud Analytics Workloads 2021 SIGMOD 8.0148928e-05
2,870 APEX: A High-Performance Learned Index on Persistent Memory 2022 VLDB 7.9033232e-05
3,328 Auto-WLM: Machine Learning Enhanced Workload Management in Amazon Redshift 2023 SIGMOD 7.4094448e-05
3,632 Learned Index: A Comprehensive Experimental Evaluation 2023 VLDB 7.1274345e-05
3,716 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 7.0541948e-05
4,385 NFL: Robust Learned Index via Distribution Transformation 2022 VLDB 6.613814e-05
4,389 DILI: A Distribution-Driven Learned Index 2023 VLDB 6.6111249e-05
4,549 One Model to Rule them All: Towards Zero-Shot Learning for Databases 2022 CIDR 6.5328866e-05
4,621 The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures 2022 SIGMOD 6.4828493e-05
4,727 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 6.4327925e-05
4,773 Cuckoo Index: A Lightweight Secondary Index Structure 2020 VLDB 6.4102054e-05
4,797 LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems 2022 SIGMOD 6.3978116e-05
4,833 Stage: Query Execution Time Prediction in Amazon Redshift 2024 SIGMOD 6.3834856e-05
4,879 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 6.3567479e-05
4,915 Can Learned Models Replace Hash Functions? 2023 VLDB 6.3452789e-05
5,210 Crystal: A Unified Cache Storage System for Analytical Databases 2021 VLDB 6.2142008e-05
5,397 Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices 2023 SIGMOD 6.1347527e-05
5,728 Detect, Distill and Update: Learned DB Systems Facing Out of Distribution Data 2023 SIGMOD 5.9979958e-05
5,856 Pando: Enhanced Data Skipping with Logical Data Partitioning 2023 VLDB 5.9514226e-05
5,935 Self-Organizing Data Containers 2022 CIDR 5.9251217e-05
5,982 Towards instance-optimized data systems 2021 VLDB 5.9096991e-05
6,041 Automated Multidimensional Data Layouts in Amazon Redshift 2024 SIGMOD 5.8894534e-05
6,250 Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses 2024 SIGMOD 5.818039e-05
6,402 A Unified Transferable Model for ML-Enhanced DBMS 2022 CIDR 5.7800842e-05
6,604 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.7196547e-05
6,622 Making In-Memory Learned Indexes Efficient on Disk 2024 SIGMOD 5.7136886e-05
6,730 Replicated Layout for In-Memory Database Systems 2022 VLDB 5.6801409e-05
6,802 SALI: A Scalable Adaptive Learned Index Framework based on Probability Models 2023 SIGMOD 5.6623052e-05
6,889 Accelerating String-key Learned Index Structures via Memoization-based Incremental Training 2024 VLDB 5.6393954e-05
7,314 Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction 2024 SIGMOD 5.5425359e-05
7,363 Blueprinting the Cloud: Unifying and Automatically Optimizing Cloud Data Infrastructures with BRAD 2024 VLDB 5.5279826e-05
7,388 Towards Foundation Database Models 2025 CIDR 5.5211011e-05
7,621 SageDB: An Instance-Optimized Data Analytics System 2022 VLDB 5.4664683e-05
8,201 Towards Designing and Learning Piecewise Space-Filling Curves 2023 VLDB 5.3623066e-05
8,219 WISK: A Workload-aware Learned Index for Spatial Keyword Queries 2023 SIGMOD 5.359172e-05
8,223 Algorithmic Complexity Attacks on Dynamic Learned Indexes 2024 VLDB 5.3584214e-05
8,391 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3248747e-05
8,715 Knowledge Graph Exploration Systems: are we lost? 2022 CIDR 5.2705676e-05
8,975 Machine Unlearning in Learned Databases: An Experimental Analysis 2024 SIGMOD 5.2343759e-05
8,978 HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle 2022 SIGMOD 5.2334381e-05
9,143 Check Out the Big Brain on BRAD: Simplifying Cloud Data Processing with Learned Automated Data Meshes 2023 VLDB 5.2074327e-05
9,176 One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting 2024 SIGMOD 5.200391e-05
9,596 LeaFi: Data Series Indexes on Steroids with Learned Filters 2025 SIGMOD 5.1376962e-05
9,627 Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs 2024 SIGMOD 5.1369088e-05
9,867 AMNES: Accelerating the computation of data correlation using FPGAs 2023 VLDB 5.1056602e-05
9,961 Waffle: In-memory Grid Index for Moving Objects with Reinforcement Learning-based Configuration Tuning System 2022 VLDB 5.0910746e-05
10,017 The Image Calculator: 10x Faster Image-AI Inference by Replacing JPEG with Self-designing Storage Format 2024 SIGMOD 5.0825892e-05
Previous Page 1 / 2 Next

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.0011386412
12 C-Store: A Column-oriented DBMS 2005 VLDB 0.00068985264
40 The Case for Learned Index Structures 2018 SIGMOD 0.00046249672
59 Differential Files: Their Application To The Maintenance Of Large Data Bases 1976 SIGMOD 0.00039478403
151 An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server 1997 VLDB 0.00028611216
160 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies 2004 SIGMOD 0.00027775994
427 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00018429918
458 Query-based Workload Forecasting for Self-Driving Database Management Systems 2018 SIGMOD 0.00017870238
461 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00017835351
774 FITing-Tree: A Data-aware Index Structure 2019 SIGMOD 0.00014063511
870 Learning Multi-dimensional Indexes 2020 SIGMOD 0.0001332034
1,132 Qd-tree: Learning Data Layouts for Big Data Analytics 2020 SIGMOD 0.00011873466
1,445 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010607118
1,490 Efficient Discovery of Approximate Dependencies 2018 VLDB 0.0001047928
1,670 BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data 2003 VLDB 9.9124313e-05
2,211 Integrating the UB-Tree into a Database System Kernel 2000 VLDB 8.8443254e-05
2,249 Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations 2019 SIGMOD 8.7479608e-05
2,337 Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies 2009 VLDB 8.6002736e-05
3,509 CORADD: Correlation Aware Database Designer for Materialized Views and Indexes 2010 VLDB 7.2279142e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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