Reproduce “Computing Extremely Accurate Quantiles Using t-Digests” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Ted Dunning, Otmar Ertl
A novel on-line data structure, the t-digest, estimates rank-based statistics with high relative accuracy, particularly in distribution tails, while maintaining a compact memory footprint. It achieves this by adaptively clustering real-valued samples and supporting efficient parallel aggregation through mergable independent digests.
Key insights
- Adaptive cluster sizing via specific scale functions (e.g., k₂ and k₃) is crucial for achieving constant relative error accuracy, particularly for extreme quantiles in distribution tails.
- The inherent ability to merge t-digests from disjoint datasets enables highly efficient parallel and distributed computation without significant loss of accuracy.
- Empirical analysis reveals that for larger compression parameters (δ), the dominant error scales closer to 1/√δ rather than 1/δ², informing optimal algorithm design and parameter selection.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.