Complex event recognition under time constraints: Towards a formal framework for efficient query evaluation
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
El Reconocimiento de Eventos Complejos (CER, por sus siglas en ingles) ofrece una solución relevante para procesar flujos de eventos, proporcionando información en tiempo real. Los sistemas CER detectan patrones en tiempo real, generan eventos complejos y responden a ellos. En estas tareas, el tiempo es un elemento central. De hecho, el modelo de secuencia temporal distingue a CER de otras soluciones, como los sistemas de gestión de flujos de datos. Algunos casos de uso incluyen salud (e.g. detección de arritmia) y sistemas de finanzas (e.g. identificar patrones de compraventa de acciones). Sorprendentemente, hasta ahora, las restricciones de tiempo suelen incluirse de forma limitada en los lenguajes de consulta y modelos de CER, y seguimos careciendo de una comprensión profunda sobre la expresividad y los algoritmos eficientes en relación con esta característica crucial: el tiempo. Este trabajo estudia el CER bajo restricciones de tiempo, considerando su lenguaje de consulta, modelos computacionales y algoritmos de evaluación en streaming. Comenzamos presentando una extensión de la Lógica de Eventos Complejos (CEL), llamada timed CEL, que incluye operadores temporales simples. Mostramos que timed CEL facilita la modelación de lenguajes de consulta de CER en la práctica, sirviendo como herramienta para estudiar su poder expresivo bajo restricciones temporales. Para ello, introducimos un modelo de autómata, llamado timed Complex Event Automata (timed CEA), que extiende el modelo CEA existente con relojes, combinando CEA y autómatas temporizados en un único modelo. Mostramos que timed CEL y timed CEA son igualmente expresivos, proporcionando la primera caracterización de lenguajes de consulta de CER bajo restricciones temporales. Luego, exploramos la evaluación eficiente de timed CEA en flujos, enfocándonos en su determinización y algoritmos. Presentamos una clase de timed CEA cerrada bajo determinización. Finalmente, desarrollamos un algoritmo de evaluación con tiempo de actualización constante y retraso lineal en salida para timed CEA deterministas monotónicos con un solo clock y comparaciones menor igual o mayor igual.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2025.
Keywords
Evaluación de consultas, Streams, Reconocimiento de eventos complejos, Teoría de autómatas