The Complex Event Recognition Group
Elias Alevizos

Alexander Artikis
Nikos Katzouris
Georgios Paliouras

Evangelos Michelioudakis

arXiv:1802.04086v1 [] 12 Feb 2018

Institute of Informatics & Telecommunications,
National Centre for Scientific Research (NCSR) Demokritos, Athens, Greece
{alevizos.elias, a.artikis, nkatz, vagmcs, paliourg}@iit.demokritos.gr

ABSTRACT
The Complex Event Recognition (CER) group is a research team, affiliated with the National Centre of Scientific Research “Demokritos” in Greece. The CER
group works towards advanced and efficient methods
for the recognition of complex events in a multitude of
large, heterogeneous and interdependent data streams.
Its research covers multiple aspects of complex event
recognition, from efficient detection of patterns on event
streams to handling uncertainty and noise in streams,
and machine learning techniques for inferring interesting patterns. Lately, it has expanded to methods for forecasting the occurrence of events. It was founded in 2009
and currently hosts 3 senior researchers, 5 PhD students
and works regularly with under-graduate students.

1.

INTRODUCTION

The proliferation of devices that work in realtime, constantly producing data streams, has led to
a paradigm shift with respect to what is expected
from a system working with massive amounts of
data. The dominant model for processing largescale data was one that assumed a relatively fixed
database/knowledge base, i.e., it assumed that the
operations of updating existing records/facts and
inserting new ones were infrequent. The user of such
a system would then pose queries to the database,
without very strict requirements in terms of latency.
While this model is far from being rendered obsolete (on the contrary), a system aiming to extract actionable knowledge from continuously evolving streams of data has to address a new set of challenges and satisfy a new set of requirements. The
basic idea behind such a system is that it is not
always possible, or even desirable, to store every
bit of the incoming data, so that it can be later
processed. Rather, the goal is to make sense out of
these streams of data, without having to store them.
This is done by defining a set of queries/patterns,
continuously applied to the data streams. Each
such pattern includes a set of temporal constraints

and, possibly, a set of spatial constraints, expressing
a composite or complex event of special significance
for a given application. The system must then be
efficient enough so that instances of pattern satisfaction can be reported to a user with minimal latency.
Such systems are called Complex Event Recognition
(CER) systems [6, 7, 2].
CER systems are widely adopted in contemporary applications. Such applications are the recognition of attacks in computer network nodes, human activities on video content, emerging stories
and trends on the Social Web, traffic and transport
incidents in smart cities, fraud in electronic marketplaces, cardiac arrhythmias and epidemic spread.
Moreover, Big Data frameworks, such as Apache
Storm, Spark Streaming and Flink, have been extending their stream processing functionality by including implementations for CER.
There are multiple issues that arise for a CER system. As already mentioned, one issue is the requirement for minimal latency. Therefore, a CER system has to employ highly efficient reasoning mechanisms, scalable to high-velocity streams. Moreover,
pre-processing steps, like data cleaning, have to be
equally efficient, otherwise they constitute a “luxury” that a CER system cannot afford. In this case,
the system must be able to handle noise. This may
be a requirement, even if perfectly clean input data
is assumed, since domain knowledge is often insufficient or incomplete. Hence, the patterns defined
by the users may themselves carry a certain degree
of uncertainty. Moreover, it is quite often the case
that such patterns cannot be provided at all, even
by domain experts. This poses a further challenge of
how to apply machine learning techniques in order
to extract patterns from streams before a CER system can actually run with them. Standard machine
learning techniques are not always directly applicable, due to the size and variability of the training
set. As a result, machine learning techniques must
work in an online fashion. Finally, one often needs

2.

COMPLEX EVENT RECOGNITION

