## G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava.
Space- and time-efficient deterministic algorithms for biased
quantiles over data streams.
In *ACM Principles of Database Systems (PODS)*, 2006.

Skew is prevalent in data streams, and should be taken into account
by algorithms that analyze the data.
The problem of finding “biased quantiles”- that is, approximate
quantiles which must be more accurate for more extreme values -
is a framework for summarizing such skewed data on data streams.
We present the first deterministic algorithms for answering biased
quantiles queries accurately with small-sublinear in the input size-
space and time bounds in one pass.
The space bound is near-optimal, and the amortized update cost is
close to constant,
making it practical for handling high speed network data streams.
We demonstrate that not only can we prove theoretical properties of the
algorithm, but that it also uses less space than existing methods in many
practical settings, and is fast to maintain.

[ bib |
slides |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*