Frugal Streaming for Estimating Quantiles:One (or two) memory suffices

Qiang Ma, S. Muthukrishnan, Mark Sandler

Modern applications require processing streams of data for estimating statistical quantities such as quantiles with small amount of memory. In many such applications, in fact, one…