Plan-based Complex Event Detection across Distributed Sources
Here is an interesting 2008 paper, Plan-based Complex Event Detection across Distributed Sources.
Abstract
Complex Event Detection (CED) is emerging as a key capability for many monitoring applications such as intrusion detection, sensorbased activity & phenomena tracking, and network monitoring. Existing CED solutions commonly assume centralized availability and processing of all relevant events, and thus incur significant overhead in distributed settings. In this paper, we present and evaluate communication efficient techniques that can efficiently perform CED across distributed event sources.
Our techniques are plan-based: we generate multi-step event acquisition and processing plans that leverage temporal relationships among events and event occurrence statistics to minimize event transmission costs, while meeting application-specific latency expectations. We present an optimal but exponential-time dynamic programming algorithm and two polynomial-time heuristic algorithms, as well as their extensions for detecting multiple complex events with common sub-expressions. We characterize the behavior and performance of our solutions via extensive experimentation on synthetic and real-world data sets using our prototype implementation.
Filed under: Advanced Event Processing, CEP News and Events, CEP Tutorials, Complex Event Processing
Thanks for sharing the link. One paragraph in the paper was interesting to me.
6.4 Effects of Event Sharing
To quantify the potential benefits of leveraging shared subevents across multiple complex events, we generated two complex events with a common subevent tree and compared the performance with and without shared optimization. Each complex event has 3 and operators,
one of which is shared. There is a total of 6 primitive events,
2 of which are common to both complex events. In the experiment, we varied the frequency of the complex event that corresponds to the shared subtree. In Figure 5(e), we see that when the frequency of the shared part is low, leveraging sharing does not lead to a noteworthy improvement since the shared part is chosen to be monitored earlier in both cases anyway. When the frequency of the shared part is the same with or slightly higher than the non-shared parts, the latter are monitored earlier without sharing optimization. In this case, shared optimization reduces the cost by monitoring the shared part first. Finally, when the shared part has very high frequency, non-shared parts are monitored first in both cases.
sharing events is similar to sharing patterns. sharing common patterns is an age old pattern matching issue. I’m surprise to see the authors of the paper never mention RETE or existing prior art from AI field. It’s a shame they ignored existing research that would have been beneficial.
the CED algorithm described in the paper is interesting, but it looks similar to other papers I’ve seen in the past.