From Worst-Case to Average-Case Analysis: Accurate Latency Predictions for Key-Value Storage Engines

Summary: Average-case latency analysis for storage engines, surpassing worst-case models. A distribution-aware framework predicts latency across diverse workloads and data structures; validated with tuning models on RocksDB and WiredTiger. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h497ac6c6d48fb9d1
Venue: SIGMOD
Year: 2020
Pagerank: 5.0925155e-05
Overall Rank: 10,035 | 32.54%
DOI: 10.1145/3318464.3384408

Incoming Non-self Citations Over Time

Authors

1. Meena Jagadeesan (Harvard University)
2. Garrett Tanzer (Harvard University)

BibTeX Citation

@inproceedings{jagadeesan_sigmod20,
        title = {{From Worst-Case to Average-Case Analysis: Accurate Latency Predictions for Key-Value Storage Engines}},
        author = {Jagadeesan, Meena and Tanzer, Garrett},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3384408},
        url = {https://dl.acm.org/doi/10.1145/3318464.3384408},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,758	Dynamic read & write optimization with TurtleKV	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
400	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00019129175
754	Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging	2018	SIGMOD	0.00014236015
1,605	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	0.00010093796
1,889	Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn	2019	CIDR	9.4273689e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,029	LavaStore: ByteDance's Purpose-built, High-performance, Cost-effective Local Storage Engine for Cloud Services	2024	VLDB
2	10,658	Making LSM-Tree-based Key-Value Store Practical and Efficient for Multi-Tenant Serverless Cloud Databases	2026	SIGMOD
3	7,241	CaaS-LSM: Compaction-as-a-Service for LSM-based Key-Value Stores in Storage Disaggregated Infrastructure	2024	SIGMOD
4	3,976	Take me to your leader! Online Optimization of Distributed Storage Configurations	2015	VLDB
5	3,952	Storage Workload Estimation for Database Management Systems	2007	SIGMOD
6	4,048	Fast Scans on Key-Value Stores	2017	VLDB
7	1,569	Compaction management in distributed key-value datastores	2015	VLDB
8	4,685	Enabling Low Tail Latency on Multicore Key-Value Stores	2020	VLDB
9	10,543	Analysis and Evaluation of Using Microsecond-Latency Memory for In-Memory Indices and Caches in SSD-Based Key-Value Stores	2026	SIGMOD
10	3,525	Key-Value Storage Engines	2020	SIGMOD