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

arXiv: https://arxiv.org/abs/1908.10693 · HTML: https://mlsanity.com/paper/1908.10693/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Aug 2019.

## Built on by (most cited first, 8 of 8)

- [LeJEPA: Provable and Scalable Self-Supervised Learning Without the Heuristics](https://mlsanity.com/paper/2511.08544/) (2025)
- [Federated Conformal Predictors for Distributed Uncertainty Quantification](https://mlsanity.com/paper/2305.17564/) (2023)
- [Federated XGBoost on Sample-Wise Non-IID Data](https://mlsanity.com/paper/2209.01340/) (2022)
- [FedCF: Fair Federated Conformal Prediction](https://mlsanity.com/paper/2509.22907/) (2025)
- [Inshrinkerator: Compressing Deep Learning Training Checkpoints via Dynamic Quantization](https://mlsanity.com/paper/2306.11800/) (2023)
- [PAPAYA Federated Analytics Stack: Engineering Privacy, Scalability and Practicality](https://mlsanity.com/paper/2412.02340/) (2024)
- [FedSCS-XGB -- Federated Server-centric surrogate XGBoost for continual health monitoring](https://mlsanity.com/paper/2603.06224/) (2026)
- [Small but Mighty: Test Suites as Improvement Signals for Self-Evolving Agents](https://mlsanity.com/paper/2610.15964/) (2026)

## Abstract (arXiv)

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.