Shared Complex Event Trend Aggregation Contributions

We represent the workload of event trend aggregation queries as the workload template that exposes all sharing opportunities in the diverse nested Kleene patterns..

We avoid the exponential CPU costs of event trend construction by introducing MatStates (materialization states) to store intermediate aggregation results prior to sharing. We prove the correctness of the shared execution strategy. We analyze how the number of MatStates can be minimized to reduce both the CPU and memory overhead of sharing.

The Muse cost model formalizes the trade-off between the benefit of sharing and the overhead of MatState maintenance. The sharing plan refinement algorithm traverses the exponential search space in quadratic time by effectively pruning nonbeneficial sharing opportunities.

Our experiments on real and synthetic event streams demonstrate that Muse achieves 4 orders of magnitude performance improvement over state-of-the-art approaches.

---