Efficient Event Stream Processing: Handling Ambiguous Events and Patterns with Negation

摘要

Event stream processing, where we detect patterns on incoming event streams, has tremendous value in early determination of critical conditions, enabling on-time response for several important applications. Event stream processing has two significant differences from prior work on XML/relational stream processing: ambiguous events, where an event can match multiple query symbols/conditions in the pattern; and negation, used in event stream processing patterns to specify the non-occurrence of a pattern. In this paper, we develop a formal framework to define the semantics of event patterns, including negation, and describe how to construct a deterministic finite state automaton even in the presence of ambiguous events. Using our framework, we can construct an efficient deterministic finite state automaton for detecting patterns with any complex nesting of negations over an event stream which may have ambiguous events. Our preliminary experimental studies illustrate the significant benefits of our approach to existing approaches.