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: 11939
Venue: VLDB
Year: 2019
Pagerank: 7.9043213e-05
Overall Rank: 2,918 | 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,645	Camel: Managing Data for Efficient Stream Learning	2022	SIGMOD	8.3768838e-05
4,969	Relative Error Streaming Quantiles	2021	PODS	5.790405e-05
7,340	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	4.7526052e-05
7,450	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	4.7218383e-05
8,669	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	4.4667395e-05
8,715	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	4.4571724e-05
9,244	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3648789e-05
10,113	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	4.1905499e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1905499e-05
10,326	Index Intersection for High-Dimensional Range Queries	2026	VLDB	4.1905499e-05
10,399	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	4.1905499e-05
10,616	Approximation-First Timeseries Query At Scale	2025	VLDB	4.1905499e-05
11,252	CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space	2023	VLDB	4.1905499e-05
11,506	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.1905499e-05
11,509	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	4.1905499e-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.00044753012
324	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00027465124
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
398	Mergeable Summaries	2012	PODS	0.00024383201
903	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00015449454
1,488	Scuba: Diving into Data at Facebook	2013	VLDB	0.00011690191
2,752	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	8.1723418e-05
2,952	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8230109e-05
2,954	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	7.8218804e-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.380727e-05
4,080	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4619407e-05
8,066	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	4.5899218e-05
3,810	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.7375383e-05
5,636	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.3985928e-05
2,954	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	7.8218804e-05
4,969	Relative Error Streaming Quantiles	2021	PODS	5.790405e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1905499e-05
9,244	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3648789e-05
10,113	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	4.1905499e-05