NEEL+: Supporting Predicates for Nested Complex Event Processing

Complex event processing (CEP) has become increasingly important in modern applications, ranging from supply chain management for RFID tracking to real-time intrusion detection. These monitoring applications must detect complex event pattern sequences in event streams. However, the state-of-art in the CEP literature such as SASE, ZStream or Cayuga either do not support the specification of nesting for pattern queries altogether or they limit the nesting of non-occurrence expressions over composite event types. A recent work by Liu et al proposed a nested complex event pattern expression language, called NEEL (Nested Complex Event Language), that supports the specification of the non-occurrence over complex expressions. However, their work did not carefully consider predicate handling in these nested queries, especially in the context of complex negation. Yet it is well-known that predicate specification is a critical component of any query language. To overcome this gap, we now design a nested complex event pattern expression language called NEEL+, as an extension of the NEEL language, specifying nested CEP queries with predicates. We rigorously define the syntax and semantics of the NEEL+ language, with particular focus on predicate scoping and predicate placement. Accordingly, we introduce a top-down execution paradigm which recursively computes a nested NEEL+ query from the outermost query to the innermost one. We integrate predicate evaluation as part of the overall query evaluation process. Moreover, we design two optimization techniques that reduce the computation costs for processing NEEL+ queries. One, the intra-query method, called predicate push-in, optimizes each individual query component of a nested query by pushing the predicate evaluation into the process of computing the query rather than evaluating predicates at the end of the computation of that particular query. Two, the inter-query method, called predicate shortcutting, optimizes inter-query predicate evaluation. That is, it evaluates the predicates that correlate different query components within a nested query by exploiting a light weight predicate short cut. The NEEL+ system caches values of the equivalence attributes from the incoming data stream. When the computation starts, the system checks the existence of the attribute value of the outer query component in the cache and the predicate acts as a shortcut to early terminate the computation. Lastly, we conduct experimental studies to evaluate the CPU processing resources of the NEEL+ System with and without optimization techniques using real-world stock trading data streams. Our results confirm that our optimization techniques when applied to NEEL+ in a rich variety of cases result in a 10 fold faster query processing performance than the NEEL+ system without optimization