Probabilistic Event Stream Processing with Lineage
Zhitao Shen, Hiroyuki Kitagawa · 2008
Many sensor network applications such as the monitoring of video camera streams or the management of RFID data streams require the ability to detect composite events over high-volume data streams. Sensor data inputs from the physical world are usually noisy, incomplete and unreliable. Thus they are usually expressed with probability. To manage this kind of data, probabilistic event stream processing systems are a natural consequence. In this paper, we propose a query language to support probabilistic queries for composite event stream matching. The language allows users to express Kleene closure patterns for complex event detection in the physical world. We also propose a working framework for query processing over probabilistic event streams. Our method first detects sequence patterns over probabilistic data streams using AIG, a new data structure, which handles record sets of active states with an NFA-based approach. Our method then computes the probability of each detected sequence pattern on their lineage. With the benefit of lineage, the probability of an output event can be directly calculated without considering the query plan. We conduct a performance evaluation of our method comparing it with a naive method. Results clearly confirm the effectiveness of our approach.