Real Time Streaming Pattern Detection for Ecommerce

Wiliam Braik, Floreal Morandat, Jean-Remy Falleri and Xavier Blanc

Introduction

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.

As a prerequisite for the next sections, let us define the following :

Let S be the input data stream of our system

Each element of S is an event e, which contains a timestamp t and some data d;

The customer id c and the action a can always be extracted from d.

Language Constructs

The most basic, indivisible element of the language is the atom, which matches an action a.

Operators can be seen as bindings between atoms to form patterns.

Operators can also bind patterns together to form more complex patterns.

The Followed By operator (noted ->) is a binary operator that captures the succession of two events or patterns.

For instance, P: View -> Exit captures a View event followed by an Exit event.

Similarly, 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.

Contiguity of Events

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.

Compilation to Deterministic Finite Automata (DFA)

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.

For the sake of conciseness, we only describe the compilation of the non-contiguous versions of both the Followed By and Kleene Plus operators.

However, note that their contiguous versions compile into similar yet slightly different automata.

An atom representing an action a is transformed into the basic automaton :

The complement of an action a is matched by the following automaton :

The star (*) 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) :

Here, the looping star transition allows to skip all irrelevant events in-between 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.

Syntax

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