DDSketch
DDSketch is a mergeable quantile sketch that uses indexed value bins to control relative-value error, subject to its mapping and storage limits.
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
- Masson, Rim and Lee. DDSketch. PVLDB 12(12), 2195-2205, 2019; sections 1-2. DOI 10.14778/3352063.3352135.
- DataDog sketches-java, commit 0f403e84572be0c38e5a3e955986c4f436404204: DDSketch accept, mergeWith and getValueAtQuantile.
- DataDog sketches-java, commit 0f403e84572be0c38e5a3e955986c4f436404204: DDSketches mapping and bounded/unbounded store contracts.
Sources & caveats
- Source review of the 2019 paper and Java implementation pinned to 0f403e84572be0c38e5a3e955986c4f436404204; no DDSketch execution or performance benchmark.