Utility-Maximizing Event Stream Suppression

Complex Event Processing (CEP) has emerged as a technology for
monitoring event streams in search of user specified event patterns.
When a CEP system is deployed in sensitive environments the user
may wish to mitigate leaks of private information while ensuring
that useful nonsensitive patterns are still reported. In this paper we
consider how to suppress events in a stream to reduce the disclosure
of sensitive patterns while maximizing the detection of nonsensitive
patterns. We first formally define the problem of utilitymaximizing
event suppression with privacy preferences, and analyze
its computational hardness. We then design a suite of real-time
solutions to solve this problem. Our first solution optimally solves
the problem at the event-type level. The second solution, at the
event-instance level, further optimizes the event-type level solution
by exploiting runtime event distributions using advanced pattern
match cardinality estimation techniques. Our user study and experimental
evaluation over both real-world and synthetic event streams
show that our algorithms are effective in maximizing utility yet still
efficient enough to offer near real-time system responsiveness.