Approximate Counts and Quantiles over Sliding Windows

We consider the problem of maintaining approximate counts and quantiles over a stream sliding window using limited space. We consider two types of sliding windows depending on whether the number of elements N in the window is fixed (fixed-size sliding window) or variable (variable-size sliding window). In a fixed-size sliding window, both the ends of the window slide synchronously over the stream. In a variable-size sliding window, an adversary slides the window ends independently, and therefore has the ability to vary the number of elements N in the window.

We present various deterministic and randomized algorithms for approximate counts and quantiles. All of our algorithms require space that is logarithmic in N and linear in 1/e, where is the approximation factor. For quantiles, this space requirement is an improvement over the previous best bound which is quadratic in 1/e. We believe that no previous work on space-efficient approximate counts over sliding windows exists.