Quick Search:

uzh logo
Browse by:


Zurich Open Repository and Archive

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.

[img]Published Version
PDF - Registered users only
View at publisher


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.




1 download since deposited on 10 Feb 2012
0 downloads since 12 months

Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Event End Date:24 March 2011
Deposited On:10 Feb 2012 11:39
Last Modified:20 Oct 2012 05:09
Publisher:Association for Computing Machinery
Series Name:Proceedings of the 14th International Conference on Extending Database Technology
Publisher DOI:10.1145/1951365.1951372
Other Identification Number:merlin-id:2493

Users (please log in): suggest update or correction for this item

Repository Staff Only: item control page