Augmented Finite Automata (AFA)

October 12th, 2010

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.

Dynamic pattern matching

September 2nd, 2010

As streaming systems become an integral part of business operations, there is an increasing need to allow automated data mining of collected historical data, and feed the results of such analysis back into the real-time monitoring component. We call this the monitor-manage-mine (M3) cycle.

Consider the problem of pattern matching over streams data. Traditionally, the pattern to be detected is provided a priori as a static automaton, and any change requires a new automaton to be deployed. This can be expensive in a dynamic and responsive environment, where the pattern is being constantly adjusted based on real-time historical analysis and mining. In a recent VLDB 2010 paper, one of our contributions is to propose an alternate model where the pattern definition itself is modeled as a second stream input to the pattern matching operator. This allows us to naturally integrate any changes to the pattern definition, into the continuous query processing. This can be very useful in a highly dynamic monitor-manage-mine business cycle. Interestingly, in our prototype implementation using StreamInsight, we found that dynamic patterns add insignificant overhead to normal processing. For more details, you are welcome to read the paper.

Dagstuhl seminar

May 20th, 2010

This week, I have been attending the Dagstuhl seminar on event processing. The seminar is conducted in a castle, in the midst of a very scenic and remote countryside in Germany. The calm atmosphere encourages sharing, innovation, and trust – this is also aided by the abundance of beer and wine at the venue :-) . Rooms at the castle cannot be locked from the outside, and apparently there has never been a theft or loss as a result of this choice. The seminar this year is focusing mainly on creating a single document that defines the concepts and facilities, and outlines the desired future and research challenges in the area of event processing. I have been closely involved with setting a context for event processing and its relationship to other disciplines, including the areas that are predecessors, contemporaries, and applications of event processing.