All reports by Author Mihir Singhal:

__
TR24-065
| 6th April 2024
__

Meghal Gupta, Mihir Singhal, Hongxun Wu#### 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 quantile sketch estimates the rank of any element with additive error at most $\varepsilon n$. A low-space algorithm solving this ... more >>>