Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors

Elena Gribelyuk, Pachara Sawettamalya, Hongxun Wu +1

Computing the approximate quantiles or ranks of a stream is a fundamental task in data monitoring. Given a stream of elements $x_1,x_2,\dots ,x_n$ and a query $x$, a relative-err…