Complex event processing over out - of - order event streams

Abstract

Complex Event Processing (CEP) enables real-time inferring of events and patterns of interest. Aggregation on a time window of events and pattern matching are two of the core functionalities of CEP. Accuracy of these CEP operations depend on the order of the events received at the CEP engine. However, due to network delay, environmental differences in event producing sources, and distributed CEP systems, event arrival order at the CEP engine maybe different from the order of event generation at the source. Such out-of-order events may lead to incorrect output events by the CEP engine. We propose a novel solution to handle the out-of-order events in three steps, namely (a) ordering events from the same source, (b) ordering events from multiple sources, and (c) optimizing query operator to further improve the accuracy after applying former steps. Sequence numbers are used to order events from a single source, whereas estimated time drift of each event source is used to order event from multiple event sources. Finally, the query operators are optimized to reduce the error of remaining out-of-order events. Performance of the proposed solution is evaluated using the DEBS 2013 Football dataset. The performance analysis shows that the proposed techniques result in 9600% to 21300% and 1200% to 2500% reduction in latency compared to MP-K-Slack and AQ-K-Slack techniques, respectively. Further, the proposed solution was able to order the events with 99.97% - 99.99% accuracy. While it is comparatively lower than MP-K-Slack which had an accuracy of 99.99% and better than AQ-K-Slack which had an accuracy of 99.02%. Therefore, the proposed solution provides a good balance between latency and accuracy. The additional optimizations carried out in aggregator and pattern matching operators further increased the accuracy of the results by 50% compared to the final results obtained without these query optimizations.