Maintaining Significant stream statistics over sliding windows

L. K. Lee, H. F. Ting

Research output: Contribution to conferencePaperpeer-review

23 Citations (Scopus)

Abstract

In this paper, we introduce the Significant One Counting problem. Let ε and θ be respectively some user-specified error bound and threshold. The input of the problem is a stream of bits. We need to maintain some data structure that allows us to estimate the number of 1-bits in a sliding window of size n such that whenever there are at least θn 1-bits in the window, the relative error of the estimate is guaranteed to be at most ε. When θ = 1/n, our problem becomes the Basic Counting problem proposed by Datar et al. [ACM-SIAM Symposium on Discrete Algorithms (2002), pp. 635-644]. We prove that any data structure for the Significant One Counting problem must use at least Ω(1/ε log2 1/θ + log εθn) bits of memory. We also design a data structure for the problem that matches this memory bound and supports constant query and update time. Note that for fixed θ and ε, our data structure uses O(log n) bits of memory, while any data structure for the Basic Counting problem needs Ω(log2 n) bits in the worst case.

Original languageEnglish
Pages724-732
Number of pages9
DOIs
Publication statusPublished - 2006
Externally publishedYes
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: 22 Jan 200624 Jan 2006

Conference

ConferenceSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL
Period22/01/0624/01/06

Fingerprint

Dive into the research topics of 'Maintaining Significant stream statistics over sliding windows'. Together they form a unique fingerprint.

Cite this