  Complex event processing (CEP) systems continuously process input event
streams to detect patterns. Over time, the input event rate might fluctuate and
overshoot the system's capabilities. One way to reduce the overload on the
system is to use load shedding. In this paper, we propose a load shedding
strategy for CEP systems which drops a portion of the CEP operator's internal
state (a.k.a. partial matches) to maintain a given latency bound. The crucial
question here is how many and which partial matches to drop so that a given
latency bound is maintained while minimizing the degradation in the quality of
results. In the stream processing domain, different load shedding strategies
have been proposed that mainly depend on the importance of individual tuples.
However, as CEP systems perform pattern detection, the importance of events is
also influenced by other events in the stream. Our load shedding strategy uses
Markov chain and Markov reward process to predict the utility/importance of
partial matches to determine the ones to be dropped. In addition, we represent
the utility in a way that minimizes the overhead of load shedding. Furthermore,
we provide algorithms to decide when to start dropping partial matches and how
many partial matches to drop. By extensively evaluating our approach on three
real-world datasets and several representative queries, we show that the
adverse impact of our load shedding strategy on the quality of results is
considerably less than the impact of state-of-the-art load shedding strategies.
