On the patterns collections list

Back on dealing with the EPIA book, we are now in the process of the 2/3 book review, and started to work on the last 1/3. Right now I am working on a section talking about temporal issues in event processing, but before talking about that, I still wish to get back to the previous chapter that deals with event patterns, continuing the discussion that I have started in this posting, and continued in this posting. In the book we bring a collection of patterns, these patterns are not meant to be complete, and we expect to grow the collection of patterns over time using the book's website.

The patterns collected are of several types:

• Logical operator patterns: all, any, absence that designate conjunction, disjunction and negation event patterns.
• Threshold oriented patterns: count of events, average/maximum/minimum of some attribute of a collection of events has some binary relationship (e.g. > ) with a given threshold.
• Relative patterns: relative max/relative min selects the events with the minimal or maximal value for a certain attribute over a collection of events.
• Modal patterns: sometimes, always, select a collection of patterns if a certain predicate is satisfied over all/some of the events in this collection.
• Not select pattern: This is a second level modal pattern that selects events that were not selected by a certain patterns.
• Sequence pattern: A temporal pattern that denotes a conjunction of event that occur within a predefined order.
• Trend patterns: Temporal patterns that detect trend, e.g. a value of a certain attribute is consistently increasing with a context.
• Spatial distance patterns: These are similar to the threshold patterns, but relate to the distance of events from some point in space.
• Spatial relative patterns: This are similar to relative patterns, but relate to the relative distance of events from other events
• Spatiotemporal patterns: This combine temporal and spatial properties, and designate direction of movement (e.g. moving consistently north, moving towards some entity).

The current full list of patterns consist of 30 patterns, and this list will probably grow. Each of the patterns is defined in the book and demonstrated using an example.

More on patterns - later.

On the ingredients of pattern definitions

In the previoius posting I started the discussion about the notion of pattern, and stated that it is a function that selects an event subset; continuing to drill down on patterns, I'll say a few words about what are the ingredients of pattern definitions, what information do we need in order to perform pattern matching in a well-defined way:

• Pattern type: which determines WHAT the pattern matching is looking for. There are a variety of pattern types, and I'll dedicate a posting to the pattern type I collected so far. Some examples: sequence (temporal pattern), moving north (spatio-temporal pattern), trheshold pattern (e.g. related to average of some value over a set) and more.
• Participant set: the set of event types whose instances issue the pattern matching set.
• Context: the context to which the pattern is associated with (actually the agent executing the pattern is associated with).
  
