DDSketch: A fast and fully-mergeable quantile sketch with relative-error guarantees

Charles Masson; Homin K. Lee; Jee E. Rim

REVIEW 2 major objections 4 minor 2 cited by

DDSketch: A fast and fully-mergeable quantile sketch with relative-error guarantees

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read DDSketch is a fully-mergeable quantile sketch that returns every queried quantile within a fixed relative error $\alpha$, and proves logarithmic memory for heavy-tailed data.

desk verdict DDSketch is a simple, fully mergeable relative-error quantile sketch whose central formal claim holds up; it deserves a serious referee, but two text-level errors (the missing EX shift in Corollary 8 and the Pareto size arithmetic) need fixing before one cites the details. read the letter →

arxiv 1908.10693 v1 pith:H2BP6FY5 submitted 2019-08-28 cs.DB cs.DS

Charles Masson , Jee E. Rim , Homin K. Lee This is my paper · ORCID

classification cs.DBcs.DS

keywords DDSketchquantilesketchesrelativeerrormergeabilityheavy-taileddatastreamingalgorithmsorderstatisticsdistributedmonitoring

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces DDSketch, a streaming sketch that answers quantile queries with a guaranteed relative error $\alpha$ instead of a guaranteed rank error. The distinction matters for heavily skewed data such as web-request latencies: with rank error alone, a p99 answer can be off by orders of magnitude even when the rank is nearly right. The sketch is fully mergeable, meaning several independently built sketches can be combined by adding their per-bucket counts, and the merged sketch retains the same accuracy as a single sketch over the combined data. For data drawn from distributions whose logarithm is subexponential, the paper proves that an $\alpha$-accurate sketch covering all quantiles down to $q=\Omega(1/\sqrt n)$ fits in $O((b\log(n/\delta))/\log\gamma)$ buckets with probability at least $1-\delta$, where $\gamma=(1+\alpha)/(1-\alpha)$.

What carries the argument

The central object is a fixed logarithmic binning of the positive line: buckets $B_i=(\gamma^{i-1},\gamma^i]$ indexed by $i=\lceil\log_\gamma x\rceil$, with $\gamma=(1+\alpha)/(1-\alpha)$ chosen so that any value in a bucket is within $\alpha$ relative error of the bucket's midpoint representative $2\gamma^i/(\gamma+1)$. This binning carries the whole argument: it turns a relative-error requirement into the purely combinatorial task of locating the bucket containing the $q$-th order statistic, it makes merging trivial because boundaries do not depend on the data, and it makes the bounded-space tradeoff legible through the condition $x_1\le x_q\gamma^{m-1}$, which says the highest bucket must not be more than $m-1$ steps above the queried quantile's bucket. The proof machinery around the binning consists of a Chernoff/Hoeffding tail bound on sample quantiles and a subexponential concentration bound on the sample maximum, whose combination produces the logarithmic sketch-size bound.

What would settle it

Take i.i.d. samples from a Pareto distribution with shape $a=1$, $n=10^6$, $\alpha=0.01$, and failure probabilities $\delta_1=\delta_2=e^{-10}$; Theorem 9 predicts that, with probability at least $1-2e^{-10}$, a DDSketch with $\gamma\approx1.02$ answers all quantiles $q\ge1/2$ within 1% relative error using at most 3380 buckets. Running that configuration repeatedly and finding either a relative error above 1% or a bucket count above 3380 with frequency exceeding $2e^{-10}$ would refute the paper's stated size guarantee. A complementary check of Proposition 4 is the paper's own adversarial set $\{\gamma,\gamma^2,\ldots,\gamma^{2m}\}$, where the condition $x_1\le x_q\gamma^{m-1}$ fails and low-quantile accuracy should degrade.

Watch

Extended reading notes

Core claim

The paper's central claim is that DDSketch is the first fully-mergeable quantile sketch with formal relative-error guarantees. It partitions $\mathbb R_{>0}$ into fixed buckets $(\gamma^{i-1},\gamma^i]$ with $\gamma=(1+\alpha)/(1-\alpha)$, increments the bucket containing a newly inserted value, and answers a quantile query by adding bucket counts until it reaches rank $q(n-1)$, returning the representative $2\gamma^i/(\gamma+1)$. Lemma 2 shows that representative is within $\alpha$ relative error of any value in its bucket, and Proposition 3 shows the cumulative-count walk therefore returns an $\alpha$-accurate quantile. Because the boundaries are fixed in advance, merging two sketches is exactly a bucketwise addition of counters; the bounded-memory variant collapses the lowest-index buckets when more than $m$ buckets are occupied, and Proposition 4 pins down when this is safe: quantile $q$ remains $\alpha$-accurate as long as $x_1 \le x_q \gamma^{m-1}$. Theorem 9 then turns this condition into a size bound of $$O\left(\frac{b\log(n/\delta)}{\log\gamma}\right)$$ buckets for i.i.d. samples from a distribution whose log is subexponential, with failure probability at most $\delta_1+\delta_2$.

Load-bearing premise

The bounded-size guarantee assumes the empirical tail is no fatter than a Pareto tail, so that the largest value stays within a factor $\gamma^{m-1}$ of the target quantile; against adversarial data the sketch can need one bucket per value.

Editorial extensions

If this is right

On heavy-tailed data, tail quantiles such as p99 are reported within a fixed multiple $1\pm\alpha$ of the true value; the experiments show this can be orders of magnitude more accurate than rank-error sketches on the same streams.
Sketches built on different hosts can be combined in any order and any number of times by summing bucket counters, and the result remains as accurate as a single sketch over the union of the data, up to the bounded-bucket collapse.
For Pareto and exponential tails the required number of buckets grows only logarithmically (or double-logarithmically) in the number of values, so a few thousand buckets keep p50 through p99 accurate over millions to astronomically many samples.
Merging two DDSketches costs roughly 10 microseconds for sketches of up to fifty million values in the reported Java implementation, making distributed aggregation practical at high ingest rates.
The bounded variant intentionally sacrifices the lowest quantiles when memory is tight, which is acceptable for monitoring upper-tail metrics like p99 but not for applications that need the smallest non-zero values.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's proof of Proposition 4 suggests a directly implementable monitoring rule that the authors do not state: track the current ratio $\log x_1 - \log x_q$ per sketch, and grow $m$ or flag the sketch when that ratio approaches $(m-1)\log\gamma$, telling operators when low quantiles are no longer guaranteed.
Because bucket boundaries are fixed, the same collapsing logic could be applied symmetrically to the highest buckets, yielding bounded-space sketches that protect a middle quantile range rather than only the upper tail; the paper mentions collapse direction for negatives only in passing.
A natural extension is variable accuracy per region: choose a smaller $\gamma$ for quantiles near the median and a larger $\gamma$ for extreme tails, preserving mergeability while spending buckets where they matter most; the paper does not explore this.
The subexponential-log assumption is sufficient rather than necessary; any distribution with a known bound on the log-tail's moment generating function can be plugged into Theorem 9's template to produce concrete sketch-size constants for Weibull, log-normal, or other heavy-tailed models.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know this paper for what it is: a clean, practical answer to a real gap. DDSketch is a fixed-boundary log-bucket histogram, and the authors are honest that the algorithm is simple. The contribution is showing that this simple structure gives formal relative-error guarantees, is fully mergeable by summing bucket counts, and has small size under subexponential and Pareto tails. The prior art is cited fairly: GK and KLL give rank error only, HDR Histogram has bounded range and no published guarantees, t-digest is one-way mergeable and lacks formal analysis. The claim to be the first fully-mergeable relative-error sketch with formal guarantees seems justified. The proofs in Lemma 2 and Proposition 3 are direct and correct; Theorem 9's size bound is sound. The paper also ships Java, Go, and Python implementations, and the experiments against GKArray, HDR, and Moments show expected behavior. That is real evidence, and the Datadog deployment adds credibility.

The soft spots are real but do not bring down the main result. Corollary 8 as written says the sample maximum is less than t = 2b log(n/delta2) with probability 1-delta2, but the proof bounds X(n) - EX > t, not X(n) > t. As stated the corollary is false whenever EX > 0. Theorem 9 quietly uses the corrected bound with EX + t, so the main theorem is fine, but the published statement is wrong and should not be quoted as a black box. Second, the Pareto size example in Section 3.3 does not reproduce. Plugging delta1 = delta2 = e^-10, alpha = 0.01, n = 10^6, a = 1 into the displayed bounds gives required size around 4900, not the claimed 3380. The expression 51 a^-1 (4 log n + 11) + 1 does not follow from the displayed inequalities; the constant likely should be 41, not 11. Again, this is an illustrative arithmetic slip, not a flaw in the asymptotic bound.

One larger caveat is structural: the bounded-space guarantee relies on Proposition 4's condition x1 <= xq gamma^(m-1), which the paper obtains only under i.i.d. sampling from a subexponential or Pareto distribution. The authors acknowledge distribution-free impossibility and note that in practice the empirical tail is assumed no fatter than Pareto. That is a reasonable framing, but it means the formal space bound depends on a distributional assumption that is not verifiable from the data alone. For a monitoring tool this is acceptable; for a pure theory audience it weakens the universality.

Bottom line: this is a solid paper that deserves a serious referee. The fix list is short but concrete: correct Corollary 8, fix the Pareto arithmetic, and clarify that the space bounds are distribution-dependent. The core algorithm and proofs are in good shape. I would bring it to a reading group and would cite it in my own work if I needed a mergeable relative-error sketch.

Recommendation: engage with the paper. It is worth the referee time, and with those two text errors corrected it would be a clean accept.

Referee Report

2 major / 4 minor

Summary. The paper proposes DDSketch, a fully mergeable quantile sketch with relative-error guarantees. Values are assigned to logarithmic buckets with boundaries gamma^{i-1} < x <= gamma^i for gamma = (1+alpha)/(1-alpha), and a quantile query returns the representative value 2 gamma^i / (gamma+1) of the bucket containing the target order statistic. The sketch is mergeable by summing bucket counts, and a bounded-memory variant collapses low-index buckets when the number of buckets exceeds a limit m. The main formal claim is that for i.i.d. data from a distribution whose logarithm is subexponential, with probability at least 1-delta1-delta2, DDSketch is an alpha-accurate (q,1)-sketch with size O((b log(n/delta)) / log gamma), provided q = Omega(1/sqrt(n)). A separate calculation is given for Pareto tails. The paper also reports extensive experiments on synthetic and real data, comparing DDSketch with GKArray, HDR Histogram, and the Moments sketch.

Significance. If the formal results are correct, DDSketch is a genuinely useful contribution: it is the first relative-error quantile sketch with formal guarantees that is fully mergeable, and the bucket design is simple enough to be fast in practice. The core accuracy argument in Lemma 2 and Proposition 3 is clean and does not rely on fitted constants or hidden assumptions. The distribution-dependent size analysis is a reasonable way to make the bounded-space claim precise, and the paper correctly acknowledges that distribution-free results are impossible. The experimental evaluation covers multiple implementations and real workloads, and the authors have released code. The main weaknesses are localized formal errors in Section 3: a false statement of the sample-maximum bound and an inconsistent Pareto size calculation. These do not invalidate the algorithmic idea or the corrected version of Theorem 9, but they must be fixed before the paper can be cited as providing a fully verified guarantee.

major comments (2)

[Section 3.2, Corollary 8] The statement of Corollary 8 is false as written. Theorem 7 bounds the tail of X - EX, so the proof establishes only Pr[X(n) - EX > t] <= delta2, i.e., X(n) < EX + 2b log(n/delta2), not X(n) < 2b log(n/delta2). For nonnegative subexponential data, EX > 0 and the difference can be arbitrarily large. Theorem 9 silently uses the corrected bound with the EX term, so the main theorem survives, but the published corollary cannot be cited as a black box and must be restated and proved correctly.
[Section 3.3, Pareto example] The claimed sketch size of 3380 for Pareto data is inconsistent with the displayed bounds. With delta1 = delta2 = e^{-10}, a = 1, and n = 10^6, the displayed bound gives log(X(n)) < 4 log(n/delta2) + 1 = 4 log n + 41 and log(X(n/2)) > -log(1/2 + sqrt(log(1/delta1)/(2n))) ~ 0.689, so the size bound is about 51(4 log n + 41) + 1, which is roughly 4900, not 3380. The expression 51a^{-1}(4 log n + 11) appears to have lost the +30 contribution from log(n/delta2) = log n + 10. This numerical example should be corrected and rechecked.

minor comments (4)

[Section 4.3] The sentence 'as we saw in Section 6' refers to the tradeoff between insertion speed and sketch size, but Section 6 is the acknowledgment; the intended reference is presumably Section 4.2 or the implementation discussion in Section 2.2.
[Section 6] The acknowledgment credits the Minor Planet Center, but none of the three datasets described in Section 4.1 appears to use Minor Planet Center data; please clarify or remove this leftover acknowledgment.
[Section 5] There is a typo in the conclusion: 'a flexible relativer error sketch' should read 'a flexible relative-error sketch.'
[Section 3.3] The phrase 'The double logarithm in our size bound from Theorem 9' is misleading in the Pareto discussion, because the final Pareto bound grows as O(log n), not as a double logarithm; please rephrase to avoid confusion about the asymptotic order.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithmic guarantees follow directly from the bucket definition and standard concentration arguments, with no fitted values or self-citation load-bearing steps.

full rationale

The paper's derivation chain is self-contained. It defines gamma=(1+alpha)/(1-alpha) buckets and proves in Lemma 2 that the bucket midpoint is an alpha-accurate relative-error estimator for every value in the bucket; this is a direct property of the bucket geometry, not an assumed conclusion. Proposition 3 shows the quantile query returns the bucket containing x_q, again by the definition of ranks and bucket boundaries. Proposition 4 derives the sufficient condition x1 <= xq gamma^{m-1} for the bounded version from the collapse rule, so the bounded-sketch guarantee is not circular. Section 3 then supplies distribution-dependent size bounds: Lemma 5 uses a Hoeffding-style argument to lower-bound the q-th sample quantile, Theorem 7 is a standard subexponential concentration inequality, and Theorem 9 combines these with the bucket-span inequality to bound sketch size. The inputs are explicit distribution parameters (sigma, b for subexponential; a for Pareto) and sample size n; no fitted constant is later renamed as a prediction. Mergeability is established by the fact that bucket counts are added and the same collapse rule is applied, which is the algorithm's definition rather than a circular invocation. Experimental comparisons use independent implementations of GKArray, HDR Histogram, and Moments sketch, plus Datadog and UCI datasets; the authors' own code repositories are implementation artifacts, not evidence for the theorems. The paper's explicit caveats that distribution-free results are impossible and that practical use relies on empirical tails no fatter than Pareto are assumptions, not smuggled outputs. The printed proof of Corollary 8 omits the EX shift in its statement and the Section 3.3 Pareto arithmetic does not reproduce the stated 3380; these are correctness and reproducibility defects, not circularity, because Theorem 9's use of the bound includes the shift and the central derivation does not reduce to its own inputs. No circular step can be exhibited from the paper's equations.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free parameters fitted to data: alpha and m are user-specified accuracy and memory parameters, and the distribution parameters enter only as inputs to the analysis. There are no invented physical entities. The main external assumptions are standard concentration inequalities and the distributional tail assumption needed for the bounded-size result.

assumptions (4)

standard math Hoeffding/Chvatal binomial tail bound used in Lemma 5 to bound lower sample quantiles.
The proof of Lemma 5 follows Chvatal's proof of a special case of the Hoeffding bound. Standard concentration inequality, accepted without derivation.
standard math Subexponential concentration inequality (Theorem 7) cited to Buldygin and Kozachenko.
Used in Corollary 8 to bound the sample maximum of subexponential random variables. Standard textbook result, not proven in the paper.
domain assumption Data is i.i.d. from a subexponential or Pareto distribution for the bounded-size guarantee.
Section 3 explicitly assumes i.i.d. samples from distributions whose logarithms are subexponential. The paper notes this is stronger than needed in practice, but the formal size bound requires it.
domain assumption For the bounded version, the sufficient condition x1 <= xq * gamma^(m-1) is used to ensure the q-quantile bucket is not collapsed.
Proposition 4 proves this condition is sufficient, but the condition itself is an assumption about the data range and the target quantile. If it fails, lower quantile accuracy is lost.

how reviews work

0 comments

Cite this review

Pith. "Pith review of DDSketch: A fast and fully-mergeable quantile sketch with relative-error guarantees." pith.science (2026). https://pith.science/paper/H2BP6FY5

@misc{pith2026190810693,
  author       = {Pith},
  title        = {Pith review of: DDSketch: A fast and fully-mergeable quantile sketch with relative-error guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H2BP6FY5}},
  note         = {Machine review of arXiv:1908.10693}
}

read the original abstract

Summary statistics such as the mean and variance are easily maintained for large, distributed data streams, but order statistics (i.e., sample quantiles) can only be approximately summarized. There is extensive literature on maintaining quantile sketches where the emphasis has been on bounding the rank error of the sketch while using little memory. Unfortunately, rank error guarantees do not preclude arbitrarily large relative errors, and this often occurs in practice when the data is heavily skewed. Given the distributed nature of contemporary large-scale systems, another crucial property for quantile sketches is mergeablility, i.e., several combined sketches must be as accurate as a single sketch of the same data. We present the first fully-mergeable, relative-error quantile sketching algorithm with formal guarantees. The sketch is extremely fast and accurate, and is currently being used by Datadog at a wide-scale.

Figures

Figures reproduced from arXiv: 1908.10693 by the authors.

**Figure 2.** The average latency of a web endpoint over time (dot [PITH_FULL_IMAGE:figures/full_fig_p001_2.png] view at source ↗

**Figure 3.** Histograms for p0-p95 and p0-p100 of 2 million web request response times. (Bars for p93-p100 exist but are shorter than [PITH_FULL_IMAGE:figures/full_fig_p002_3.png] view at source ↗

Figures from the paper (8 more)

**Figure 4.** Figure 4: Actual quantiles vs. 0.005-rank-accurate and 0.01-relative-accurate quantiles of a data stream (20 batches of 100,000 values). from a distribution whose logarithm is subexponential with parameters (σ, b), which includes heavy-tailed distributions such as the log-norma…

**Figure 5.** Figure 5: Histograms of the pareto, span and mpcat-obs data sets. The y-axes of the pareto and span data sets are plotted on log scales due to their heavy-tailed nature. samples with probability greater than 0.99991. This grows doubleexponentially, so a sketch of size 1000 can …

**Figure 6.** Figure 6: Sketch size in memory in kB. [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]

**Figure 7.** Figure 7: Number of bins in DDSketch for the pareto data set. set is a set of span durations of the distributed traces of requests that Datadog received over a few hours. The durations are integers in units of nanoseconds, and it includes a wide range of values (from 100 to 1.9 …

**Figure 8.** Figure 8: Average time required to add a value to a sketch. [PITH_FULL_IMAGE:figures/full_fig_p008_8.png]

**Figure 9.** Figure 9: Average time required to merge two sketches as a [PITH_FULL_IMAGE:figures/full_fig_p009_9.png]

**Figure 10.** Figure 10: Relative errors of p50, p95, and p99 estimates. [PITH_FULL_IMAGE:figures/full_fig_p010_10.png]

**Figure 11.** Figure 11: Rank errors of p50, p95, and p99 estimates. [PITH_FULL_IMAGE:figures/full_fig_p011_11.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Enabling Multi-Dimensional Distributed Trace Comparison with Contrast
cs.DC 2026-07 conditional novelty 6.0 of 10

A mergeable trace-summary representation (TPO) lets operators dynamically compare arbitrary groups of traces across structural, timing, critical-path, and semantic dimensions, powering a visual and an LLM-based compar...
Approximation-First Timeseries Monitoring Query At Scale
cs.DB 2025-05 conditional novelty 5.0 of 10

PromSketch caches Exponential-Histogram sketch summaries in memory so overlapping window-aggregation rule queries can be answered approximately without rescanning raw time series.

Reference graph

Works this paper leans on

42 extracted references · 39 canonical work pages · cited by 2 Pith papers

[1]

INTRODUCTION Computing has increasingly moved to a distributed, container- ized, micro-service model. Some organizations run thousands of hosts, across several data centers, with each host running a dozen containers each, and these containers might only live for a couple hours [11, 10]. Eﬀectively being able to administer and operational- ize such a large...

arXiv
[2]

It is straightforward to insert items into this sketch as well as delete items and merge sketches

DDSKETCH We will ﬁrst describe the most basic version of our algorithm that will be able to giveα-accurateq-quantiles for any0≤q≤ 1. It is straightforward to insert items into this sketch as well as delete items and merge sketches. Then we will show how to modify the sketch so that it givesα-accurateq-quantiles forq0≤ q≤ 1 with bounded size. Section 2.2 w...

work page
[3]

Thus by Proposi- tion 4, we will focus on the necessary conditions forx1≤xqγm−1 or: log(x1)− log(xq) log(γ) + 1≤m

DISTRIBUTION BOUNDS For most practical applications, e.g., tracking the latency of web requests to a particular endpoint, one cares about constant quantiles such as those around the median such as 0.25, 0.5, 0.75, or those towards the edge such as 0.9, 0.95, 0.99, 0.999. Thus by Proposi- tion 4, we will focus on the necessary conditions forx1≤xqγm−1 or: l...

work page
[4]

Our Java implementation provides multiple ver- sions of DDSketch: buckets can be stored in a contiguous way (for fast addition) or in a sparse way (for smaller memory footprint)

EV ALUA TION We provide implementations of DDSketch in Java [12], Go [13] and Python [14]. Our Java implementation provides multiple ver- sions of DDSketch: buckets can be stored in a contiguous way (for fast addition) or in a sparse way (for smaller memory footprint). The number of buckets can grow indeﬁnitely or be bounded with a ﬁxed maximum of m bucke...

work page
[5]

To get a sense of the scale, some of our customers have endpoints that handle over 10M points per second, and DDSketch provides accurate latency quan- tiles for these endpoints

CONCLUSION Datadog’s use-case for distributed quantile sketching comes from our agent-based monitoring where we need to accurately aggregate data coming from disparate sources in our high-throughput, low- latency, distributed data processing engine. To get a sense of the scale, some of our customers have endpoints that handle over 10M points per second, a...

work page
[6]

ACKNOWLEDGMENT This research has made use of data provided by the International Astronomical Union’s Minor Planet Center

work page
[7]

Cormode, F

G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. Eﬀective computation of biased quantiles over data streams. In 21st International Conference on Data Engineering , ICDE’05, pages 20–31, New York, NY, USA, 2005. IEEE Computer Society Press. 103 104 105 106 107 10810-3 10-2 10-1 100 101 Relative Error in p50 pareto 103 104 105 106 107 10810-3 10-2 ...

work page 2005
[8]

Cormode, F

G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. Space- and time-eﬃcient deterministic algorithms for biased quantiles over data streams. InProceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’06, pages 263–272, New York, NY, USA, 2006. ACM

work page 2006

Show all 42 references

[9]

Cranor, T

C. Cranor, T. Johnson, O. Spataschek, and V. Shkapenyuk. Gigascope: a stream database for network applications. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pages 647–651. ACM, 2003

2003
[10]

Abraham, J

L. Abraham, J. Allen, O. Barykin, V. Borkar, B. Chopra, C. Gerea, D. Merl, J. Metzler, D. Reiss, S. Subramanian, J. L. Wiener, and O. Zed. Scuba: Diving into data at facebook. PVLDB, 6(11):1057–1067, 2013

2013
[11]

P. K. Agarwal, G. Cormode, Z. Huang, J. Phillips, Z. Wei, and K. Yi. Mergeable summaries. InProceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’12, pages 23–34, New York, NY, USA, 2012. ACM

2012
[12]

Beyer, C

B. Beyer, C. Jones, J. Petoﬀ, and N. R. Murphy.Site Reliability Engineering: How Google Runs Production Systems. ” O’Reilly Media, Inc.”, 2016

2016
[13]

V. V. Buldygin and U. V. Kozachenko.Metric Characterization of Random Variables and Random Processes. American Mathematical Society, Rhode Island, USA, 2000

2000
[14]

Chv ´atal

V. Chv ´atal. The tail of the hypergeometric distribution. Discrete Mathematics, 25:285–287, 1979

1979
[15]

Cormode, M

G. Cormode, M. Garofalakis, P. J. Haas, and C. Jermaine. Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends R© in Databases, 4(1-3):1–294, 2011

2011
[16]

Dean and L

J. Dean and L. A. Barroso. The tail at scale. Communications of the ACM, 56(2):74–80, 2013

2013
[17]

Dunning and O

T. Dunning and O. Ertl. Computing extremely accurate quantiles using t-digests. arXiv preprint arXiv:1902.04023, 2019

1902 arXiv
[18]

Elasticsearch reference: Percentiles aggregation

Elasticsearch. Elasticsearch reference: Percentiles aggregation. https://www.elastic.co/guide/en/ elasticsearch/reference/current/ search-aggregations-metrics-percentile-aggregation. html, 2015. Accessed: 2018-09-14

2015
[19]

8 emerging trends in container orchestration

Datadog. 8 emerging trends in container orchestration. https: //www.datadoghq.com/container-orchestration,
[20]

M. B. Greenwald and S. Khanna. Space-eﬃcient online computation of quantile summaries. In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, SIGMOD ’01, pages 58–66, New York, NY, USA, 2001. ACM

2001
[21]

8 surprising facts about real docker adoption

Datadog. 8 surprising facts about real docker adoption. https://www.datadoghq.com/docker-adoption/,
[22]

Accessed: 2018-12-12

2018
[23]

https://github.com/DataDog/sketches-java, 2019

Datadog. https://github.com/DataDog/sketches-java, 2019

2019
[24]

https://github.com/DataDog/sketches-go, 2019

Datadog. https://github.com/DataDog/sketches-go, 2019

2019
[25]

https://github.com/DataDog/sketches-py, 2019

Datadog. https://github.com/DataDog/sketches-py, 2019

2019
[26]

S. DAWN. Moments sketch. https: //github.com/stanford-futuredata/momentsketch,
[27]

Unfortunately, for data sets with heavy tails, rank-error guaran- tees can return values with large relative errors

and [21] for excellent surveys on much of this work as well as additional motivation for sketching quantiles). Unfortunately, for data sets with heavy tails, rank-error guaran- tees can return values with large relative errors. Consider again the histogram of 2M request respon...
[28]

Accessed: 2019-05-29

2019
[29]

The best known rank-error quantile sketch is that of Greenwald and Khanna [20] whose deterministic sketch (GK) providesϵ rank accuracy usingO((1/ϵ) log(nϵ)) space

demonstrated the ﬁrst quantile sketching algorithm with for- mal guarantees. The best known rank-error quantile sketch is that of Greenwald and Khanna [20] whose deterministic sketch (GK) providesϵ rank accuracy usingO((1/ϵ) log(nϵ)) space. In addition to accuracy and size, a ...
[30]

R. R. Sambasivan, R. Fonseca, I. Shafer, and G. R. Ganger. So, you want to trace your distributed system? key design insights from years of practical experience. Technical Report CMU-PDL-14-102, Carnegie Mellon University, 2014

2014
[31]

E. Gan, J. Ding, K. S. Tai, V. Sharan, and P. Bailis. Moment-based quantile sketches for eﬃcient high cardinality aggregation queries. PVLDB, 11(11):1647–1660, 2018

2018
[33]

M. B. Greenwald and S. Khanna. Quantiles and equidepth histograms over streams. In M. Garofalakis, J. Gehrke, and R. Rastogi, editors, Data Stream Management, pages 45–86. Springer, New York, NY, USA, 2016

2016
[34]

S. Guha, N. Koudas, and K. Shim. Approximation and streaming algorithms for histogram construction problems. ACM Transactions on Database Systems (TODS), 31(1):396–438, 2006. 103 104 105 106 107 10810-5 10-4 10-3 10-2 10-1 100 Rank Error in p50 pareto 103 104 105 106 107 10810...

2006
[35]

S. Guha, K. Shim, and J. Woo. Rehist: Relative error histogram construction algorithms. In Proceedings of the 30th International Conference on Very Large Data Bases , VLDB ’04, pages 300–311. VLDB Endowment, 2004

2004
[36]

H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In Proceedings of the 24rd International Conference on Very Large Data Bases, VLDB ’98, pages 275–286, 1998

1998
[37]

Karnin, K

Z. Karnin, K. Lang, and E. Liberty. Optimal quantile approximation in streams. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS) , FOCS ’16, pages 71–78, New York, NY, USA, 2016. IEEE Computer Society Press

2016
[38]

M. Lichman. Uci machine learning repository. https: //archive.ics.uci.edu/ml/datasets/individual+ household+electric+power+consumption, 2013

2013
[39]

G. Luo, L. Wang, K. Yi, and G. Cormode. Quantiles over data streams: experimental comparisons, new analyses, and further improvements. PVLDB, 25(4):449–472, 2016

2016
[40]

Madden, M

S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. The design of an acquisitional query processor for sensor networks. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data , pages 491–502. ACM, 2003

2003
[41]

J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12(3):315–323, 1980

1980
[43]

G. Tene. Hdrhistogram: A high dynamic range (hdr) histogram. http://hdrhistogram.org/, 2012. Accessed: 2018-09-15

2012
[2048]

It is also worth noting that the actual sketch size required for the Pareto distribution is much smaller than the upper bounds we calculated in Section 3.3. 103 104 105 106 107 108 N Values 0 20 40 60 160 180 200 220 DDSketch DDSketch (fast) HDRHistogram GKArray MomentSketch T...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

INTRODUCTION Computing has increasingly moved to a distributed, container- ized, micro-service model. Some organizations run thousands of hosts, across several data centers, with each host running a dozen containers each, and these containers might only live for a couple hours [11, 10]. Eﬀectively being able to administer and operational- ize such a large...

arXiv

[2] [2]

It is straightforward to insert items into this sketch as well as delete items and merge sketches

DDSKETCH We will ﬁrst describe the most basic version of our algorithm that will be able to giveα-accurateq-quantiles for any0≤q≤ 1. It is straightforward to insert items into this sketch as well as delete items and merge sketches. Then we will show how to modify the sketch so that it givesα-accurateq-quantiles forq0≤ q≤ 1 with bounded size. Section 2.2 w...

work page

[3] [3]

Thus by Proposi- tion 4, we will focus on the necessary conditions forx1≤xqγm−1 or: log(x1)− log(xq) log(γ) + 1≤m

DISTRIBUTION BOUNDS For most practical applications, e.g., tracking the latency of web requests to a particular endpoint, one cares about constant quantiles such as those around the median such as 0.25, 0.5, 0.75, or those towards the edge such as 0.9, 0.95, 0.99, 0.999. Thus by Proposi- tion 4, we will focus on the necessary conditions forx1≤xqγm−1 or: l...

work page

[4] [4]

Our Java implementation provides multiple ver- sions of DDSketch: buckets can be stored in a contiguous way (for fast addition) or in a sparse way (for smaller memory footprint)

EV ALUA TION We provide implementations of DDSketch in Java [12], Go [13] and Python [14]. Our Java implementation provides multiple ver- sions of DDSketch: buckets can be stored in a contiguous way (for fast addition) or in a sparse way (for smaller memory footprint). The number of buckets can grow indeﬁnitely or be bounded with a ﬁxed maximum of m bucke...

work page

[5] [5]

To get a sense of the scale, some of our customers have endpoints that handle over 10M points per second, and DDSketch provides accurate latency quan- tiles for these endpoints

CONCLUSION Datadog’s use-case for distributed quantile sketching comes from our agent-based monitoring where we need to accurately aggregate data coming from disparate sources in our high-throughput, low- latency, distributed data processing engine. To get a sense of the scale, some of our customers have endpoints that handle over 10M points per second, a...

work page

[6] [6]

ACKNOWLEDGMENT This research has made use of data provided by the International Astronomical Union’s Minor Planet Center

work page

[7] [7]

Cormode, F

G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. Eﬀective computation of biased quantiles over data streams. In 21st International Conference on Data Engineering , ICDE’05, pages 20–31, New York, NY, USA, 2005. IEEE Computer Society Press. 103 104 105 106 107 10810-3 10-2 10-1 100 101 Relative Error in p50 pareto 103 104 105 106 107 10810-3 10-2 ...

work page 2005

[8] [8]

Cormode, F

G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. Space- and time-eﬃcient deterministic algorithms for biased quantiles over data streams. InProceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’06, pages 263–272, New York, NY, USA, 2006. ACM

work page 2006