Saturday, March 8, 2008

On Forward and Backward CEP

Paul Vincent from TIBCO has recently posted some thoughts on "goal oriented event processing" . As usual, Paul sees event processing during the " through the rule spectacles, so I'll try to predent it in a wider perspective. It is agreed that the role of CEP (which by itself is part of larger EP) is to detect patterns over multiple events. What is forward and backwards in this context ?
  • Forward: For each event -- check if this event completes some pattern
  • Backward: Given a pattern -- check if this pattern have been satisified (in some time context) in the past.

Both are useful for different cases, and sometimes we need a mix; looking deeper at the differences:

  • Forward is always event driven (it is done as a reaction to event)
  • Backward is request-response (it is done as part of explicit request), note that the request may by itself be trigerred by an event that makes it hybrid model.
  • Forward is used when patterns need to be detected immediately, it is most cost-effective to optimize for all patterns that events may complete then to look for all patterns and see if they are completed. Example: detect arbitrage opporunity between two exchanges.
  • Backwards is used when patterns are done periodically, or as ad-hoc queries. Example: At the end of each month, Find all stocks that during the last month have satisfied the following conditions: The stock closing values at the end of the day were strictly increasing over a period of five consecutive working days, anywhere during this month; The stock value in the beginning at the end of the five days value was at least 30 percent more than its value at the beginning of the five days period.
  • Mixed is used when in some cases -- a pattern may need "reinforcement" in past patterns -- Example: A person that has deposited (in aggregate) more than $20,000 within a single working day is a SUSPECT in money laundering. To reinforce the suspicion the following retrospective patterns are sought:
    There has been a period of week within the last year in which the same person has deposited (in aggregate) $50,000 or more and has withdrawn (in aggregate) at least $50,000 within the same week.
    The same person has already been a "suspect" according to this definition within the last 30 business days.
    If any of these patterns are satisfied – the event "confirmed suspect" is derived.

Forward and backward pattern detection can, of course, be implemented in various ways - business rules, SQL (stream and regular queries as backward), Scripts and specialized patter-oriented implementation.


Paul Haley said...

Interesting perspective. In general AI parlance backward chaining involves trying to find a path "backwards" from goals to the current state (rather than trying to find a path forward from the current state that achieves goals). By representing goals declaratively, they can persist over a longer period of time and support some of what you are talking about. This is distinct from most implementations, such as Prolog, in which goals are transient. Such goals would evaporate within the processing of only a single event and could not affect events over time! If you're interested, I just put up a paper on this from IJCAI-87 at request of the Drools team. Perhaps they will be implementing something along these lines?

Paul Haley said...

Interesting perspective! The key distinction between foward and backward "chaining" (rather than "processing") in AI is the latter requires goals while the latter is more reactive and may be implemented in a data-driven manner without regard to goals.

In CEP, one would want goals not to be transient within the processing of a single event, as they are in Prolog, but persistent and declaratively represented.

At the request of the Drools team, I posted an IJCAI-87 paper today that discusses precisely this issue. Perhaps they are working on it? Do you think Drools could make a good CEP tool?

Opher Etzion said...

Hello Paul. The forward and backward chaining (AKA - top-down vs. bottom-up in deductive databases) are indeed quite old. While "agent" is a kind of implementation, the "pattern" is a declerative specification - and the goal can be stated as: find events that match the pattern, similar to the "prove that a certain assertion is true" (and in the way substitute the variables in constants). The difference is that in event processing -- under "pattern detection" the pattern is predetermined -- unlike pattern mining, in which it is not. I'll make specific posting about it soon.