• Pattern assertion: Some patterns have assertions associated with them. Assertion can determine if events are relevant (e.g. if we are looking at a sequence of two events, say event of type E1, and event of type E2, where in order to do a pattern matching we require that E1.A > E2.B, where A and B are names of attributes. There are also some pattern associated with certain pattern type, e.g. if the pattern type is a threshold pattern than there is an assertion associated with it, e.g. Average (e1.A) [over each context partition] > 40.
• Pattern policy: Pattern policy determines when a matching set is going to be activated, how many times, can event count for more than one pattern, how repeated events are treated and more.
  

This was only in title level, and in the next postings I'll provide more information about pattern types and pattern policies.

What is an "Event Processing Pattern" ?

My last trip abroad was a mix of vacation and business trip (to attend the Tretno event processing symposium, and the meeting of the EASSy consortium that is writing a proposal for EU project), as such I took a piece of luggage with me, and deposit it (in Hebrew the words "to deposit" and "to abandon" are very close --: "lehafkid" vs. "lehafkir", thus I am typically saying that I have abandoned the luggage in the airline...), anyway, standing near the carousel (something I really hate to do !), I realized that I am actually doing a pattern matching. I have a mental model of my luggage in my mind (shape, color, other characteristics), and I am trying to match this mental model with the pieces of luggage flowing on the carousel. There may be more than one that fits my mental model, and sometimes I grab one, look closely, and decides that this has been a "false positive". Likewise, we are matching patterns many times in our daily life.

So - what exactly is an event processing pattern? In the EPIA book, we have dedicated a (long!) chapter to pattern matching in event processing, and started it with the following definition:

A Pattern is a function that takes a collection of input event instances and produces a matching set that consists of zero or more of those input events


This is, in essence, what we do in the luggage case, selecting one out of a set. Interesting cases are cases in which we should find events that the pattern relate to their combination (this, according to some definitions, what makes the "Complex" in the "Complex Event processing" pharas), so they need to satisfy some pattern as a collection of events, and not as individual events. An example is we wish to determine if a moving object (say: motorcycle) is moving north, by looking at the location of the motorcycle over some period of time, we can observe whether the progression of location satisfies the pattern of "moving north". I'll write more about pattern types soon.

On temporal aspects of event processing

In the past I was involved in work on temporal databases, in the picture you can see a 1998 book about temporal databases that I co-edited with Sury Sripada and Sushil Jajodia. Although there were some attempts to create substantial extension to SQL with temporal capabilities, and move temporal databases to the mainstream. This did not work, and there are several reasons, the event processing area provides a second chance for these idea to come to the mainstream now, as event processing have strong relations to temporal issues. Bob Hagman from Aleri (former Coral8) has recently written some survey of implementation alternatives related to time aspects in the Aleri Blog. In the DEBS 2008 language analysis tutorial we had dealt quite briefly with the topic of time. Earlier this year I have written a chapter in the upcoming book of the book "Handbook of Research on Advanced Distributed Event-Based Systems, Publish/Subscribe and Message Filtering Technologies; edited by Annika Hinze and Alejandro Buchmann"

This chapter is entitled: "Temporal Perspectives in Event Processing".
Here is the chapter's main topics:

• Temporal dimensions: in temporal databases we dealt with the temporal semantics of a collection of snapshots (states), in event processing we deal with the temporal semantics of events (transitions). Are the temporal dimensions the same ? do they have the same semantics ?
• The "instantaneous" issue -- do event occur over a time-point or an interval, and if it is interval what does it mean from computational point of view ?
• Time granularity -- in temporal databases we introduced the term "chronon" which stands for the time granularity that makes sense for a particular use. This idea is also applicable to event processing, for different events, different chronons make sense.
  
• Temporal contexts: the term "time window" in stream processing is a kind of a temporal context. What kinds of temporal contexts are required, and what is the computational implications of them. I'll write more about contexts soon, as this is the topic of chapter 7 of the EPIA book.
• Temporal patterns: "complex event processing" is about finding patterns among collections of events; some (but not all) of these patterns are temporal in nature -- what are the temporal oriented patterns ?
• Temporal properties of derived events: An event processing system derives events as result of its processing. What is the time properties of the derived events? this is a rather tricky question that deserves a discussion.
• Ordering events: for some temporal patterns, knowing the order of events is important. What are the issues associated with keeping such an order, how out-of-order events should be handled ?
• A related issue is "retrospective events" -- what happens if events that relate to the past are detected, where the assumption that they did not occur already triggered some processing ?

• Issues of time in distributed environment -- clock synchronization, time-zone handling, time validity for mobile clients --- are all applicable for event processing.

As written, this is an outline of topics surveyed at that chapter, I'll write more about some of them in the future.

On Data Mining and Event Processing

Today I have travelled to Beer Sheva, the capital of the Negev, which is the south part of Israel, that consists mostly of desert. I have visited Ben-Gurion University, met some old friends, and gave a talk in a well-attended seminar on "the next generation of event processing". I have travelled by train (2 hours and 15 minutes each direction), and since my last visit there five years ago or so, they have built a train station from which there is a bridge which goes to the campus, very convenient. Since I am not a frequent train rider in Israel, I discovered that in both ends of the line, there are no signs saying which trains go on which track, and this is assumed to be common knowledge... Although they do notify when a train entered the station where it is going and from which track, but still they have a point to improve.

Since some of the people attended my talk were data mining people they have wondered about the relationships of event processing and data mining, since I've heard this question before I thought the answer will be of interest to more people.

In the "pattern detection" function of event processing, there is a detection in run-time of patterns that have been predetermined, thus, the system knows what patterns it is looking for, and the functionality is to ensure correct and efficient detection of the predetermined patterns.

Data mining is about looking at historical data to find various things. One of the things that can be found are patterns that have some meaning and we know that if this pattern occurs again then it requires some reaction. The classic example is "fraud detection", in which, based on mining past data, there is a determination that a certain pattern of action indicates suspicion of fraud. In this case the data mining determines the pattern, and the event processing system finds in run-time that this pattern occurs. Note, that not all patterns can be mined from past data, for example- if the pattern is looking for violation of regulations, then the pattern stands for the regulation, but this is not mined, but determined by some regulator and is given explicitly.

So - typically data mining is done off-line and event processing is performed on-line, but again, this is not true for all cases, there are examples in which event processing and mining are mixing in run-time. An example is: there is a traffic model, according to which the traffic light policies are set, but there is also constant monitoring of the traffic, and when the monitored traffic is deviating significantly then the traffic model has to be changed and the policies should be set according to the new traffic model, this is kind of mix between event processing and mining, since the actual mining process is triggered by events, and the patterns may change dynamically as the result of this mining process.

More - Later.

On EuroPLoP and Event Processing Patterns

This is Kloster Irsee in Germany, where the EuroPLoP conference is held. The conference itself is held in kind of an opposite way to other conferences, in a regular conference, the author of a paper presents, in this conference, the author of a paper hears other criticizing his paper, and does not talk. It also have some other properties -- some of the sessions are held in room which the chairs have been taken out, so people are sitting on the floor, or standing, there are also games embedded in the program --- my daughter would have said if she was here that there is a bunch of nerd children trying to behave in a cool fashion - well... anyway, we came here to combine work on creating a consortium for EU project and having a three hours "focused group" inside the conference, organized and moderated by Adrian Paschke. The audience was mixed - some were the EP gang, those who came to work on the EU project, and some where regular participants in the conference. The various interpretations of patterns related to EP have been discussed, and the need to advance in all of them. This is directly related to my tutorial in DEBS 2008, there is now work in progress on a pattern meta-language that we are doing in IBM, in a few weeks I'll tell you more about it - stay tuned.
More about my tutorial in DEBS 2008 - Paul Vincent from TIBCO has taken a picture of a slide that I've presented with different computer (due to some unclear technical problem) with probably different character set (Paul also blogged about this slide) - in footnote 1. Paul has been kind enough to send me the picture - so here it is, you may see some unknown characters...

More about patterns - soon.

On the multiple types of patterns in event processing

The red arrow in the map shows where I am now - in Kaufbeuren, a town in the south-west corner on Bavaria. I have arrived last night by train, and it has been a challenge to find a place to eat in 9PM, but with a few minutes of search I have found it. I am on the way to the patterns conference, in which we have a working group to establish a partnership towards EU project proposal. Thus, I would like to write a few lines about patterns. In my DEBS 2008 tutorial I have used the following slide:

In this slide there are four possible meanings for patterns in event processing:

(1). Patterns in the sense of functions that event processing application may perform (e.g. enrich, route, transform, filter, detect pattern).

(2). Patterns that are detected on the history of events (note that "detect pattern" is just one of the patterns of the first type, but the support of this pattern is what makes it CEP).

(3). Patterns in the user's domain - the way things are presented to the user (which may not be translated 1-1 to an implementation pattern)

(4). Patterns in the software engineering sense - best practices of how to use some language / product / technology.

All of the four are interesting and also have some dependencies, my tutorial has concentrated mainly on patterns of type (2), I have written about type (1) a lot in the past -- types (3) and (4) are frontiers that need to be conquered. More - Later.

On EP and Analytics

Recently, some of my fellow-bloggers have occupied themselves with the question whether analytics are integral necessary part from CEP, and without it CEP does not really exist. My good friend Tim Bass went further in his current Blog and called the current state of the practice in CEP as Snake Oil , well - here I return to my previous posting with the metaphor of a group of blind people touching an elephant and each of them touches a different side of an elephant and each is confident that he knows what an elephant is, and furthermore he is the only one who knows what an elephant is. One of the benefits (there also some shortcomings...) of working in a large company is the exposure to many types of applications that are very far apart, and yet, all of them can share the same infrastructure (with some variations), talking specifically about the issue of EP and analytics - there are some applications that you cannot really think of without using analytics like "fraud detection" - where we need always to look at patterns that were unknown before, and have been used when our software has blocked the previous set of gaps, thus if the blind person touches the right back leg of the elephant in the "fraud detection" side, he sees analytics as a must. However - likewise there are plenty of other application - probably on other legs, back or trunk that do not require analytics - some simple examples: A physician sets individual alerts based on combination of test results/monitors reading - when to alert the physician or nurse; exception handling in manufacturing process - where the exceptions types are well-defined (and translated again to some combination of events); monitoring security regulation of different persons that need to be accompanied to various places within a plant according to the tag type, and checking if an autorized escorting person exists within the required distance, which monitors regulation and does not require any analytics, this is a small sample of CEP applications I have noticed recently.

Personally I think that analytics are very important, and we'll see more and more applications in which they are required, like the fraud detection one I've already mentioned, smart auditing etc... As stated before, I think that the combination of EP and some intelligent techniques (like: machine learning, prediction, handling uncertain information), which I call "Intelligent Event Processing" is very important for going forward, and we intend to reach to the AI community by doing a first Intelligent Event Processing conference as one of the AAAI spring symposia - stay tunde to note on that,

Having said that, I cannot say that this is the majority of applications, currently most CEP applications do not require analytics, here I join the opinion of Hans Glide on this issue.



This assertion returns me to the picture on the top of this blog - showing the half-full glass syndrom. Some people look at the empty half glass and some look at the full half glass. First - let's take the optimistic "full half" approach -- indications show that there are CEP products that serve as platform to build applications that bring real value to real customers, these applications are in a wide variery of areas, in variety of products, some of the type of "time series" streams, and some are not (next week I'll give a tutorial in DEBS 2008 on patterns, so this will be an opportunity to blog about types of patterns). The fact that they exist, is an indication that the EP indusrty is not just promoting "snake oil"
It is more interesting, as a scientist, to look at the empty half glass - which I think is even more than half. I think that the EP discipline is in its infancny, it already walks some steps, can say a few words, but we need to invest more until it will run, dance, sing and write Blogs... However, as every parent can testify, huge progress happens since from being a newborn until getting to the state I've described, so I don't underestimate the work done so far, and the traction achieved in the market, and think the entire community believe that we just scratched the surface of the potential. More - later.

