ddsketch · research · also Distributed Distribution Sketch

DDSketch

DDSketch is a mergeable quantile sketch that uses indexed value bins to control relative-value error, subject to its mapping and storage limits.

Related Observatory article: Read on hesela.com

The original positive-value construction uses fixed logarithmic bins. Its unbounded form supports insertion, deletion and merging; bounded variants collapse bins and can lose the stated accuracy for affected quantiles. Uncollapsed bins still approximate values. [1]

The reviewed Java implementation requires equal index mappings when merging and adds observation counts. Its weighted accept method rejects negative counts; the paper's deletion capability is not permission to pass negative weights to this API. Its quantile selection uses q*(n-1), not the nearest-rank ceil(q*n) convention. [2]

Memory and accuracy depend on the store. An unbounded dense store grows with the covered value range; capped stores collapse extreme indexes when necessary. Keep the mapping, store policy and representable range with serialized data. [3]

A successful merge does not establish disjoint observation coverage or resolve a revised window. This is a provenance requirement inferred from additive counts, not an implementation defect.

Relations

related
Quantile sketch, Quantile, Latency histogram bin

Citations

  1. Masson, Rim and Lee. DDSketch. PVLDB 12(12), 2195-2205, 2019; sections 1-2. DOI 10.14778/3352063.3352135. (accessed 2026-11-20)
  2. DataDog sketches-java, commit 0f403e84572be0c38e5a3e955986c4f436404204: DDSketch accept, mergeWith and getValueAtQuantile. (accessed 2026-11-20)
  3. DataDog sketches-java, commit 0f403e84572be0c38e5a3e955986c4f436404204: DDSketches mapping and bounded/unbounded store contracts. (accessed 2026-11-20)
Sources & caveats
  • Source review of the 2019 paper and Java implementation pinned to 0f403e84572be0c38e5a3e955986c4f436404204; no DDSketch execution or performance benchmark.

JSON: /data/terms/ddsketch.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. DDSketch. Hesela. 2026-11-20. https://hesela.dev/terms/ddsketch/