  Complex Event Processing (CEP) is a stream processing model that focuses on
detecting event patterns in continuous event streams. While the CEP model has
gained popularity in the research communities and commercial technologies, the
problem of gracefully degrading performance under heavy load in the presence of
resource constraints, or load shedding, has been largely overlooked. CEP is
similar to "classical" stream data management, but addresses a substantially
different class of queries. This unfortunately renders the load shedding
algorithms developed for stream data processing inapplicable. In this paper we
study CEP load shedding under various resource constraints. We formalize broad
classes of CEP load-shedding scenarios as different optimization problems. We
demonstrate an array of complexity results that reveal the hardness of these
problems and construct shedding algorithms with performance guarantees. Our
results shed some light on the difficulty of developing load-shedding
algorithms that maximize utility.
