Optimal Quantile Approximation in Streams
Optimal Quantile Approximation in Streams
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, <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">⋯</sub> ,xn and allows one to approximate the rank of any query item up to additive …