Maintaining significant stream statistics over sliding windows

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/ε log 2 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 Ω(log 2 n) bits in the worst case.