MuSE Graphs for Flexible Distribution of Event Stream Processing in Networks

Complex event processing (CEP) supports reactive applications through the continuous evaluating of queries over streams of event data. In a network of event sources, efficient query evaluation is achieved by distribution: Queries are split into operators (query decomposition), which are then assigned to some of the nodes (operator placement). Yet, existing solutions limit the decomposition to the operator hierarchy of a query, ignoring possible rewritings of it, and place each operator at exactly one node in the network. That neglects optimizations based on pattern composition through multiple queries as results are always gathered at a single sink node.

In this paper, we propose a new evaluation model for CEP, coined Multi-Sink Evaluation (MuSE) graphs. It incorporates arbitrary projections of queries for distribution and assigns them to potentially many nodes. We prove correctness of query evaluation with MuSE graphs and provide a cost model to assess its efficiency. Since the construction of cost-optimal MuSE graphs is intractable, we present an approximation algorithm and several pruning strategies. Our evaluation shows that MuSE graphs reduce network transmission costs by up to three orders of magnitude over baseline strategies.