Detection of chart patterns is a very common application of a stream processing system, in applications such as algorithmic trading. The trends being detected and exploited are often rather bizarre. Simple techniques such as regular expressions and constrained automata are inadequate to detect such complex patterns. We recently proposed new semantics and model for pattern matching over streams. The proposed model, called Augmented Finite Automaton (or AFA), is basically an NFA with additional typed information (called a register) associated with the automaton during runtime. Registers make it possible to support many modern pattern requirements, while the specific restrictions on size and semantics ensure a very efficient implementation over disordered streams.
- Badrish Chandramouli
- Microsoft Research