Approximate Counts and Quantiles over Sliding Windows

Abstract

We consider the problem of maintaining \epsilon-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 O(1/\epsilon polylog(1/\epsilon, N)) space. For quantiles, this space requirement is an improvement over the previous best bound of O(1/\epsilon^2 polylog(1/\epsilon, N)). We believe that no previous work on space-efficient approximate counts over sliding windows exists.

Back to publications
Back to previous page