Design of a sliding window over distributed and asynchronous event streams

Yiling Yang, Yu Huang, Jiannong Cao, Xiaoxing Ma, Jian Lu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

The event stream model of computation has a wide range of applications, e.g., computer system monitoring, physical environment sensing/surveillance, and stock trade monitoring. Sliding windows are widely used to facilitate effective event stream processing. However, it is greatly challenged when the event sources are distributed and asynchronous. One important technique to cope with the asynchrony is to utilize that the meaningful snapshots of an asynchronous computation form a distributive lattice. It thus becomes the central challenge whether this lattice structure still preserves and how to maintain it at runtime, when we restrict our attention to events within sliding windows. To address this challenge, we first prove that the snapshots of the asynchronous event streams within the sliding windows form a convex distributive lattice (denoted by Lat-Win). This enables us to easily integrate existing predicate specification and detection techniques, to express and monitor properties of our concern over asynchronous event streams. Then we propose an algorithm to maintain Lat-Win at runtime. The proposed scheme is evaluated in a context-aware smart office scenario, where activities of the user can be recognized by monitoring multiple streams of sensed events. The Lat-Win algorithm is implemented on the open-source context-aware middleware we developed. The evaluation results first show the advantage of adopting sliding windows over asynchronous event streams. Then they show the performance of detecting specified predicates within Lat-Win, with dynamic changes in the computing environment.
Original languageEnglish
Article number6600682
Pages (from-to)2551-2560
Number of pages10
JournalIEEE Transactions on Parallel and Distributed Systems
Volume25
Issue number10
DOIs
Publication statusPublished - 1 Oct 2014

Keywords

  • asynchronous event streams
  • lattice of snapshots
  • predicate detection
  • Sliding window

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this