Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report
This work addresses the need for forecasting in event stream processing, offering a domain-specific solution that is incremental by building on existing formalisms like symbolic automata and prediction suffix trees.
The paper tackles the problem of forecasting when complex event patterns will occur in real-time streams, a gap in existing Complex Event Recognition systems, and demonstrates that using prediction suffix trees as variable-order Markov models improves accuracy by capturing long-term dependencies more efficiently than full-order Markov models.
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.