| Available via | http://dbpubs.stanford.edu/pub/2003-72 |
|
Submitted on |
9th of December 2003 |
|
Author |
Arasu, Arvind; Manku, Gurmeet |
|
Title |
Approximate Counts and Quantiles over Sliding Windows |
|
Date of publication |
9th of December 2003 |
|
Published in |
Technical Report |
|
Citation |
Arasu, Arvind; Manku, Gurmeet. Approximate Counts and Quantiles over Sliding Windows, Technical Report |
|
Number of pages |
13 |
|
Language |
English |
|
Project |
STREAM |
|
Type |
Technical Report |
|
Subject group |
Miscellaneous |
|
Abstract |
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. |
|
Keywords |
Data Streams, Sliding Windows, Quantiles, Counts, Approximation, Limited Space |
| Fulltext source |
Postscript (ps, ps.gz, ps.zip)
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | siroker@db.stanford.edu
| |