Header

UZH-Logo

Maintenance Infos

A robust skip-till-next-match selection strategy for event pattern matching


Cadonna, Bruno; Gamper, Johann; Böhlen, Michael Hanspeter (2014). A robust skip-till-next-match selection strategy for event pattern matching. In: Advances in Databases and Information Systems - 18th East European Conference, ADBIS 201, Ohrid, Macedonia, 7 September 2014 - 10 September 2014, 177-191.

Abstract

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 some incoming events are noise and therefore should be ignored. Skip-till-next-match is prone to blocking noise, i.e., noise that prevents the detection of matches. In this paper, we propose the robust skip-till-next-match selection strategy, which is robust against noise and finds matches that are missed by skip-till-next-match when blocking noise occurs in the input stream. To implement the new strategy in automaton-based pattern matching algorithms, we propose a backtracking mechanism. Extensive experiments using real-world data and different event pattern matching algorithms show that with skip-till-next-match the number of matches not detected due to blocking noise can be substantial, and that our backtracking mechanism outperforms alternative solutions that first produce a superset of the result followed by a post processing step to filter out non-compliant matches.

Abstract

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 some incoming events are noise and therefore should be ignored. Skip-till-next-match is prone to blocking noise, i.e., noise that prevents the detection of matches. In this paper, we propose the robust skip-till-next-match selection strategy, which is robust against noise and finds matches that are missed by skip-till-next-match when blocking noise occurs in the input stream. To implement the new strategy in automaton-based pattern matching algorithms, we propose a backtracking mechanism. Extensive experiments using real-world data and different event pattern matching algorithms show that with skip-till-next-match the number of matches not detected due to blocking noise can be substantial, and that our backtracking mechanism outperforms alternative solutions that first produce a superset of the result followed by a post processing step to filter out non-compliant matches.

Statistics

Altmetrics

Downloads

2 downloads since deposited on 24 Oct 2014
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
Language:English
Event End Date:10 September 2014
Deposited On:24 Oct 2014 15:55
Last Modified:21 Nov 2017 17:29
Publisher:Springer International Publishing
Series Name:Lecture Notes in Computer Science
Number:8716
ISSN:0302-9743
ISBN:978-3-319-10932-9
Official URL:http://link.springer.com/chapter/10.1007/978-3-319-10933-6_14
Related URLs:http://link.springer.com/book/10.1007%2F978-3-319-10933-6 (Publisher)
Other Identification Number:merlin-id:10385

Download