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

BibTeX | DublinCore | EndNote | HTML |

| PDF 195Kb |

## 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.

Item Type: | Techreport (Technical Report) | |
---|---|---|

Uncontrolled Keywords: | Data Streams, Sliding Windows, Quantiles, Counts, Approximation, Limited Space | |

Subjects: | Miscellaneous | |

Projects: | STREAM | |

Related URLs: | Project Homepage | http://infolab.stanford.edu/stream/ |

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