Continuous Monitoring of Distributed Data Streams over a Time‐Based Sliding Window

Continuous Monitoring of Distributed Data Streams over a Time‐Based Sliding Window

0.00 Avg rating0 Votes
Article ID: iaor2012426
Volume: 62
Issue: 3
Start Page Number: 1088
End Page Number: 1111
Publication Date: Apr 2012
Journal: Algorithmica
Authors: , , ,
Keywords: networks: flow, combinatorial optimization, communications
Abstract:

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 ε log ε N k ) equ1 bits for basic counting, O ( k ε log N k ) equ2 words for frequent items and O ( k ε 2 log N k ) equ3 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 ϵ <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.

Reviews

Required fields are marked *. Your email address will not be published.