Quick Search:

uzh logo
Browse by:
bullet
bullet
bullet
bullet

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
917Kb

Abstract

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
Language:English
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
ISBN:978-1-4503-0528-0
Publisher DOI:10.1145/1951365.1951372
Other Identification Number:merlin-id:2493
Citations:Google Scholar™

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

Repository Staff Only: item control page