On the Complexity of Privacy-Preserving Complex Event Processing

Complex Event Processing (CEP) Systems are stream processing
systems that monitor incoming event streams in search of userspecified
event patterns. While CEP systems have been adopted in
a variety of applications, the privacy implications of event pattern
reporting mechanisms have yet to be studied — a stark contrast to
the significant amount of attention that has been devoted to privacy
for relational systems. In this paper we present a privacy problem
that arises when the system must support desired patterns (those
that should be reported if detected) and private patterns (those that
should not be revealed). We formalize this problem, which we term
privacy-preserving, utility maximizing CEP (PP-CEP), and analyze
its complexity under various assumptions. Our results show that
this is a rich problem to study and shed some light on the difficulty
of developing algorithms that preserve utility without compromising
privacy.