Maintaining significant stream statistics over sliding windows
Lap–Kei Lee, Hing‐Fung Ting · 2006
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 Dataretal. [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 + 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 Ω(log 2 n) bits in the worst case. Ω ( 1 1 log2 ε θ 1