Relative Error Streaming Quantiles
Approximating distributions and quantiles is a fundamental task in data analysis. We consider streaming algorithms that make just one pass over a massive dataset and must use a small amount of memory, polylogarithmic in the input size. The problem of approximating the median and other quantiles with an additive error is sufficiently well-understood, however, the case of the stronger relative error is still open. Such an error guarantee provides more accurate estimates for extreme quantile queries (such as the 99.5th percentile), thus helping to understand the tails of the distribution.
We describe a new streaming algorithm providing the relative error guarantee with a nearly optimal trade-off between space usage and accuracy. Joint work with Graham Cormode, Zohar Karnin, Edo Liberty, and Justin Thaler.