  Complex Event Recognition (CER) systems have become popular in the past two
decades due to their ability to "instantly" detect patterns on real-time
streams of events. However, there is a lack of methods for forecasting when a
pattern might occur before such an occurrence is actually detected by a CER
engine. We present a formal framework that attempts to address the issue of
Complex Event Forecasting (CEF). Our framework combines two formalisms: a)
symbolic automata which are used to encode complex event patterns; and b)
prediction suffix trees which can provide a succinct probabilistic description
of an automaton's behavior. We compare our proposed approach against
state-of-the-art methods and show its advantage in terms of accuracy and
efficiency. In particular, prediction suffix trees, being variable-order Markov
models, have the ability to capture long-term dependencies in a stream by
remembering only those past sequences that are informative enough. Our
experimental results demonstrate the benefits, in terms of accuracy, of being
able to capture such long-term dependencies. This is achieved by increasing the
order of our model beyond what is possible with full-order Markov models that
need to perform an exhaustive enumeration of all possible past sequences of a
given order. We also discuss extensively how CEF solutions should be best
evaluated on the quality of their forecasts.