Numerous CER systems have been proposed in
the literature [6, 7]. Recognition systems with a
logic-based representation of complex event (CE)
patterns, in particular, have been attracting attention since they exhibit a formal, declarative semantics [2]. We have been developing an efficient dialect of the Event Calculus, called ‘Event Calculus
for Run-Time reasoning’ (RTEC) [4]. The Event
Calculus is a logic programming formalism for representing and reasoning about events and their effects [14]. CE patterns in RTEC identify the conditions in which a CE is initiated and terminated.
Then, according to the law of inertia, a CE holds at
a time-point T if it has been initiated at some timepoint earlier than T , and has not been terminated
in the meantime.
RTEC has been optimised for CER, in order to
be scalable to high-velocity data streams. A form of
caching stores the results of subcomputations in the
computer memory to avoid unnecessary recomputations. A set of interval manipulation constructs simplify CE patterns and improve reasoning efficiency.
A simple indexing mechanism makes RTEC robust
to events that are irrelevant to the patterns we want
to match and so RTEC can operate without data filtering modules. Finally, a ‘windowing’ mechanism
supports real-time CER. One main motivation for
RTEC is that it should remain efficient and scalable
in applications where events arrive with a (variable)
delay from, or are revised by, the underlying sensors: RTEC can update the intervals of the already
recognised CEs, and recognise new CEs, when data
arrive with a delay or following revision.
RTEC has been analysed theoretically, through a
complexity analysis, and assessed experimentally in
several application domains, including city transport and traffic management [5], activity recognition on video feeds [4], and maritime monitoring
[18]. In all of these applications, RTEC has proven
capable of performing real-time CER, scaling to large
data streams and highly complex event patterns.
1

http://cer.iit.demokritos.gr/

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

ECcrisp
MLN –EC

P (CE | input data)

to move beyond detecting instances of pattern satisfaction into forecasting when a pattern is likely to
be satisfied in the future.
Our CER group1 at the National Centre for Scientific Research (NCSR) Demokritos, in Athens,
Greece, has been conducting research on CER for
the past decade, and has developed a number of
novel algorithms and publicly available software tools.
In what follows, we sketch the approaches that we
have proposed and present some indicative results.

0

3
initiation

10
initiation

20
termination

time I

Figure 1: CE probability estimation in the Event
Calculus. The solid line concerns a probabilistic
Event Calculus, such as MLN-EC, while the dashed
line corresponds to a crisp (non-probabilistic) version of the Event Calculus. Due to the law of inertia, the CE probability remains constant in the
absence of input data. Each time the initiation conditions are satisfied (e.g., in time-points 3 and 10),
the CE probability increases. Conversely, when the
termination conditions are satisfied (e.g., in timepoint 20), the CE probability decreases.

3.

UNCERTAINTY HANDLING

CER applications exhibit various types of uncertainty, ranging from incomplete and erroneous data
streams to imperfect CE patterns [2]. We have been
developing techniques for handling uncertainty in
CER by extending the Event Calculus with probabilistic reasoning. Prob-EC [21] is a logic programming implementation of the Event Calculus using
the ProbLog engine [13], that incorporates probabilistic semantics into logic programming. Prob-EC
is the first Event Calculus dialect able to deal with
uncertainty in the input data streams. For example, Prob-EC is more resilient to spurious data than
the standard (crisp) Event Calculus.
MLN-EC [22] is an Event Calculus implementation based on Markov Logic Networks (MLN)s [20],
a framework that combines first-order logic with
graphical models, in order to enable probabilistic
inference and learning. CE patterns may be associated with weight values, indicating our confidence
in them. Inference can then be performed regarding the time intervals during which CEs of interest hold. Like Prob-EC, MLN-EC increases the
probability of a CE every time its initiating conditions are satisfied, and decreases this probability
whenever its terminating conditions are satisfied,
as shown in Figure 1. Moreover, in MLN-EC the
domain-independent Event Calculus rules, expressing the law of inertia, may be associated with weight
values, introducing probabilistic inertia. This way,
the model is highly customisable, by tuning appropriately the weight values with the use of machine
learning techniques, and thus achieves high predic-

1
0.9
0.8

F1 score

0.7
0.6
0.5
0.4
0.3
0.2

MLN –EC

l–CRF

0.1
0

0

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1

Threshold

