2012 EfficientEventPatternMatchingwi

• (Cadonna et al., 2012) ⇒ Bruno Cadonna, Johann Gamper, and Michael H. Böhlen. (2012). “Efficient Event Pattern Matching with Match Windows.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339607

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+Efficient+Event+Pattern+Matching+with+Match+Windows
• http://dl.acm.org/citation.cfm?id=2339530.2339607&preflayout=flat#citedby

Quotes

Author Keywords

• Event pattern matching; optimization; query processing; window

Abstract

In event pattern matching a sequence of input events is matched against a complex query pattern that specifies constraints on extent, order, values, and quantification of matching events. In this paper we propose a general pattern matching strategy that consists of a pre-processing step and a pattern matching step. Instead of eagerly matching incoming events, the pre-processing step buffers events in a match window to apply different pruning techniques (filtering, partitioning, and testing for necessary match conditions). In the second step, an event pattern matching algorithm, A, is called only for match windows that satisfy the necessary match conditions. This two-phase strategy with a lazy call of the matching algorithm significantly reduces the number of events that need to be processed by A as well as the number of calls to A. This is important since pattern matching algorithms tend to be expensive in terms of runtime and memory complexity, whereas the pre-processing can be done very efficiently. We conduct extensive experiments using real-world data with pattern matching algorithms for, respectively, automata and join trees. The experimental results confirm the effectiveness of our strategy for both types of pattern matching algorithms.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 EfficientEventPatternMatchingwi	Bruno Cadonna Johann Gamper Michael H. Böhlen			Efficient Event Pattern Matching with Match Windows				10.1145/2339530.2339607		2012