Efficient multi-query evaluation for distributed CEP through predicate-based push–pull plans.

Complex Event Processing (CEP) evaluates queries over event streams. However, once events are generated by nodes in a network, query evaluation requires the transmission of events between the nodes. Commonly, this is realized by sending events immediately upon their generation. Yet, to reduce network communication, query evaluation may incorporate pull-based communication, where events are buffered locally until they are requested by another node. Existing approaches for push–pull communication in distributed CEP, however, are limited in the expressiveness of pull requests and leverage solely the temporal constraints imposed by a query. In this paper, we propose a new evaluation model for distributed CEP, coined predicate-based push-pull (PrePP) plans. It includes pull requests that enable fine-granular filtering of events at their sources based on query predicates, thereby reducing event transmission. We formulate the problem of constructing PrePP plans with minimal transmission cost that also exploit opportunities for sharing of intermediate results among the queries of workload. However, the construction of optimal PrePP plans turns out to be NP-hard. We therefore propose algorithms to speed up the construction of PrePP plans, while producing near-optimal results. We illustrate the benefits of PrePP plans for distributed CEP in comprehensive experiments with synthetic as well as real-world data. Specifically, PrePP plans can reduce event transmission by up to three orders of magnitude over baseline techniques. • We propose a model for push–pull communication in distributed complex event processing (CEP) that leverages query predicates in pull requests. • Given a network of event sources and a query workload, we formulate the problem of constructing a predicate-based push–pull plan that minimizes transmission costs. • We present strategies to construct efficient evaluation plans under this model. • Experiments with synthetic and real-world data illustrate the benefits of the presented evaluation model for distributed CEP. [ABSTRACT FROM AUTHOR]