On Event Pattern Semantics

Today is Passover, while I am far from being religious, there are several traditions we keep, one of them is to have a family dinner in Passover-eve, and reading (at least part of) the Haggadah, so I've looked at the internet to find some fancy Haggadah in English, and here is the result.

The call for EPTS founding members
is also progressing - by now more than 20 compnies either signed or indicated that they are in internal approval process, and intend to sign as EPTS members, in addition to about 20 individual members. We excpect this number to grow towards the deadline, and call anybody who has not joined and wish to contribute to the emerging EP community to join.

Moving to today's topic: Tom Puzak has posted on the CEP interest group a message about nine features the CEP engine should have. This discussion is useful, since there is no agreed upon "CEP manifesto", a definition what are the functions that should be supported by "CEP engines", and we are going to need one, sooner or later.

Since I am working on a tutorial for the DEBS conference which will talk about event pattern semantics as a major theme, here is a sneak preview about the type of semantic decisions that are needed, this is in addition to the semantics of the specific pattern (conjunction, disjunction, absernce, sequence...).

1. In which context this particular pattern is relevant. Context can be temporal (within working hours, 1 hour from the power break), spatial (within the headquarter building), semantic (only for platinum customers or state-oriented ( while it is rainining) - or combinations of all the various dimensions (I have written before about the notion of context).

2. Is an event participate in the same pattern in a single context or in multiple contexts ? this can happen when there there is overlap among contexts.

3. Is the action / notification about the fact that the pattern has been detected should execute immediately or in a deferred mode (example: at the end of the temporal context).

4. Within a context - is the pattern existential (i.e. we are looking for a single pattern per context) or can there be multiple instances >

5. Using quantifiers on synonims - Taking the example from Tom Puzak's message: we are looking for a message of A, B within 60 secondes (temporal context), and the actual flowing events are: A1 A2 B1 A3 B2 B3 - we may want the cartesian product, but typically this is not what we really wish - thus, we can use quantifiers to select among the A and B events. Quantifiers can be according to order - firts, last, each or according to content of attributes (or both).

6. Can a single event particpate in more than one pattern within the same context ?

7. Should newer synonim kill older sysnonims ?

This are just titles - and in the DEBS tutorial I'll explain each with examples and show how they impact the pattern detection behavior.

Bottom line -- tune up the semantics of a pattern consists of several decisions, if these decisions are not supported in the language, and the application does not conform with the default, results in hacking around... more - later.

Event Processing can change some people's life

After returning from a business trip, and a few days family vacation to celebrate the Purim holiday, I am retrurning to the Blog. One of my loyal readers, Eran Toch, has suggested the topic of this posting by sending me an article saying that the former NY governor, Mr. Spitzer, has started his way down of his high office, when caught by a "anti money laundering" program that looked for simple pattern of three events. Well - this is a classic event processing pattern, and it seems that it has changed the life of a few people (starting from Eliot Spitzer himself, and in a chain effect, many other people). This reminds me of a visit that a group of Eurpoean journalists visited the IBM Haifa Research Lab in Israel in 2003 or 2004, and I was asked to give them a talk about CEP (I am not sure even if we already used this name) - after giving them some example of use cases, all of a sudden one of the journalists had the association to Orwell's big brother, and after he mentioned it, there was some philosophical debate between some of the journalists to us, whether this technology has a potential to be a nightmare for human rights. My opinion is that many technologies can be abused, but can also used for good causes - criminals (and auditors) can use patterns to find flows in systems, and organizations can use similar patterns in order to trace the same criminals that are trying to take advantage of flows... No matter how used -- event patterns is very powerfull, and its impact on our life has not even scratched the surface of its potential.

CEP and the story of the captured traveller

Reading the recent posting of my friend Tim Bass entitled "CEP and the story of the Fish" I decided to answer with another story (from the other side of Asia) :

A traveller went in the jungle somewhere on the globe and unfortunately was captured by a tribe that is still using ancient weapons. He is brought to the chief, and the chief says - " You have trespassed into the tribe's territory, which is punishable by death, however, I am a very curious person, if you'll show me something I haven't seen before I'll let you go"; our unlucky traveller started to look in his pockets and the only meaningful thing he found was a lighter, so he took his chance, showing it to the chief saying: "this thing makes fire", however, since he was in under a big pressure, he pressed once - no fire, pressed twice - no fire, in the third time the lighter indeed has produced the promised fire, the chief did not hesitate and said "let him go", so our relieved traveller muttered to himself - "I knew that they have not seen a lighter", but surprisingly to him the chief said - "oh, I have seen many lighter, but a Zippo lighter that does not light in the first time I have never seen".

When someone disagrees with somebody else, it is very easy to assume that my point of view is right since I am smarter / knows more / more qualified / older / more experienced / generally always right etc... My preference is not to doubt the wisdom, experience or qualification of anybody that I am arguing / discussing / debating with, but make the arguments on the issue and not on the person who makes the arguments....

Enough introduction -- now for the main message of this posting, the term CEP (Complex Event Processing) has more or less agreed now in the industry to denote "computing that performs operations on complex events", where complex event is an "abstraction or aggregation of events". The term complex does not say that the processing is complex, but that it deals with complex events, as defined. Complex event processing is typically detecting predefined patterns that can be expressed by queries/rules/patterns/scripts and are deterministic in nature. Regardless if I think that this is the best term, I think that it is important to have common agreed terminology, otherwise we are confusing the industry, the customers (and sometimes ourselves). Now, Tim Bass claims that since event processing with stochastic/probabilistic/uncertain nature is more complex than what we call "complex event processing", we have to call this one - "complex event processing", and rename what we call "complex event processing" to be "simple event processing". Unfortunately, it is too late for that - and also not justified, again, since the "complex" in the "complex event processing" does not say that this is "complex processing of events" but that this is "processing of complex events" (very common misconception !). Bottom line: yes - there is another class of event processing capabilities that requires techniques from AI, machine learning, OR etc.. and that is not deterministic in nature; no - I don't think we should call it "complex event processing", we have suggested the term "intelligent event processing" which I have already referred to in previous posting , there are a variety of other postings that I have dedicated to terminology.

More - later

On False positives and False Ngatives

From syntactic point of view, CEP looks for patterns and derives event / trigger action based on each pattern detected, however, detecting the patten is the mechanic work, the patterns designate a "situation" which is an "event" in the customer's frame of reference to which the customer wants to react to (there are also "internal" situation for further processing. There is obviously a gap between the intention (situation) and the way it is detected (patter no the event flow). In many cases,satisfying the pattern is sufficient condition to detect the intended situation, however, in other cases, this serves as "best approximation". This leads to the phenomenon of false positives (detecting of patterns, but the situation did not really happen) and post negatives (situation occurred but pattern has not been detected). Some reasons are:

• Raw events are missed - do not get at all, or do not get on time (source or communication issues).
• Raw events are not accurate - values are not accurate (source issues).
• Temporal order issues - Uncertainty in correct order of events.
• Pattern does not accurately reflect the conditions for situation (e.g. there are probabilistic elements)
• (other reasons) ?

Like the time constraints case there are various utility functions to designate the damage from either false positives or false negatives.

More on that issue - later.

On CEP and IEP

Ambidexterity is a good property for a boxer, he can decide when is better to attack with his right hand, and when to attack with the left hand (I am part of the left-handed minority, should write sometimes a post about being left-handed in the Right-hand people's world). Likewise, there are problems in the event processing space that can be solved by deterministic means (rules, queries, scripts, patterns --- chose your favorite religion), and problems that are solved by stochastic means -- using probabilistic networks, machine learning etc.. (AKA IEP - Intelligent Event Processing). When there is a pattern that need to be traced , to check compliance with regulations, and the pattern is well-defined - then a deterministic approach should be used; when there is a need to dynamically change the traffic lights policies to have minimal waiting time of vehicle, there is a need to predict the traffic in the next few minutes - this is a non deterministic problem and require some stochastic tool (BTW - my student, Elad Margalit, is looking at the traffic lights issue as his M.Sc. thesis). Event Processing Platforms should include various types of functionality - which brings to another discussion on the "actor/agent" architecture - which I'll refer to in one of the next posts. more -later

Non events again - much ado about nothing

Shakespeare fans (and theater fans in general) love the wonderful play : Much Ado about Nothing.
I recalled the title of the play when seeing that different people this week have written various things about the issue of "non events". Tim Bass thinks that this is just a time-based event, there have been various answers to David Luckham's question on the CEP forum. I actually did not think that I'll write second posting on this topic, since I don't think that this topic is that important, it is just one of various basic patterns. However, I'll try to provide more formal discussion on what is called "non-event event".

Let's defer the name discussion for a while - and try to define what it is:

This pattern is a function of two things (as many patterns are): an event E, and a context C, for simplicity let's assume that this is a temporal context only - i.e. a time window.

The definition:

• Forall t: t is a time-stamp and t is an element of C, the event e does not occur in C.

We can of course enable a condition - saying "event E that satisfies predicate P", but this does not change the principle.

The first question is - does the fact that an event E does not occur in a time-stamp t is an event - i.e. is a "negative event" an event by itself - the answer is NO - the fact that an event does not happen in a certain time-stamp is not an event, since an event is something that happens and not something that does not happen.

The second question is - is the definition of pattern shown above is an event ? the answer is - like any other pattern, the detection of a pattern may create a derived event. The semantics is that the detection of this pattern may be interpreted as a situation that requires some reaction, and in this case, we chose to derive an event that designates that this situation has been reported, this does not change the answer to the first question - the negative event at any time-stamp is still not an event!

Now - to the question of WHEN such a derived event is reported. In general, a derived event may be reported immediately when the pattern is detected, or in a deferred mode (this term is taken from active databases). There are patterns that only make sense in deferred mode - this pattern is one of them - since it is only make sense to talk about the fact that an event did not happen during a time-interval - at the end of this time-interval. Deferred report of derived events typically occurs at the end of a temporal context, but it can also have something like temporal coherence condition, such as: report within 2 hours. The reporting of the derived event is time-based, but this is true not only for this pattern, but to any derived event that is reported in deferred mode.

Last but not least -- the name : non-event event is a bad name, since it has a flavor of negative events as noted in question 1. The names - "absent pattern", "not pattern", and "time-out pattern" are used for it. Time-out can be a good name - but need to think if it general enough.

Back to other topics -- in the next post.