Event stream processing with out-of-order data arrival

Ming Li, Mo Liu, Luping Ding, Elke A. Rundensteiner, Murali Mani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

37 Scopus citations

Abstract

Complex event processing has become increasingly important in modern applications, ranging from supply chain management for RFID tracking to real-time intrusion detection. The goal is to extract patterns from such event streams in order to make informed decisions in real-time. However, networking latencies and even machine failure may cause events to arrive out-of-order at the event stream processing engine. In this work, we address the problem of processing event pattern queries specified over event streams that may contain out-of-order data. First, we analyze the problems state-of-the-art event stream processing technology would experience when faced with out-of-order data arrival. We then propose a new solution of physical implementation strategies for the core stream algebra operators such as sequence scan and pattern construction, including stack-based data structures and associated purge algorithms. Optimizations for sequence scan and construction as well as state purging to minimize CPU cost and memory consumption are also introduced. Lastly, we conduct an experimental study demonstrating the effectiveness of our approach.

Original languageEnglish (US)
Title of host publication27th International Conference on Distributed Computing Systems Workshops, ICDCSW'07
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages67-74
Number of pages8
ISBN (Print)0769528384, 9780769528380
DOIs
StatePublished - 2007
Externally publishedYes
Event27th International Conference on Distributed Computing Systems Workshops, ICDCSW'07 - Toronto, ON, Canada
Duration: Jun 22 2007Jun 29 2007

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Conference

Conference27th International Conference on Distributed Computing Systems Workshops, ICDCSW'07
Country/TerritoryCanada
CityToronto, ON
Period6/22/076/29/07

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Event stream processing with out-of-order data arrival'. Together they form a unique fingerprint.

Cite this