Int. J. of Communication Networks and Distributed Systems   »   2009 Vol.2, No.4

 

 

Title: Efficient probabilistic event stream processing with lineage and Kleene-plus

 

Author: Zhitao Shen, Hideyuki Kawashima, Hiroyuki Kitagawa

 

Addresses:
Graduate School of Systems and Information Engineering, University of Tsukuba, Ibaraki 305-8573, Japan.
Graduate School of Systems and Information Engineering, University of Tsukuba, Ibaraki 305-8573, Japan.
Graduate School of Systems and Information Engineering, University of Tsukuba, Ibaraki 305-8573, Japan

 

Abstract: This paper proposes a working framework and a query language to support probabilistic queries for composite event detection over probabilistic event streams. The language allows users to express Kleene closure patterns for complex event detection in the physical world. Our processing method first detects sequence patterns over probabilistic data streams using AIG, a new data structure, which handles active states with a nondeterministic finite automaton (NFA). Our method then computes the probability of each detected sequence pattern based on its lineage. Through the benefit of lineage, the probability of an output event can be directly calculated without taking into account the query plan. An optimised plan can be selected. Finally, we conducted a performance evaluation of our method and compared the results with the original and optimised query plan. The experiment clearly showed that our proposal outperforms straight-forward query plans.

 

Keywords: event stream processing; probabilistic data management; data streams; nondeterministic finite automata; lineage; Kleene-plus; probabilistic queries; composite event detection; probabilistic event streams; Kleene closure patterns; sequence patterns.

 

DOI: 10.1504/IJCNDS.2009.026554

 

Int. J. of Communication Networks and Distributed Systems, 2009 Vol.2, No.4, pp.355 - 374

 

Available online: 19 Jun 2009

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article