# Computing Extremely Accurate Quantiles Using t-Digests

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2019.

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

- [8-bit Optimizers via Block-wise Quantization](https://mlsanity.com/paper/2110.02861/) (2021)
- [LeJEPA: Provable and Scalable Self-Supervised Learning Without the Heuristics](https://mlsanity.com/paper/2511.08544/) (2025)
- [Efficient Federated Conformal Prediction with Group-Conditional Guarantee](https://mlsanity.com/paper/2603.14198/) (2026)
- [Distributed Monitoring for Data Distribution Shifts in Edge-ML Fraud Detection](https://mlsanity.com/paper/2401.05219/) (2024)
- [PAPAYA Federated Analytics Stack: Engineering Privacy, Scalability and Practicality](https://mlsanity.com/paper/2412.02340/) (2024)
- [The CRITICAL Records Integrated Standardization Pipeline (CRISP): End-to-End Processing of Large-scale Multi-institutional OMOP CDM Data](https://mlsanity.com/paper/2509.08247/) (2025)
- [Correlation-Aware Feature Attribution Based Explainable AI](https://mlsanity.com/paper/2511.16482/) (2025)
- [VLA Foundry: A Unified Framework for Training Vision-Language-Action Models](https://mlsanity.com/paper/2604.19728/) (2026)
- [Distribution-Aware End-to-End Embedding for Streaming Numerical Features in Click-Through Rate Prediction](https://mlsanity.com/paper/2602.03223/) (2026)
- [Federated Measurement of Demographic Disparities from Quantile Sketches](https://mlsanity.com/paper/2602.18870/) (2026)

## Abstract (arXiv)

We present on-line algorithms for computing approximations of rank-based statistics that give high accuracy, particularly near the tails of a distribution, with very small sketches. Notably, the method allows a quantile q to be computed with an accuracy relative to max(q, 1-q) rather than absolute accuracy as with most other methods. This new algorithm is robust with respect to skewed distributions or ordered datasets and allows separately computed summaries to be combined with no loss in accuracy. An open-source Java implementation of this algorithm is available from the author. Independent implementations in Go and Python are also available.