View article

This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An ε approximate quantile sketch receives a stream of items x1, _⋯ ,xn and allows one to approximate the rank of any query item up to additive error ε n with probability at least 1-δ.The rank of a query x is the number of stream items such that x _i ≤ x. The minimal sketch size required for this task is trivially at least 1/ε.Felber and Ostrovsky obtain a O((1/ε)log(1/ε)) space sketch for a fixed δ.Without restrictions on the nature of the stream or the ratio between ε and n, no better upper or lower bounds were known to date. This paper obtains an O((1/ε)log log (1/δ)) space sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap between randomized and deterministic quantile sketching for which an Ω((1/ε)log(1/ε)) lower bound is …