HackerPapers

arXiv:1902.04023stat.CO

Computing Extremely Accurate Quantiles Using t-Digests

Ted Dunning, Otmar Ertl

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.

arXiv comments
22 pages, 10 figures
Journal reference
DOI
Subjects
stat.COComputation (Statistics) cs.DSData Structures and Algorithms

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Mar 2020 to Sep 2021. Found in 1 HN submission from Feb 2019 to Feb 2019. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. How percentile approximation works and why it's more useful than averages 1 comment

    • There are some newer data structures that take this to the next level such as T-Digest[1], which remains extremely accurate even when determining percentiles at the very tail end (like 99.999%) [1]: https://arxiv.org/pdf/1902.04023.pdf / https://github.com/tdunning/t-digest

      cyralView on HNParent context

  2. Lies, Damned Lies, and Averages: Perc50, Perc95 Explained for Programmers 1 comment

    • The Circllhist algorithm is interesting, but I get an uneasy feeling from the use of a _relative error_ measure to evaluate the performance of quantile estimation. Note that other authors don't use this measure. Dunning uses Mean Absolute Error in his latest T-digest paper…

      jmacd333View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.