Permanent URL to this publication: http://dx.doi.org/10.5167/uzh-56410
Cadonna, Bruno; Gamper, Johann; Böhlen, Michael H (2011). Sequenced event set pattern matching. In: 14th International Conference on Extending Database Technology , Uppsala, Sweden, 22 March 2011 - 24 March 2011, 33-44.
PDF - Registered users only
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.
|Item Type:||Conference or Workshop Item (Paper), refereed, original work|
|Communities & Collections:||03 Faculty of Economics > Department of Informatics|
|DDC:||000 Computer science, knowledge & systems|
|Event End Date:||24 March 2011|
|Deposited On:||10 Feb 2012 12:39|
|Last Modified:||20 Oct 2012 07:09|
|Publisher:||Association for Computing Machinery|
|Series Name:||Proceedings of the 14th International Conference on Extending Database Technology|
|Other Identification Number:||merlin-id:2493|
Users (please log in): suggest update or correction for this item
Repository Staff Only: item control page