Monday, January 19, 2009

On Event Pattern Detection vs. Event Pattern Discovery



This drawing, in various forms, has been used by us for many years to illustrate the notion of pattern, actually in the PowerPoint version it is animated, and the geometric shapes are keep moving. The term pattern is a bit overloaded in event processing, as noted my DEBS 2008 tutorial on this topic, but this illustration refers to the pattern which shows some combination of events, to be more accurate it is a predicate on the event history that if evaluated to the value of
"true" something should happen. This illustration was created by Tali Yazkar-Haham from IBM Haifa Research Lab as an exercise in a presentation course, and was used in dozens of presentations ever since (including presentations of some people outside IBM who typically forgot to give credit to the source).

Paul Vincent, in a continuous debate with Tim Bass, on the complex events forum, has written about "detection of new instance" and "detection of new type". While these terms make sense, I prefer not to overload the term detection and use the terms event pattern detection and event pattern discovery.

Pattern detection deals with detection that a predefined pattern has happened. This is what illustrated in the picture above. Some example can be: a patient is hooked up to a heartbeat monitor, and the physician is pre-setting a pattern "the heartbeat is monotonically increasing within 10 minutes, and the amount of increase is more than 30 during that period". This is actually a predicate over a part of the event history of a single source and type (other examples can involve multiple sources and types, but the principle is the same).



So event pattern detection is defined as detection that a predefined patterns has occurred.
This is equivalent to what Paul called: Pattern instance Detection.
In contrast, when we talk about
event pattern discovery we mean that the pattern is not known in advance, and the pattern discovery function determines what is the pattern. The legend says that Archimedes discovered his famous laws about floating bodies when sitting in the bathtub and shouted: Eureka (this illustration was taken from the homepage of a company who has the word Eureka in its name, again animated in the source).
A pattern can be discovered by machine learning techniques using decision trees, statistical modeling, Bayesian Networks and numerous other methods. At the end when a pattern is discovered then it also need to be detected in reality; there are also cases in which there is a continuous detection since the patterns are changing after a short time.

Getting back to the previous example about the heartbeat, it may be the case that this pattern has bot been set by a physician, instead it was detected by some method that has looked at past events and found out that this pattern has some significance.

Most people thinking about "complex event processing" are actually talking about pattern detection, regardless of whether the patterns were composed by a human or discovered by machine learning. The illustration at the top of this page illustrates what people typically mean. As stated in the past, I don't want to get into the meaning of TLAs, and leave it to my colleagues who are doing marketing. Thus the term that I used "event pattern detection" is the more accurate one.

Another observation about the difference is that event pattern detection can be applied as COTS -- a user can use such a product, compose some patterns, hook it up to event sources, and get the pattern to be detected.

On the other hand --- while there are many tools that can help in the event pattern discovery, we cannot hook it up to event source and tell it: discover all. There is a need to do some formal modeling of the system, kind of patterns that are sought etc... In other words, this is not something that a typical developer or business analyst can do, since it requires some expertise,

It is getting late - so I'll finish at this point and return to this topic at some later point.



10 comments:

Damir said...

Ok Opher,
Time to do something about this rosy/pink text. It is hard to read. Have mercy, I am 48, wear reading glasses and this pink stuff is causing strain on eyes. Plenty of good themes out there. And don't give me "Read something else" -- I want to read this stuff.
Sincerely,
Damir Sudarevic
Damir Systems Inc.

Opher Etzion said...

Hi Damir. Sorry about the violet text, converted it to a more conservative color to let you concentrate on the content.

cheers,

Opher

Damir said...

Thank you, thank you, thank you.

Hans said...

From my experience, you need pattern detection in order to take an action. I'm sure that this is in a book somewhere.

For example, you can discover a pattern and use it to predict some outcome. But to take an action, you need to be looking for something specific (maybe the case when the predicted outcome meets some criteria) to trigger the action.

Opher Etzion said...

Hi Hans.

You are absolutely right. The pattern detection is part of the executable event processing on-line, pattern discovery typically occur off-line and create the patterns that need to be discovered on-line; there are cases that pattern discovery also occurs on-line, and may result in dynamic updates on pattern detection. I'll make more notes on it in one of the next postings.

cheers,

Opher

Hans said...

And for pattern discovery that is on-line, the result may be an update to some criteria or value in a detection rule. Or it may be an event that is evaluated by a detection rule. Or both.

Tim Bass said...

Hi Opher,

I agree with you (I think!). I don't think overloading of terms such as "detection of new instance" and "detection of new types" is important to solving most classes of problems.

That is why I did not reply to Paul's post. I don't find Paul's discussion of interest or useful.

Yours sincerely, Tim

Roland St├╝hmer said...

Hi Opher. Hi everybody.

What about the term: pattern *matching* for the detection of new instances? It does not entail any ambiguities as to whether the patterns are the subject of the detection or not.

Yours, Roland.

Opher Etzion said...

Hi Roland.

Actually - matching seems a good idea... I may adopt the term, need to sleep on it.

cheers,

Opher

Hans said...

Also "pattern recognition" could be used instead of "pattern discovery".