Complex event recognition meets hierarchical conjunctive queries
Loading...
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Las consultas conjuntivas jerárquicas (HCQ) son un subconjunto de las consultas conjuntivas (CQ) con propiedades algorítmicas robustas. Berkholz, Keppeler y Schweikardt, entre otros, han demostrado que HCQ es la subclase de CQ mas grande que admite la evaluación dinámica de consultas con constant update time y constant dealy enumeration. Por otra parte, nos encontramos con el concepto de Complex Event Recognition (CER), una tecnología prominente para la evaluación de patrones sobre streams de datos. Dado que un stream de datos puede interpretarse como una secuencia, potencialmente infinita, de inserciones para la evaluación dinámica de consultas, es natural preguntarse si es posible aprovechar las propiedades de las HCQ para encontrar una clase robusta de consultas que puedan evaluarse de forma eficiente en el setting de CER. En esta tesis buscamos combinar las HCQ con patrones de secuencia para encontrar una clase de consultas de CER que tengan lo mejor de ambos mundos. Con este objetivo, proponemos un modelo de autómata, llamado Parallelized Complex Event Automata (PCEA), para evaluar consultas de CER con correlación (i.e., joins) sobre streams de datos. Este modelo nos permite expresar patrones de secuencia y comparar valores entre tuplas, pero además incorpora una definición alternativa de no determinismo que llamamos paralelización. Mostramos que para toda HCQ, utilizando bag semantics, es posible construir un PCEA equivalente. Adicionalmente, mostramos que HCQ es la clase de consultas conjuntivas acíclicas más grande que este modelo puede definir. Por lo anterior, PCEA es un modelo que captura precisamente las HCQ y las extiende con patrones de secuencia. Finalmente, mostramos que PCEA hereda las propiedades algorítmicas de las HCQ, presentando un algoritmo de evaluación para PCEA bajo sliding windows con logarithmic update time y output-linear delay.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2024.