2012 EfficientEventPatternMatchingwi: Difference between revisions

From GM-RKB
Jump to navigation Jump to search
(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

Subject Headings:

Notes

Cited By

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

;

 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2012 EfficientEventPatternMatchingwiBruno Cadonna
Johann Gamper
Michael H. Böhlen
Efficient Event Pattern Matching with Match Windows10.1145/2339530.23396072012