Optimal quantile estimation: beyond the comparison model

Meghal Gupta, Mihir Singhal, Hongxun Wu

Estimating quantiles is one of the foundational problems of data sketching. Given $n$ elements $x_1,x_2,\dots ,x_n$ from some universe of size $U$ arriving in a data stream, a qu…