Figure 2: CER under uncertainty. F1 -score of
MLN-EC and linear-chain CRFs for different CE
acceptance thresholds.
tive accuracy in a wide range applications.
The use of background knowledge about the task
and the domain, in terms of logic (the Event Calculus), can make MLN-EC more robust to variations in the data. Such variations are very common in practice, particularly in dynamic environments, such as the ones encountered in CER. The
common assumption made in machine learning that
the training and test data share the same statistical properties is often violated in these situations.
Figure 2, for example, compares the performance of
MLN-EC against linear-chain Conditional Random
Fields on a benchmark activity recognition dataset,
where evidence is incomplete in the test set as compared to the training set.

4.

EVENT PATTERN LEARNING

The manual authoring of CE patterns is a tedious and error-prone process. Consequently, the
automated construction of such patterns from data
is highly desirable. We have been developing supervised, online learning learning tools for constructing logical representations of CE patterns, from a
single-pass over a relational data stream. OSLα [16]
is such a learner for Markov Logic Networks (MLNs),
formulating CE patterns in the form of MLN-EC
theories. OSLα extends OSL [9] by exploiting a
background knowledge in order to significantly constrain the search for patterns.
In each step t of the online procedure, a set of
training examples Dt arrives containing input data
along with CE annotation. Dt is used together
with the already learnt hypothesis, if any, to predict the truth values of the CEs of interest. This
is achieved by MAP (maximum a posteriori) inference. Given Dt , OSLα constructs a hypergraph that
represents the space of possible structures as graph

paths. Then, for all incorrectly predicted CEs, the
hypergraph is searched using relational pathfinding, for clauses supporting the recognition of these
CEs. The paths discovered during the search are
generalised into first-order clauses. Subsequently,
the weights of the clauses that pass the evaluation
stage are optimised using off-the-shelf online weight
learners. Then, the weighted clauses are appended
to the hypothesis and the procedure is repeated for
the next set of training examples Dt+1 .
OLED [11] is an Inductive Logic Programming
(ILP) system that learns CE patterns, in the form of
Event Calculus theories, in a supervised fashion and
in a single pass over a data stream. OLED constructs
patterns by first encoding a positive example from
the input stream into a so-called bottom rule, i.e.,
a most-specific rule of the form α ← δ1 ∧ . . . ∧ δn ,
where α is an initiation or termination atom and
δ1 , . . . , δn are relational features, constructed onthe-fly, using prescriptions from a predefined language bias. These features express anything “interesting”, as defined by the language bias, that is true
within the positive example at hand. A bottom rule
is typically too restrictive to be useful. To learn a
useful rule, OLED searches within the space of rules
that θ-subsume the bottom rule, i.e., rules that involve some of the δi ’s only. To that end, OLED starts
from the most-general rule—a rule with an empty
body—and gradually specialises that rule by adding
δi ’s to its body, using a rule evaluation function to
assess the quality of each generated specialisation.
OLED’s single-pass strategy is based on the Hoeffding bound [8], a statistical tool that allows to
approximate the quality of a rule on the entire input using only a subset of the data. In particular, given a rule r and some of its specialisations
r1 , . . . , rk , the Hoeffding bound allows to identify
the best among them, with probability 1−δ and
within an error margin , using only N = O( 12 ln 1δ )
training examples from the input stream.
We have evaluated OLED and OSLα on real
datasets concerning activity recognition, maritime
monitoring, credit card fraud detection, and traffic management in smart cities [11, 16, 3, 15, 12].
We have also compared OLED and OSLα to OSL [9],
XHAIL, a ‘batch’ structure learner requiring many
passes over the data [19], and to hand-curated Event
Calculus patterns (with optimised weight values).
The results suggest that both OLED and OSLα can
match the predictive accuracy of batch learners as
well as that of hand-crafted patterns. Moreover,
OLED and OSLα have proven significantly faster than
both batch and online learners, making them more
appropriate for large data streams.

a

EVENT FORECASTING

