Scalable Event Trend Analytics Contributions

The first contribution tackles the problem of executing queries with Kleene closure. Such queries extract event sequences of arbitrary, statically unknown length, which we call event trends. Due to common event sub-sequences in event trends, either the responsiveness is delayed by repeated computations or an exorbitant amount of memory is required to store partial results. Our solution compactly encodes event trend information using a graph-based data structure and detects trends in optimal CPU time given limited memory.

The second contribution is our optimization methodology for aggregation push-down into the Kleene closure computation to avoid expensive trend construction. Our runtime executor incrementally updates aggregates while reducing both time and space complexity. Furthermore, we support efficient trend aggregation under rich event matching semantics by computing aggregates at multiple granularity levels.

The third contribution is employment of shared execution given a workload of these complex pattern queries. Instead of processing each query separately, our approach shares incremental trend aggregation tasks amongst common queries in the workload. We observe that sharing is not always beneficial due to the overhead incurred in shared expression updates. To cope with this issue, we are developing a compile-time sharing analyzer.

---