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 rst -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 rst -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 are 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