Sequenced event set pattern matching
MetadataShow full item record
Event pattern matching is a query technique where a sequence of input events is matched against a complex pattern that specifies constraints on extent, order, values, and quantification of matching events. The increasing importance of such query techniques is underpinned by a significant amount of research work, the availability of commercial products, and by a recent proposal to extend SQL for event pattern matching. The proposed SQL extension includes an operator PERMUTE, which allows to express patterns that match any permutation of a set of events. No implementation of this operator is known to the authors. In this paper, we study the sequenced event set pattern matching problem, which is the problem of matching a sequence of input events against a complex pattern that specifies a sequence of sets of events rather than a sequence of single events. Similar to the PERMUTE operator, events that match with a set specified in the pattern can occur in any permutation, whereas events that match with different sets have to be strictly consecutive, following the order of the sets in the pattern specification. We formally define the problem of sequenced event set pattern matching, propose an automaton-based evaluation algorithm, and provide a detailed analysis of its runtime complexity. An empirical evaluation with real-world data shows that our algorithm outperforms a brute force approach that uses existing techniques to solve the sequenced event set pattern matching problem, and it validates the results from our complexity analysis.
Showing items related by title, author, creator and subject.
Cadonna B; Gamper J; Böhlen MH (Springer, 2014)In event pattern matching, various selection strategies have been proposed to impose additional constraints on the events that participate in a match. The skip-till-next-match selection strategy is used in scenarios where ...
Cadonna B; Gamper J; Böhlen MH (ACM, 2012)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 ...
Gacitua-Decar V; Pahl C (2017)Context: Processes are central to the operation of many systems or organizations. Process-centric systems, ranging from enterprise workfow systems to open distributed service compositions, have significantly increased in ...