Continuous Monitoring of Distributed Data Streams over a Time-Based Sliding Window
In this paper we extend the study of algorithms for monitoring distributed data streams from whole data streams to a time-based sliding window. The concern is how to minimize the communication between individual streams and the root, while allowing the root, at any time, to report the global statistics of all streams within a given error bound. This paper presents communication-efficient algorithms for three classical statistics, namely, basic counting, frequent items and quantiles. The worst-case communication cost over a window is O(k/epsilon log epsilon N/k) bits for basic counting, O(k/epsilon log N/k) words for frequent items and O(k epsilon 2log N/k) words for quantiles, where k is the number of distributed data streams, N is the total number of items in the streams that arrive or expire in the window, and epsilon < 1 is the given error bound. The performance of our algorithms matches and nearly matches the corresponding lower bounds. We also show how to generalize these results to streams with out-of-order data.
distributed data streams algorithms communication frequent items quantiles