Computing Extremely Accurate Quantiles Using t-Digests

By Ted Dunning, Otmar Ertl. 2019

85 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Ocean Engineering, Numerical Methods & Scientific Computing, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Ocean Engineering

In Numerical Methods & Scientific Computing

In Algorithms & Complexity

Citations in the corpus

8-bit Optimizers via Block-wise Quantization (2021, methodology): “For estimating 256 quantiles on a large stream of numbers, our algorithm takes on average 0.064 ns to process one element in the stream, whereas the fastest general algorithms take 300 ns (Govindaraju et al., 2005) and 5 ns (Dunning and Ertl, 2019).”
Continual Learning in Practice (2019, positive): “For rank-based statistics, such as quantiles and trimmed means, a new data structure “t-digest” for accurate on-line accumulation has been proposed [20].”
Automatic Model Monitoring for Data Streams (2019, methodology): “, Q-digest or, more recently, the T-digest algorithm [6] – see also the review by Luo et al.”