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.
S
be the input data stream of our systemS
is an event e
, which contains a timestamp t
and some data d
;c
and the action a
can always be extracted from d
.a
.The Followed By operator (noted ->
) is a binary operator that captures the succession of two events or patterns.
P: View -> Exit
captures a View event followed by an Exit event.A -> B
captures the occurence of a pattern A
followed by the occurence of another pattern B
.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).
For instance, View+
captures a sequence of one or more consecutive View events.
Similarly, A+
captures a sequence of one or more consecutive A
patterns.
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 [View, Exit]
.
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.
For instance, P: View+ -> Exit
terminates when an Exit
event is matched after a sequence of one or more View
events.
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) :
A
and B
.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.
Name | Size | Description | |
---|---|---|---|
Parent Directory | - | ||
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 | |