Approaches to online quantile estimation
summary
Compares concrete streaming quantile data structures: Greenwald‑Khanna (ordered tuples with gi/delta compression), the KLL compactor hierarchy (randomized even/odd compactions, Hoeffding analysis, probabilistically optimal size and mergeable), and t-digest with asymmetric scale (centroids plus a scale function that trades left-tail accuracy for right-tail savings). Presents a measured tradeoff: for delta=100 the asymmetric t‑digest drops ~70→40 centroids keeping right‑tail error the same, and notes a new relative‑error KLL variant with provable tail guarantees at higher space.
AI-written summary · about
chapters (9)
- 0:00Introduction and context
- 1:42Defining the problem
- 6:18Theoretical limitations
- 11:20Key properties for algorithms
- 13:17Monroe-Patterson results
- 15:32Greenwald-Khanna algorithm
- 19:25KLL hierarchical sampling
- 23:42T-Digest and variations
- 34:56Q&A and closing
related talks
15mPractical t-digest Applications #bbuzz
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 10mSketching High-Dimensional Data
22mLoopDelta: Embedding Locality-aware Opportunistic Delta Compression in Inline...
01h 04mSampling Big Ideas in Sublinear Algorithms
35mSampling for Subset Selection and Applications
55mTheory of Data Streams
01h 04mNew Algorithms for Heavy Hitters in Data Streams