Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/36339
Title: | A Formal Framework for Complex Event Recognition | Authors: | Grez, Alejandro Riveros, Cristian Ugarte, Martin VANSUMMEREN, Stijn |
Issue Date: | 2021 | Publisher: | ASSOC COMPUTING MACHINERY | Source: | ACM TRANSACTIONS ON DATABASE SYSTEMS, 46 (4) , p. 1 -49 (Art N° 16) | Abstract: | Complex event recognition (CER) has emerged as the unifying field for technologies that require processing and correlating distributed data sources in real time. CER finds applications in diverse domains, which has resulted in a large number of proposals for expressing and processing complex events. Existing CER languages lack a clear semantics, however, which makes them hard to understand and generalize. Moreover, there are no general techniques for evaluating CER query languages with clear performance guarantees. In this article, we embark on the task of giving a rigorous and efficient framework to CER. We propose a formal language for specifying complex events, called complex event logic (CEL), that contains the main features used in the literature and has a denotational and compositional semantics. We also formalize the so-called selection strategies, which had only been presented as by-design extensions to existing frameworks. We give insight into the language design trade-offs regarding the strict sequencing operators of CEL and selection strategies. With a well-defined semantics at hand, we discuss how to efficiently process complex events by evaluating CEL formulas with unary filters. We start by introducing a formal computational model for CER, called complex event automata (CEA), and study how to compile CEL formulas with unary filters into CEA. Furthermore, we provide efficient algorithms for evaluating CEA over event streams using constant time per event followed by output-linear delay enumeration of the results. | Notes: | Grez, A (corresponding author), Pontificia Univ Catolica Chile, Dept Comp Sci, Vicuna Mackenna 4860,Edificio San Agustin, Santiago 7820436, Chile.; Grez, A (corresponding author), Millennium Inst Fdn Res Data, Santiago, Chile. ajgrez@uc.cl; cristian.riveros@uc.cl; martin@martinugarte.com; stijn.vansummeren@uhasselt.be |
Keywords: | Complex event recognition; complex event processing; streaming;evaluation; constant delay enumeration | Document URI: | http://hdl.handle.net/1942/36339 | ISSN: | 0362-5915 | e-ISSN: | 1557-4644 | DOI: | 10.1145/3485463 | ISI #: | WOS:000728453500004 | Rights: | © 2021 Association for Computing Machinery | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2022 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
formal.pdf Restricted Access | Published version | 23.55 MB | Adobe PDF | View/Open Request a copy |
main.pdf Restricted Access | Peer-reviewed author version | 852.93 kB | Adobe PDF | View/Open Request a copy |
WEB OF SCIENCETM
Citations
6
checked on Apr 15, 2024
Page view(s)
44
checked on Sep 7, 2022
Download(s)
16
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.