DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees

Summary: DDSketch, a fast, fully-mergeable quantile sketch with formal relative-error guarantees. First to provide true relative-error bounds under skew and seamless merge across distributed streams; practical and deployed (Datadog). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11938
Venue: VLDB
Year: 2019
Pagerank: 7.9118579e-05
Overall Rank: 2,914 | 79.73%
DOI: 10.14778/3352063.3352135

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,643	Camel: Managing Data for Efficient Stream Learning	2022	SIGMOD	8.384956e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
7,358	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	4.7529363e-05
7,451	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	4.7263711e-05
8,673	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	4.4709116e-05
8,717	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	4.4614498e-05
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05
10,113	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	4.1945683e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1945683e-05
10,314	Index Intersection for High-Dimensional Range Queries	2026	VLDB	4.1945683e-05
10,388	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	4.1945683e-05
10,608	Approximation-First Timeseries Query At Scale	2025	VLDB	4.1945683e-05
11,250	CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space	2023	VLDB	4.1945683e-05
11,502	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.1945683e-05
11,505	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
323	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00027492196
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
402	Mergeable Summaries	2012	PODS	0.00024196343
905	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.0001546195
1,487	Scuba: Diving into Data at Facebook	2013	VLDB	0.00011701099
2,748	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	8.1785955e-05
2,953	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	7.8267643e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
8,062	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	4.5943269e-05
3,808	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.7455428e-05
5,627	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.403782e-05
2,953	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	7.8267643e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1945683e-05
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05
10,113	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	4.1945683e-05