Forecasting over time-evolving data streams is a
task that can be defined in multiple ways. There
is a conceptual difference between forecasting and
prediction, as the latter term is understood in machine learning, where the main goal is to “predict”
the output of a function on previously unseen input data, even if there is no temporal dimension.
In forecasting, time is a crucial component and the
goal is to predict the temporally future output of
some function or the occurrence of an event. Timeseries forecasting is an example of the former case
and is a field with a significant history of contributions. However, its methods cannot be directly
transferred to CER, since it handles streams of
(mostly) real-valued variables and focuses on forecasting relatively simple patterns. On the contrary,
in CER we are also interested in categorical values, related through complex patterns and involving multiple variables. Our group has developed
a method, where automata and Markov chains are
employed in order to provide (future) time intervals
during which a match is expected with a probability
above a confidence threshold [1].
We start with a given pattern of interest, defining relations between events, in the form of a regular
expression—i.e., using operators for sequence, disjunction and iteration. Our goal, besides detecting
occurrences of this pattern, is also to estimate, at
each new event arrival, the number of future events
that we will need to wait for until the expression is
satisfied, and thus a match be detected. A pattern
in the form of a regular expression is first converted
to a deterministic finite automaton (DFA) through
standard conversion algorithms. We then construct
a Markov chain that will be able to provide a probabilistic description of the DFA’s run-time behavior,
by employing Pattern Markov Chains (PMC) [17].
The resulting PMC depends both on the initial pattern and on the assumptions made about the statistical properties of the input stream—the order m
of the assumed Markov process.
After constructing a PMC, we can use it to calculate the so-called waiting-time distributions, which
can give us the probability of reaching a final state
of the DFA in k transitions from now. To estimate
the final forecasts, another step is required, since
our aim is not to provide a single future point with
the highest probability, but an interval in the form
of I=(start, end ). The meaning of such an interval is that the DFA is expected to reach a final
state sometime in the future between start and end
with probability at least some constant threshold
θfc (provided by the user). An example is shown

a
a
start

a

0

1

b

2

b

b

3

4

a

b

b

(a) Deterministic Finite Automaton, state 1.
1

Completion Probability

5.

state:0
state:1
interval:3,8
state:2
state:3

0.8
0.6
0.4
0.2
0

1

2

3

4

5

6

7

8

9

10

11

12

Number of future events

(b) Waiting-time distribution, state 1.

Figure 3: Event Forecasting. The event pattern
requires that one event of type a is followed by three
events of type b. θf c = 0.5. For illustration, the x
axis stops at 12 future events.
in Figure 3, where the DFA in Figure 3a is in state
1, the waiting-time distributions for all of its nonfinal states are shown in Figure 3b, and the distribution, along with the forecast interval, for state 1
are shown in green.
Figure 4 shows results of our implementation on
two real-world datasets from the financial and the
maritime domains. In the former case, the goal
was to forecast a specific case of credit card fraud,
whereas in the latter it was to forecast a specific
vessel manoeuver. Figures 4a and 4d show precision
results (the percentage of forecasts that were accurate), where the y axes correspond to different values of the threshold θfc , and the x axes correspond
to states of the PMC (more “advanced” states are
to the right of the axis), i.e., we measure precision
for the forecasts produced by each individual state.
Similarly, Figures 4b and 4e are per-state plots for
spread (the length of the forecast interval), and Figures 4c and 4f are per-state plots for distance (the
temporal distance between the time a forecast is
produced and the start of the forecast interval).
As expected, more “advanced” states produce forecasts with higher precision, smaller spread and distance. However, there are cases where we can get
earlier both high precision and low spread scores
(see Figures 4d and 4e). This may happen when
there exist strong probabilistic dependencies in the
stream, e.g., when one event type is very likely (or

0.6

60

0.4

40
20

0.2

0.8

8

0.6

6

0.4

4
2

0.2

1 11 12 13 2 21 3

4

5

6

7

0

1 11 12 13 2 21 3

4

5

6

0

0

1 11 12 13 2 21 3

State

State

(b) Spread.

(c) Distance.

60

0.4

40
20

0.2
11 ts 13 gse 14 gsn 15 gsw 16 gss 17 gen 18 gew 19 ges 20 gee

0

0.8

300

5

6

7

250

0.6

200
150

0.4

100

0.2

50

15

Prediction Threshold

80

4

350

Prediction Threshold

Prediction Threshold

5

0.2

State

0.6

9 tn

0.4

7

100

7 tw

10

0.6

(a) Precision.

0.8

3 te

0.8

0

0

0

15

Prediction Threshold

80

10

Prediction Threshold

Prediction Threshold

100

0.8

0.8
10

0.6
0.4

5

0.2

0
3 te

7 tw

9 tn

11 ts 13 gse 14 gsn 15 gsw 16 gss 17 gen 18 gew 19 ges 20 gee

0
3 te

7 tw

9 tn

11 ts 13 gse 14 gsn 15 gsw 16 gss 17 gen 18 gew 19 ges 20 gee

State

State

State

(d) Precision.

(e) Spread.

(f) Distance.

Figure 4: Event forecasting for credit card fraud management (top) and maritime monitoring (bottom). The
y axes correspond to different values of the threshold θfc . The x axes correspond to states of the PMC.
very unlikely) to appear, given that the last event(s)
is of a different event type. Our system can take
advantage of such cases in order to produce highquality forecasts early.

