Brent Spell on Computing Extremely Accurate Quantiles Using t-Digests

Collecting real-time metrics like request latency is a critical part of production support. While it is easy to aggregate summary statistics like count, mean, and range, they are often a poor representation of actual service performance. This paper [1] describes a data structure that efficiently and accurately represents a histogram, which can be used to monitor and alert on quantile metrics (median, 99th percentile, etc.) in real time and constant space.

Brent Spell is a programmer at OpenTable in Chattanooga, where he works on infrastructure for distributed systems and machine learning applications for restaurants.

[1]: Computing Extremely Accurate Quantiles Using t-Digests (https://github.com/tdunning/t-digest/blob/master/docs/t-digest-paper/histo.pdf)