Continuous monitoring of distributed data streams over a time-based sliding window

Ho Leung Chan, Tak Wah Lam, Lap Kei Lee, Hing Fung Ting

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)

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

Original languageEnglish
Pages (from-to)1088-1111
Number of pages24
JournalAlgorithmica
Volume62
Issue number3-4
DOIs
Publication statusPublished - 1 Apr 2012
Externally publishedYes

Keywords

  • Algorithms
  • Communication
  • Distributed data streams
  • Frequent items
  • Quantiles

Fingerprint

Dive into the research topics of 'Continuous monitoring of distributed data streams over a time-based sliding window'. Together they form a unique fingerprint.

Cite this