6.

PARTICIPATION IN RESEARCH & INNOVATION PROJECTS

The CER group has been participating in several research and innovation projects, contributing
to the development of intelligent systems in challenging domains. SPEEDD2 (Scalable Proactive
Event-Driven Decision Making) was an FP7 EUfunded project, coordinated by the CER group, that
developed tools for proactive analytics in Big Data
applications. In SPEEDD, the CER group worked
on credit card fraud detection and traffic management [3, 15], developing formal tools for highly scalable CER [4], and pattern learning [10, 16].
REVEAL3 (REVEALing hidden concepts in social media) was an FP7 EU project that developed
techniques for real-time extraction of knowledge from
social media, including influence and reputation assessment. In REVEAL, the CER group developed a
technique for online (single-pass) learning of event
patterns under uncertainty [11].
datACRON4 (Big Data Analytics for Time Crit2

http://speedd-project.eu/
3
http://revealproject.eu/
4
http://www.datacron-project.eu/

ical Mobility Forecasting) is an H2020 EU project
that introduces novel methods for detecting threats
and abnormal activity in very large fleets of moving entities, such as vessels and aircrafts. Similarly, AMINESS5 (Analysis of Marine Information
for Environmentally Safe Shipping) was a national
project that developed a computational framework
for environmental safety and cost reduction in the
maritime domain. The CER group has been working on maritime and aviation surveillance, developing algorithms for, among others, highly efficient
spatio-temporal pattern matching [18], complex
event forecasting [1], and parallel online learning
of complex event patterns [12].
Track & Know (Big Data for Mobility & Tracking Knowledge Extraction in Urban Areas) is an
H2020 EU-funded project that will research, develop and exploit a new software framework increasing the efficiency of Big Data applications in the
transport, mobility, motor insurance and health sectors. The CER team is responsible for the complex
event recognition and forecasting technology that
will be developed in Track & Know.

7.

CONTRIBUTIONS TO THE COMMUNITY

The CER group supports the research community at different levels; notably, by making avail5

http://aminess.eu/

able the proposed research methods as open-source
solutions. The RTEC CER engine (see Section 2)
is available as a monolithic Prolog implementation6
and as a parallel Scala implementation7 . The OLED
system for online learning of event patterns (see Section 4) is also available as an open-source solution8 ,
both for single-core and parallel learning. OLED is
implemented in Scala; both OLED and RTEC use
the Akka actors library for parallel processing.
The OSLα online learner (see Section 4), along
with MAP inference based on integer linear programming, and various weight optimisation algorithms (Max-Margin, CDA and AdaGrad), are contributed to LoMRF9 , an open-source implementation of Markov Logic Networks. LoMRF provides
predicate completion, clausal form transformation,
and function elimination. Moreover, it provides a
parallel grounding algorithm which efficiently constructs the minimal Markov Random Field.

8.

REFERENCES

