Distributed Streams Algorithms for Sliding Windows

摘要

This paper presents algorithms for estimating aggregate functions over a "sliding window" of the N most recent data items in one or more streams. Our results include: 1. For a single stream, we present the first ε-approxima-tion scheme for the number of 1's in a sliding window that is optimal in both worst case time and space. We also present the first ε-approximation scheme for the sum of integers in [0..R] in a sliding window that is optimal in both worst case time and space (assuming R is at most polynomial in N). Both algorithms axe deterministic and use only logarithmic memory words. 2. In contrast, we show that any deterministic algorithm that estimates, to within a small constant relative error, the number of 1's (or the sum of integers) in a sliding window over the union of distributed streams requires Ω(N) space. 3. We present the first randomized (ε, δ)-approximation scheme for the number of 1's in a sliding window over the union of distributed streams that uses only logarithmic memory words. We also present the first (ε, δ)-approximation scheme for the number of distinct values in a sliding window over distributed streams that uses only logarithmic memory words. Our results are obtained using a novel family of synopsis data structures which we call waves.