PMTree: An efficient pattern matching method for event stream processing

Complex event processing technique focuses on analyzing and extracting the event sequence of the specific pattern from the continuous event streams. Under the high-throughput situations, how to recognize the event sequence quickly and accurately has become an important problem. The state-of-the-art pattern matching methods, i.e. NFA, Petri and DAG, have shortcomings in the expressive ability and high cost to support some requirements. To deal with this situation, we propose a tree-based pattern matching method PMTree. PMTree defines event model and corresponding event relation operator, maps event pattern to the specific nodes in PMTree, applies time/predicate constraints on these nodes, and at last joins them to build a PMTree. We study the optimization strategies in the tree construction which can reduce the pattern matching cost and search the optimal combination of tree nodes, providing a cost model and an optimization algorithm. Experiments show that PMTree is more efficient, compared with Esper, an open source complex event processing engine; in the same situation the processing speed can be 3-6 times faster than Esper, and its performance is stable under different situations, e.g. the number of events, the type of event sequence or the complexity of event sequence, etc.