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||http://infolab.stanford.edu/stream/|
|Deposited By:||Import Account|
|Deposited On:||08 Dec 2003 16:00|
|Last Modified:||24 Dec 2008 08:23|
Repository Staff Only: item control page