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

Summary: DDSketch is the first fully mergeable quantile sketch with formal relative-error guarantees, avoiding rank-error failures on skewed data. Its logarithmic value mapping delivers fast, accurate summaries for distributed streams and production-scale use. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h97abdab416646f8f
Venue: VLDB
Year: 2019
Pagerank: 8.4766851e-05
Overall Rank: 2,432 | 83.65%
DOI: 10.14778/3352063.3352135

Incoming Non-self Citations Over Time

Authors

1. Charles Masson (Datadog)
2. Jee E. Rim (Datadog)
3. Homin K. Lee (Datadog)

BibTeX Citation

@article{masson_vldb19,
        title = {{DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees}},
        author = {Masson, Charles and Rim, Jee E. and Lee, Homin K.},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {12},
        pages = {2195--2205},
        doi = {10.14778/3352063.3352135},
        url = {https://doi.org/10.14778/3352063.3352135},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,284	Camel: Managing Data for Efficient Stream Learning	2022	SIGMOD	7.4560271e-05
4,564	Relative Error Streaming Quantiles	2021	PODS	6.5317429e-05
7,364	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5418075e-05
7,602	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	5.4868396e-05
8,776	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.2800094e-05
9,039	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	5.2331548e-05
9,570	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	5.1571823e-05
9,798	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	5.1257999e-05
10,674	Quantile Estimation with Duplicates	2026	SIGMOD	4.9793485e-05
10,909	Incremental Query Optimizer Statistics in Amazon Redshift	2026	VLDB	4.9793485e-05
11,059	Index Intersection for High-Dimensional Range Queries	2026	VLDB	4.9793485e-05
11,116	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	4.9793485e-05
11,268	Approximation-First Timeseries Query At Scale	2025	VLDB	4.9793485e-05
11,762	CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space	2023	VLDB	4.9793485e-05
12,005	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.9793485e-05
12,007	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	4.9793485e-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
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035978046
240	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023435436
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
456	Mergeable Summaries	2012	PODS	0.0001791284
850	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013488409
1,381	Scuba: Diving into Data at Facebook	2013	VLDB	0.00010860462
2,750	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.0573403e-05
2,798	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	7.9933329e-05
3,163	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.5789852e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,496	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
2	3,678	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
3	8,170	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD
4	3,872	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD
5	5,045	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB
6	2,798	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB
7	4,564	Relative Error Streaming Quantiles	2021	PODS
8	10,674	Quantile Estimation with Duplicates	2026	SIGMOD
9	9,570	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD
10	9,798	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD