{"id":"5207737f-afee-4260-aa08-128043be8846","arxiv_id":"1908.10693","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"DDSketch gives the first fully mergeable quantile sketch whose estimates carry formal relative-error guarantees, using logarithmic buckets and bounded memory for heavy-tailed data.","lead":"DDSketch is a new compact data structure that estimates percentiles of huge, distributed data streams to within a fixed relative error, and its pieces can be combined without losing accuracy. It matters because systems like web monitoring need to track extreme tail latencies, such as p99 and p999, across many servers while using very little memory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 8 misstates the sample-maximum bound (missing the EX shift), and the Pareto size calculation in Section 3.3 does not reproduce the claimed constants.","rationale":"The central claim that DDSketch is the first fully-mergeable relative-error quantile sketch with formal guarantees is supported by the algorithm and the corrected proof structure. The bounded-space guarantee rests on Proposition 4 and the distributional assumptions in Section 3; the reader correctly identified that the guarantee is conditional and not distribution-free. My stress-test focused on the proof of Theorem 9 itself, where Corollary 8 is stated incorrectly: it claims an uncentered bound but proves a centered one. Because Theorem 9 uses the corrected centered bound (with EX added inside the logarithm), the main result can be repaired by fixing the corollary's statement. The Pareto arithmetic error further shows the paper needs a revision, but neither issue overturns the algorithm's correctness or its novelty. The reader's CONDITIONAL verdict is appropriate; my concern adds a specific proof-level correction rather than changing the verdict.","tokens_in":14423,"tokens_out":27139,"duration_ms":236802,"concrete_test":"Re-derive Corollary 8 from Theorem 7: since Theorem 7 bounds Pr[X − EX > t], the union-bound argument proves X(n) < EX + 2b log(n/δ2), not X(n) < 2b log(n/δ2). Then recompute the Pareto size claim in Section 3.3 by substituting δ1 = δ2 = e^−10, α = 0.01, n = 10^6, a = 1 into the displayed formulas; if the result is not approximately 3380, the numerical example is inconsistent with the stated bounds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main formal guarantee, Theorem 9, bounds the sketch size by (log X(n) − log X(qn))/log γ + 1 and then upper-bounds log X(n) using Corollary 8. As written, Corollary 8 asserts that the sample maximum is less than t = 2b log(n/δ2) with probability 1−δ2. Its proof, however, starts from Theorem 7, which gives Pr[X − EX > t] ≤ exp(−t/2b). The proof then bounds Pr[X(n) − EX > t], not Pr[X(n) > t]. The stated corollary is therefore false in general (e.g., whenever EX > 0). The paper silently uses the corrected bound X(n) < EX + 2b log(n/δ2) in Theorem 9, so the main theorem is not invalidated, but the published statement of Corollary 8 is wrong and cannot be cited as a black box. A second, independent text inconsistency appears in the Pareto example: substituting δ1 = δ2 = e^−10, α = 0.01, n = 10^6, and a = 1 into the displayed bounds from Section 3.3 yields a required size around 4900, not the claimed 3380. These issues do not undermine the central algorithmic contribution, but they mean the formal guarantee as presented is not fully reproducible without correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14629,"tokens_out":9373,"duration_ms":98686,"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":[{"comment":"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":"Section 3.2, Corollary 8"},{"comment":"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.","section":"Section 3.3, Pareto example"}],"minor_comments":[{"comment":"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":"Section 4.3"},{"comment":"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":"Section 6"},{"comment":"There is a typo in the conclusion: 'a flexible relativer error sketch' should read 'a flexible relative-error sketch.'","section":"Section 5"},{"comment":"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.","section":"Section 3.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is on the right track and the central algorithmic contribution is sound, but the formal section currently contains a false corollary and an incorrect numerical example. Both are fixable without changing the algorithm or the main corrected theorem. I would recommend major revision rather than rejection, with a request that the authors verify all displayed constants in Section 3.3 and state the sample-maximum bound with the EX term explicitly. The claim to be 'the first fully-mergeable relative-error quantile sketch with formal guarantees' should also be checked against recent literature, since related work on relative-error sketches has evolved since the submission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nOne 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.\n\nBottom 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.\n\nRecommendation: engage with the paper. It is worth the referee time, and with those two text errors corrected it would be a clean accept.","headline":"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.","tokens_in":15214,"tokens_out":5263,"would_cite":true,"duration_ms":49151,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["DDSketch","quantile sketches","relative error","mergeability","heavy-tailed data","streaming algorithms","order statistics","distributed monitoring"],"falsifier":"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.","tokens_in":14180,"feed_emoji":"📈","tokens_out":9407,"duration_ms":94064,"temperature":0.7,"pith_summary":"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)$.","feed_headline":"DDSketch keeps tail quantiles within 1%, even after merging","feed_subtitle":"A few thousand log-spaced buckets keep p99 accurate on skewed data spread across hosts.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes that exact quantiles require retaining all data, motivating approximate quantile sketches.","marker":"[29]"},{"why":"Supplies the deterministic GK rank-error sketch that serves as the main accuracy baseline.","marker":"[20]"},{"why":"Gives the optimal fully-mergeable rank-error sketch whose guarantee DDSketch replaces with relative error.","marker":"[25]"},{"why":"Is the prior relative-error sketch with bounded range and no formal guarantees that DDSketch extends to arbitrary range.","marker":"[31]"},{"why":"Provides the fully mergeable Moments sketch whose average-rank guarantee is contrasted with DDSketch's worst-case relative error.","marker":"[19]"},{"why":"Defines mergeability of summaries, the property DDSketch claims in full.","marker":"[2]"},{"why":"Supplies the tail bound on binomial tails used in Lemma 5 for lower sample quantiles.","marker":"[5]"},{"why":"Provides the subexponential concentration inequalities used for the sample maximum bound in Theorem 7 and Corollary 8.","marker":"[4]"}],"fun_headline_variants":["First fully-mergeable sketch with relative-error guarantees","Relative-error quantiles, mergeable without accuracy loss","DDSketch: mergeable quantile sketch with strict relative error","Tail quantiles accurate to 1% across merged sketches","First relative-error quantile sketch that is fully mergeable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["First fully-mergeable sketch with relative-error guarantees","Relative-error quantiles, mergeable without accuracy loss","DDSketch: mergeable quantile sketch with strict relative error","Tail quantiles accurate to 1% across merged sketches","First relative-error quantile sketch that is fully mergeable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00062,"raw_usage":{"total_tokens":2888,"prompt_tokens":968,"completion_tokens":1920,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":584,"completion_tokens_details":{"reasoning_tokens":1838}},"tokens_in":584,"tokens_out":1920,"duration_ms":12682,"temperature":1.0,"reasoning_tokens":1838,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:37:40.935659+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"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","cited_arxiv_id":null,"evidence_quote":"Supplies the tail bound on binomial tails used in Lemma 5 for lower sample quantiles."},{"cited_title":"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","cited_arxiv_id":null,"evidence_quote":"Establishes that exact quantiles require retaining all data, motivating approximate quantile sketches."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the deterministic GK rank-error sketch that serves as the main accuracy baseline."},{"cited_title":"https://github.com/DataDog/sketches-py, 2019","cited_arxiv_id":null,"evidence_quote":"Gives the optimal fully-mergeable rank-error sketch whose guarantee DDSketch replaces with relative error."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Is the prior relative-error sketch with bounded range and no formal guarantees that DDSketch extends to arbitrary range."},{"cited_title":"8 emerging trends in container orchestration","cited_arxiv_id":null,"evidence_quote":"Provides the fully mergeable Moments sketch whose average-rank guarantee is contrasted with DDSketch's worst-case relative error."},{"cited_title":"It is straightforward to insert items into this sketch as well as delete items and merge sketches","cited_arxiv_id":null,"evidence_quote":"Defines mergeability of summaries, the property DDSketch claims in full."},{"cited_title":"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)","cited_arxiv_id":null,"evidence_quote":"Provides the subexponential concentration inequalities used for the sample maximum bound in Theorem 7 and Corollary 8."}],"review_version":1}