Randomized Sketches for Quantile in LSM-tree based Store

Summary: Randomized pre-computed sketches enable sublinear I/O for quantiles in LSM-tree stores. Flush-time chunks yield O(√N) I/O; hierarchical SSTable sketches and KLL summaries beat streaming; validated in Apache IoTDB. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7060
Venue: SIGMOD
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,388 | 27.74%
DOI: 10.1145/3709717

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Ziling Chen
2. Shaoxu Song

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
140	The MADlib Analytics Library or MAD Skills, the SQL	2012	VLDB	0.00042270404
402	Mergeable Summaries	2012	PODS	0.00024196343
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
609	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.0001923446
1,311	Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging	2018	SIGMOD	0.00012657439
2,914	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	7.9118579e-05
3,967	Apache IoTDB: A Time Series Database for IoT Applications	2023	SIGMOD	6.5796647e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
5,535	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	5.4539235e-05
5,627	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.403782e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05
11,505	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05
7,515	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	4.7180617e-05
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
1,064	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014356481
5,627	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.403782e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1945683e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05