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: 12126
Venue: VLDB
Year: 2019
Pagerank: 8.5552968e-05
Overall Rank: 2,455 | 83.16%
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 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,221	Camel: Managing Data for Efficient Stream Learning	2022	SIGMOD	7.6271601e-05
4,472	Relative Error Streaming Quantiles	2021	PODS	6.6810874e-05
7,256	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.6625146e-05
7,455	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	5.6127752e-05
8,616	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.4004741e-05
8,878	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	5.3532614e-05
9,386	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	5.2755515e-05
9,618	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	5.2434488e-05
10,487	Quantile Estimation with Duplicates	2026	SIGMOD	5.093636e-05
10,612	Index Intersection for High-Dimensional Range Queries	2026	VLDB	5.093636e-05
10,675	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	5.093636e-05
10,865	Approximation-First Timeseries Query At Scale	2025	VLDB	5.093636e-05
11,450	CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space	2023	VLDB	5.093636e-05
11,700	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	5.093636e-05
11,703	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	5.093636e-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
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
230	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023891474
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
451	Mergeable Summaries	2012	PODS	0.00018151445
828	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013769869
1,352	Scuba: Diving into Data at Facebook	2013	VLDB	0.00011064595
2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.2108958e-05
2,747	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	8.1711208e-05
3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.7470414e-05

Semantically Similar Papers

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