sites.cs.ucsb.edu
Quantiles on Streams [PDF]
The problem of quantile computation, while well-solved in the classical model of computation, assumes a new and challenging character within the constraints of single-pass computation (the streaming model). Indeed, when the algorithm’s memory is limited and significantly smaller than the size of the data set S, it is not possible to compute the quantile precisely, and the best possible solution is an approximation.