Computing Extremely Accurate Quantiles Using t-Digests

Ted Dunning, Otmar Ertl
2/11/2019
stat.COcs.DS

Official code: tdunning/t-digest (2,175 stars, Apache-2.0, last commit 2025-02-17).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

tdunning/t-digestOfficial100%
Apache-2.0

A new data structure for accurate on-line accumulation of rank-based statistics such as quantiles and trimmed means

2,175233R, JavaNov 19, 20131 years agoApache-2.0
accuracyonline-algorithmsquantilet-digest

Similar Papers

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

81% match3 repos1872019

Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees

79% match2023

UDDSketch: Accurate Tracking of Quantiles in Data Streams

79% match1 repo132020

Low-Rank Tucker Approximation of a Tensor From Streaming Data

77% match1 repo72019

Sequential estimation of quantiles with applications to A/B-testing and best-arm identification

77% match2 repos872019

Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries

75% match1 repo202018

Cite this paper

@article{dunning2019computing,
  title  = {Computing Extremely Accurate Quantiles Using t-Digests},
  author = {Ted Dunning and Otmar Ertl},
  year   = {2019},
  eprint = {1902.04023},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1902.04023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1902.04023.svg)](https://codeofpaper.com/paper/1902.04023)

Discussion