Stanford InfoLab Publication Server

Approximate Counts and Quantiles over Sliding Windows

Arasu, Arvind and Manku, Gurmeet (2003) Approximate Counts and Quantiles over Sliding Windows. Technical Report. Stanford.




We consider the problem of maintaining approximate counts and quantiles over fixed- and variable-size sliding windows in limited space. For quantiles, we present deterministic algorithms whose space requirements are O(1/e log(1/e)log N) and O(1/e log(1/e) log(eN) log N) in the worst-case for fixed- and variable-size windows, respectively, where N denotes the current number of elements in the window and e, the relative error. Our space bounds improve upon the previous best bounds of O(1/e^2 polylog (1/e,N)). For counts, we present both deterministic and randomized algorithms. The deterministic algorithms require O(1/e log^2 (1/e)) and O(1/e log^2 (1/e) log eN) for worst-case space for fixed- and variable-size windows, respectively, while the randomized ones require O(1/e log (1/(e d))) and O(1/e log(1/(ed)) log eN) worst-case space, where d denotes the probability of failure. We believe no previous work on space-efficient approximate counts for sliding windows exists.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:Data Streams, Sliding Windows, Quantiles, Counts, Approximation, Limited Space
Related URLs:Project Homepage
ID Code:624
Deposited By:Import Account
Deposited On:08 Dec 2003 16:00
Last Modified:24 Dec 2008 08:23

Download statistics

Repository Staff Only: item control page