Wiliam Braik, Floreal Morandat, Jean-Remy Falleri and Xavier Blanc
This page describes our simple pattern detection language for eCommerce, which is partially presented in the article named Real Time Streaming Pattern Detection for Ecommerce. It is a declarative language for expressing customer behaviour patterns. This page explains how patterns can be composed to create more complex patterns, and how patterns are compiled into deterministic automata.
However, we do not talk about how the automata are deployed onto Spark for large-scale customer behavior detection. To know more about how automata are parallelized and run on Spark, please refer to the article.
Sbe the input data stream of our system
Sis an event
e, which contains a timestamp
tand some data
cand the action
acan always be extracted from
The Followed By operator (noted
->) is a binary operator that captures the succession of two events or patterns.
P: View -> Exitcaptures a View event followed by an Exit event.
A -> Bcaptures the occurence of a pattern
Afollowed by the occurence of another pattern
The Kleene Plus operator (noted
+) is a unary operator that captures a sequence of consecutive identical events or patterns (there must be at least one to be captured).
View+ captures a sequence of one or more consecutive View events.
A+ captures a sequence of one or more consecutive
Each operator exists in two versions : a contiguous version, and a non-contiguous version.
The non-contiguous versions allow the user to skip irrelevant events that are not matched by the definition of the pattern.
For instance, the non-contiguous version of Followed By can detect the pattern
P: View -> Exit within the sequence of events
[View, Add, Exit], as it can conveniently skip the
Add event in-between.
Whereas the contiguous version would only be able to match the two-element sequence
Similarly, the non-contiguous version of Kleene Plus can skip non-matching events, which is why it does not have any termination criterion by itself.
Therefore, Kleene Plus can never be the rightmost component of a pattern.
However, the pattern does terminate if Kleene Plus is followed by an event or any terminable pattern.
P: View+ -> Exit terminates when an
Exit event is matched after a sequence of one or more
The first step of the compilation inputs a pattern definition
P and outputs a Non-Deterministic Finite Automaton (NFA).
It is inspired by the Thompson construction algorithm, used for the compilation of regular expressions.
P is recursively decomposed into subpatterns and eventually into atoms.
Then, atoms are converted into simple automata which are composed to form subpatterns, which in turn are composed to form more complex patterns, until all components are merged and the final automaton is obtained. At each step, a set of rules for each operator determines how automata are merged together.
An atom representing an action
a is transformed into the basic automaton :
The complement of an action
a is matched by the following automaton :
*) transition matches any action besides
a. Generally speaking, a star transition is traversed if only and only if no other transition matches the current event.
Followed By is a binary operator which merges two automata (the automaton of
A on the left-hand side, and the automaton of
B on the right-hand side) :
The Kleene Plus operator basically inputs an automaton and outputs an enriched version of this automaton :
Note that the automaton of Kleene Plus does not have a final state. As explained in the previous section, the non-contiguous Kleene Plus does not have any termination criterion by itself.
To see an example of a more complex automaton composition, please refer to the article where the NFA of
P : View+ -> Exit is presented, and shows how a Kleene Plus automaton can be composed using a Followed By operator.
Once the NFA of the defined pattern
P is constructed, the second step of the compilation runs the Powerset construction algorithm in order to obtain the final DFA.
A simple syntax for the language is used throughout the article which is not actually the definitive syntax of the language. We are currently working on two different syntaxes : one SQL-like syntax, and the other similar to the syntax used in the article.
|AtomNot.png||3.6K||Automaton of the complement of an Atom|
|Atom.png||5.0K||Automaton of an Atom|
|KleenePlus.png||7.7K||Automaton of the operator Kleene Plus|
|FollowedBy.png||12K||Automaton of the operator Followed By|