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 language | English |
---|---|
Pages | 724-732 |
Number of pages | 9 |
DOIs | |
Publication status | Published - 2006 |
Externally published | Yes |
Event | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: 22 Jan 2006 → 24 Jan 2006 |
Conference
Conference | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Country/Territory | United States |
City | Miami, FL |
Period | 22/01/06 → 24/01/06 |