Article ID: | iaor2012426 |
Volume: | 62 |
Issue: | 3 |
Start Page Number: | 1088 |
End Page Number: | 1111 |
Publication Date: | Apr 2012 |
Journal: | Algorithmica |
Authors: | Lam Tak-Wah, Chan Ho-Leung, Ting Hing-Fung, Lee Lap-Kei |
Keywords: | networks: flow, combinatorial optimization, communications |
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