2012 EfficientEventPatternMatchingwi: Difference between revisions
(Importing text file) |
m (Text replacement - " <i> " to " <i>") |
||
Line 18: | Line 18: | ||
In [[this paper]] we propose a general [[pattern matching strategy]] that consists of a [[pre-processing]] [[step]] and a [[pattern matching step]]. </s> | In [[this paper]] we propose a general [[pattern matching strategy]] that consists of a [[pre-processing]] [[step]] and a [[pattern matching step]]. </s> | ||
Instead of [[eagerly matching]] [[incoming event]]s, the pre-processing [[step]] [[buffers event]]s in a [[match window]] to apply different [[pruning technique]]s (filtering, partitioning, and [[testing]] for [[necessary match condition]]s). </s> | Instead of [[eagerly matching]] [[incoming event]]s, the pre-processing [[step]] [[buffers event]]s in a [[match window]] to apply different [[pruning technique]]s (filtering, partitioning, and [[testing]] for [[necessary match condition]]s). </s> | ||
In the second [[step]], an [[event pattern matching algorithm]], <i> A </i>, is called only for [[match window]]s that satisfy the [[necessary match condition]]s. </s> | In the second [[step]], an [[event pattern matching algorithm]], <i>A </i>, is called only for [[match window]]s that satisfy the [[necessary match condition]]s. </s> | ||
This [[two-phase strategy]] with a [[lazy call of the matching algorithm]] significantly [[reduces the number]] of [[event]]s that need to be [[processed]] by <i> A </i> as well as the number of calls to <i> A </i>. </s> | This [[two-phase strategy]] with a [[lazy call of the matching algorithm]] significantly [[reduces the number]] of [[event]]s that need to be [[processed]] by <i>A </i> as well as the number of calls to <i>A </i>. </s> | ||
This is important since [[pattern matching algorithm]]s tend to be expensive in terms of [[runtime]] and [[memory complexity]], whereas the [[pre-processing]] can be done very [[efficiently]]. </s> | This is important since [[pattern matching algorithm]]s tend to be expensive in terms of [[runtime]] and [[memory complexity]], whereas the [[pre-processing]] can be done very [[efficiently]]. </s> | ||
[[We]] conduct extensive [[experiment]]s using [[real-world data]] with [[pattern matching algorithm]]s for, respectively, [[automata]] and [[join tree]]s. </s> | [[We]] conduct extensive [[experiment]]s using [[real-world data]] with [[pattern matching algorithm]]s for, respectively, [[automata]] and [[join tree]]s. </s> |
Revision as of 03:13, 2 October 2015
- (Cadonna & 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:
Notes
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
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 |