Open Access Publications from the University of California

## Order statistics and variability in data streams

• Author(s): Felber, David
We introduce a new, natural parameter for data streams, the variability'' $v$, that permits us to easily extend existing algorithms for the aggregating streaming model to one in which streams are composed of insertion and deletion transactions. For this second model, our definition refines existing worst-case communication bounds from $O(n)$ to $\tilde{O}(v)$ for a host of problems. We further show that the variabilities for many streams of interest grow slowly with respect to the size of the streams.