Practical t-digest Applications #bbuzz
summary
Algorithm computes approximate quantiles with constant relative accuracy (very tight at tails, looser near median) by merging sorted points into centroids with a bounded size so digest memory stays finite regardless of data volume. Implementations appear in ElasticSearch, Apache Mahout, streamlib and Maven Central; a tree-based implementation by Adrian Grant is fastest. Typical cost is ~100 ns per point with few megabytes per node, exact quantiles queryable online and useful for 99.999th‑percentile queries.
AI-written summary · about
chapters (8)
- 0:00Introduction and speaker background
- 1:09Why online algorithms matter
- 3:18Quantiles and their importance
- 5:25Variable accuracy in quantiles
- 7:14How T-digest works
- 11:05Algorithm implementation details
- 12:31Integration and use cases
- 13:35Anomaly detection applications
related talks
37mApproaches to online quantile estimation
39mReal Time Datamining and Aggregation at Scale
39mAcceptably Inaccurate: Probabilistic Data Structures #bbuzz
01h 09mVector Search: Ask Me Anything!
34mBig Data, Small Code ... #bbuzz
12mMilliSort and MilliQuery: Large-Scale Data-Intensive Computing in Milliseconds
27mModelling the extreme using Quantile Regression
34mPrediction intervals