[1] E. Alevizos, A. Artikis, and G. Paliouras.
Event forecasting with pattern markov chains.
In DEBS, pages 146–157. ACM, 2017.
[2] E. Alevizos, A. Skarlatidis, A. Artikis, and
G. Paliouras. Probabilistic complex event
recognition: A survey. ACM Comput. Surv.,
50(5):71:1–71:31, 2017.
[3] A. Artikis, N. Katzouris, I. Correia, C. Baber,
N. Morar, I. Skarbovsky, F. Fournier, and
G. Paliouras. A prototype for credit card
fraud management: Industry paper. In DEBS,
pages 249–260, 2017.
[4] A. Artikis, M. J. Sergot, and G. Paliouras. An
event calculus for event recognition. IEEE
TKDE, 27(4):895–908, 2015.
[5] A. Artikis, M. Weidlich, F. Schnitzler,
I. Boutsis, T. Liebig, N. Piatkowski,
C. Bockermann, K. Morik, V. Kalogeraki,
J. Marecek, A. Gal, S. Mannor, D. Gunopulos,
and D. Kinane. Heterogeneous stream
processing and crowdsourcing for urban traffic
management. In EDBT, pages 712–723, 2014.
[6] G. Cugola and A. Margara. Processing flows
of information: From data stream to complex
event processing. ACM Comput. Surv.,
44(3):15:1–15:62, 2012.
[7] N. Giatrakos, A. Artikis, A. Deligiannakis,
and M. N. Garofalakis. Complex event
recognition in the big data era. PVLDB,
6

https://github.com/aartikis/RTEC
https://github.com/kontopoulos/ScaRTEC
8
https://github.com/nkatzz/OLED
9
https://github.com/anskarl/LoMRF
7

10(12):1996–1999, 2017.
[8] W. Hoeffding. Probability inequalities for
sums of bounded random variables. JASA,
58(301):13–30, 1963.
[9] T. N. Huynh and R. J. Mooney. Online
Structure Learning for Markov Logic
Networks. In ECML, pages 81–96, 2011.
[10] N. Katzouris, A. Artikis, and G. Paliouras.
Incremental learning of event definitions with
inductive logic programming. Machine
Learning, 100(2-3):555–585, 2015.
[11] N. Katzouris, A. Artikis, and G. Paliouras.
Online learning of event definitions. TPLP,
16(5-6):817–833, 2016.
[12] N. Katzouris, A. Artikis, and G. Paliouras.
Parallel online learning of complex event
definitions. In ILP. Springer, 2017.
[13] A. Kimmig, B. Demoen, L. D. Raedt,
V. Costa, and R. Rocha. On the
implementation of the probabilistic logic
programming language ProbLog. TPLP,
11(2-3):235–262, 2011.
[14] R. A. Kowalski and M. J. Sergot. A
logic-based calculus of events. New
Generation Comput., 4(1):67–95, 1986.
[15] E. Michelioudakis, A. Artikis, and
G. Paliouras. Online structure learning for
traffic management. In ILP. Springer, 2016.
[16] E. Michelioudakis, A. Skarlatidis,
G. Paliouras, and A. Artikis. Online structure
learning using background knowledge
axiomatization. In ECML, 2016.
[17] G. Nuel. Pattern Markov Chains: Optimal
Markov Chain Embedding through
Deterministic Finite Automata. Journal of
Applied Probability, 2008.
[18] K. Patroumpas, E. Alevizos, A. Artikis,
M. Vodas, N. Pelekis, and Y. Theodoridis.
Online event recognition from moving vessel
trajectories. GeoInformatica, 21(2), 2017.
[19] O. Ray. Nonmonotonic abductive inductive
learning. JAL, 7(3):329–340, 2009.
[20] M. Richardson and P. M. Domingos. Markov
logic networks. Machine Learning,
62(1-2):107–136, 2006.
[21] A. Skarlatidis, A. Artikis, J. Filipou, and
G. Paliouras. A probabilistic logic
programming event calculus. TPLP,
15(2):213–245, 2015.
[22] A. Skarlatidis, G. Paliouras, A. Artikis, and
G. A. Vouros. Probabilistic Event Calculus for
Event Recognition. ACM Transactions on
Computational Logic, 16(2):11:1–11:37, 2015.

