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 >>>