  Complex event processing (CEP) is a prominent technology used in many modern
applications for monitoring and tracking events of interest in massive data
streams. CEP engines inspect real-time information flows and attempt to detect
combinations of occurrences matching predefined patterns. This is done by
combining basic data items, also called primitive events, according to a
pattern detection plan, in a manner similar to the execution of multi-join
queries in traditional data management systems. Despite this similarity, little
work has been done on utilizing existing join optimization methods to improve
the performance of CEP-based systems. In this paper, we provide the first
theoretical and experimental study of the relationship between these two
research areas. We formally prove that the CEP Plan Generation problem is
equivalent to the Join Query Plan Generation problem for a restricted class of
patterns and can be reduced to it for a considerably wider range of classes.
This result implies the NP-completeness of the CEP Plan Generation problem. We
further show how join query optimization techniques developed over the last
decades can be adapted and utilized to provide practically efficient solutions
for complex event detection. Our experiments demonstrate the superiority of
these techniques over existing strategies for CEP optimization in terms of
throughput, latency, and memory consumption.
