Computing Extremely Accurate Quantiles Using t-Digests

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.

22 pages, 10 figures

Cited by in corpus (11)

• Relative Error Streaming Quantiles
• A Survey of Approximate Quantile Computation on Large-scale Data (Technical Report)
• Continual Learning in Practice
• KS(conf ): A Light-Weight Test if a ConvNet Operates Outside of Its Specifications
• Asymptotic Singular Value Distribution of Linear Convolutional Layers
• 8-bit Optimizers via Block-wise Quantization
• Conservation of the $t$-digest Scale Invariant
• The Size of a $t$-Digest
• Histogram Specification by Assignment of Optimal Unique Values
• Asymmetric scale functions for $t$-digests
• Storyboard: Optimizing Precomputed Summaries for Aggregation