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: 7122
Venue: SIGMOD
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,675 | 26.77%
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 (Tsinghua University)
2. Shaoxu Song (Tsinghua University)

BibTeX Citation

@inproceedings{chen_sigmod25,
        title = {{Randomized Sketches for Quantile in LSM-tree based Store}},
        author = {Chen, Ziling and Song, Shaoxu},
        series = {{SIGMOD} '25},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3709717},
        url = {https://dl.acm.org/doi/10.1145/3709717},
        year = {2025}
}

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
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
106	The MADlib Analytics Library or MAD Skills, the SQL	2012	VLDB	0.00033539462
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018373044
446	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00018332392
451	Mergeable Summaries	2012	PODS	0.00018151445
831	Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging	2018	SIGMOD	0.00013748512
2,455	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	8.5552968e-05
3,793	Apache IoTDB: A Time Series Database for IoT Applications	2023	SIGMOD	7.1217835e-05
4,472	Relative Error Streaming Quantiles	2021	PODS	6.6810874e-05
4,945	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	6.4321265e-05
5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.3283918e-05
9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	5.289545e-05
11,703	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB
2	10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
3	9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
4	7,936	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD
5	443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD
6	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
7	5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB
8	10,487	Quantile Estimation with Duplicates	2026	SIGMOD
9	4,472	Relative Error Streaming Quantiles	2021	PODS
10	9,386	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD