A Genetic Algorithm to Discover Flexible Motifs
with Support
Joan Serrà∗ , Aleksandar Matic∗ , Josep Lluis Arcos† , and Alexandros Karatzoglou∗

arXiv:1511.04986v4 [cs.LG] 5 Dec 2016

∗ Telefónica

Research, Barcelona, Spain. Email: firstname.lastname@telefonica.com
† IIIA-CSIC, Bellaterra, Spain. Email: arcos@iiia.csic.es

Abstract—Finding repeated patterns or motifs in a time series
is an important unsupervised task that has still a number of
open issues, starting by the definition of motif. In this paper, we
revise the notion of motif support, characterizing it as the number
of patterns or repetitions that define a motif. We then propose
GENMOTIF, a genetic algorithm to discover motifs with support
which, at the same time, is flexible enough to accommodate
other motif specifications and task characteristics. GENMOTIF
is an anytime algorithm that easily adapts to many situations:
searching in a range of segment lengths, applying uniform scaling,
dealing with multiple dimensions, using different similarity and
grouping criteria, etc. GENMOTIF is also parameter-friendly:
it has only two intuitive parameters which, if set within reasonable bounds, do not substantially affect its performance. We
demonstrate the value of our approach in a number of synthetic
and real-world settings, considering traffic volume measurements,
accelerometer signals, and telephone call records.

I.

INTRODUCTION

Discovering repeated short-length segments, commonly
called motifs, in a time series is a fundamental task that has a
number of important applications. Beyond data exploration and
assessment, motif discovery is often a key component of many
higher-level algorithms [1], both of supervised and unsupervised nature. Due to this importance, a myriad of approaches
have been proposed. Today, these can be categorized from
different perspectives or dimensions, starting by the definition
of a motif.
There are four main aspects that define a time series
motif [1]: (a) the relative position of the segments, (b) the
similarity between segments, (c) the length of the segments,
and (d) the support of the motif. To determine (a), pioneering approaches used approximate representations of the
time series, defined a fixed segment length, and chose a
static threshold to distinguish between similar and dissimilar
segments [2], [3]. Such approximate approaches have proven
to be suitable in a number of applications, thus the work in
this domain has continued until today [4]–[6]. However, socalled exact algorithms were recently introduced [7] which,
while being as efficient as some approximate ones, deal with
the raw time series and do not require a similarity threshold.
More recently, further developments have allowed to work with
a range of segment lengths [8], [9], thus reducing the constraint
of specifying a fixed value for such a crucial parameter.
Out of the four previous aspects, the introduction of the
notion of motif support (d) remains the most elusive one.
The current definitions of exact-based motifs are typically
rooted on segment pairs [7]. Yet there is no specific reason for
constraining the definition of a motif to segment pairs. The
alternative definition may be based on groups of segments,

where the number of segments s represents the support of
the motif. This way, a definition based on segment pairs
becomes just a special case in which s = 2. Conceptually,
this notion of motif support starts bridging the gap between
motif discovery and subsequence time series clustering [10].
Practically, the introduction of support allows focusing on
more frequent segments that occur at least s times in a time
series. Furthermore, it can contribute to obtain a more robust
motif, as s similar segments need to be combined to derive
one motif.
In addition to the above-mentioned aspects, there are a
number of known open issues in time series motif discovery,
and in exact motif discovery in particular [1]. These include
discovering repeated warped segments [11], finding motifs under complexity invariance [12] or uniform scaling [13], multiand sub-dimensional motif discovery [14], and algorithms that
can work in anytime mode [9]. To the best of our knowledge,
existing approaches address one or, at most, two of such open
issues, with different tradeoffs and varying degrees of success.
Moreover, they typically require to set a number of parameters.
The only exception is SWARMMOTIF [15], which adapts a
specific metaheuristic [16], particle swarm optimization [17],
to the task of time series motif discovery. Such adaptations can
lead to very flexible algorithms that are able to tackle most of
the previous issues at the same time [15]. We here consider
an alternative metaheuristic adaptation that, in addition, goes
beyond previous works by incorporating a novel notion of
motif support in its formulation.
In this paper, we present GENMOTIF, an approach that is
based on the adaptation of genetic algorithms [18] to the task of
time series motif discovery. The main individual contributions
of our approach are summarized below. However, we believe
that it is the combination of such contributions what makes
GENMOTIF a unique and novel algorithm for time series motif
discovery:
•

It explicitly involves a new notion of motif support.
As mentioned, this is a natural step that has both
conceptual as well as practical benefits.

•

It is an anytime algorithm. As with all genetic algorithms, an approximation to the final solution is
incrementally refined with time.

•

It does not oblige the practitioner to specify an exact
segment length, which in many cases can be problematic.

•

It performs uniform scaling of the segments that form
a motif. This has been shown to be a desirable quality
in a number of practical situations [13].

•

It allows to analyze multi-dimensional time series.

•

It is dissimilarity-agnostic. Its formulation is independent of the measurement used to assess segment
similarity. This implies that we can measure segment
similarity with, for example, dynamic time warping,
or incorporate notions of complexity-invariance, if
needed.

•

It has only two parameters, which we show do not
substantially affect its performance, provided that they
are set within reasonable bounds.

We highlight the utility of GENMOTIF with one synthetic and
three real-world case studies. We also stress its novelty by performing a qualitative comparison with the most conceptually
closest approaches in the literature. Except for one case study,
we employ publicly-available data sets, and make all our code
available online1 to foster reproducibility and to promote the
usage of the algorithm in further scientific domains.
The remainder of the paper is structured as follows. We
first formulate the notion of motif support and introduce
the necessary notation. We then detail the implementation of
GENMOTIF. Next, we experimentally evaluate its performance
and show two use cases that highlight its value. We also
qualitatively compare GENMOTIF with the state-of-the-art.
Finally, we summarize our contributions.
II.

PROBLEM DEFINITION AND NOTATION:
MOTIFS WITH SUPPORT

Consider a time series z = [z1 , . . . zn ] of length n. Given
a range of segment lengths of interest l ∈ [lmin , lmax ], l  n,
we want to find a set of k motifs M = {m1 , . . . mk } with a
support of s each. This means that a motif mi is derived from s
segments x contained in z. A segment x = [x1 , . . . xl ] is a small
slice of z, that is, [x1 , . . . xl ] = [zi+1 , . . . zi+l ], 0 ≤ i ≤ n − l.
In order to avoid trivial matches [3], the considered segments
should preferably be non-overlapping, although some percent
of overlap could be also tolerated [8]. Thus, a solution to the
task is a set of ks segments X = {x1 , . . . xks }, where k nonintersecting groups of s segments each define a motif mi . That
is, X = {X1 , . . . Xk }, Xi = {xu+1 , . . . xu+s }, u = s(i − 1),
Xi ∩ Xj = ∅.
There are several ways in which a group of segments Xi
can define a motif mi , and these depend on the dissimilarity
space and the central tendency measure chosen. Intuitively,
mi should be a good representative of Xi . Therefore, the
motif mi should be ‘very close’ to all s segments in Xi ,
according to a given dissimilarity measure. If we consider the
Euclidean distance as the dissimilarity measure and the mean
as a measure of central tendency, we can define
mi =

1 X
xu .
s

u6=u∗

The only requirement is that all segments xu are of equal
length, which we can fulfill by simply upsampling to the
largest length or by any other interpolation criterion. On a
more general case, given an arbitrary dissimilarity measure
between segments xu and xv , D(xu , xv ), we can obtain mi by

xu ⊂Xi

It can be noted that with motif definitions in Eqs. 1 and 2,
there is an analogy between finding k motifs with support and,
respectively, k-means or k-medoids clustering [19]. However,
there is an important difference: we do not cluster all available
data; only ks short-length time series segments are considered.
This can yield important speedups in terms of computation
time, as we only consider a small part of all available segments,
kslmax  n.
The previous definitions match our intuition that a motif
mi should be ‘very close’ to all segments in Xi . However,
there is another important factor that we may want to impose:
the fact that motifs in M are maximally dissimilar between
themselves. This will prevent the discovery of the same motif
twice. To enforce the closeness of motifs’ supports and, at
the same time, the dissimilarity between different motifs,
we can resort to existing clustering evaluation measures. For
instance, we can consider the Davies-Bouldin index [20]
or the silhouette coefficient [21], which are both measures
that take into account intra-cluster variance and inter-cluster
dissimilarity [19]. Following our notation, the Davies-Bouldin
index corresponds to


k
1X
R(mi , Xi ) + R(mj , Xj )
IDB (X ) =
max
, (3)
k i=1 1≤j≤k
D(mi , mj )
i6=j

and the silhouette index corresponds to
ks
1 X R(xu , X \ Xi ) − R(xu , Xi )
, (4)
IS (X ) = 1 −
ks u=1 max(R(xu , Xi ), R(xu , X \ Xi ))

where
R(y, X ) =

1 X
D(y, xu )
|X |
xu ⊂X

and, in Eq. 4, Xi denotes the set that contains xu . Note that IDB
makes explicit use of the concept of central tendency, while IS
does not. Thus, depending on the dissimilarity measure used,
one might be more appropriate than the other2 .
Overall, finding k motifs with s support is a combinatorial
problem. A solution consists of ks segments, and if we have
a time series of length n and a range of segment lengths
r = lmax + 1 − lmin , a brute-force search needs to examine,
(nr)!
nr
roughly, Cks
= (ks)!(nr−ks)!
combinations. This, for a very
small application involving n = 10 000, r = 100, k = 2, and
s = 5, already yields over 2.7 · 1053 possibilities3 .
III.

(1)

xu ⊂Xi

1 https://github.com/joansj/genmotif

considering the medoid of Xi , which we denote by xu∗ :
!
X
∗
mi = xu∗ | u = arg min
D(xu , xu∗ ) . (2)

GENMOTIF

A. Background
In the following, we present our proposed approach,
GENMOTIF, which is based on genetic algorithms. Genetic
algorithms have a long tradition in solving combinatorial
2 Notice however that I still requires some measure of central tendency to
S
extract mi in a final stage.
3 As a curiosity, we find there are about 1.33 · 1050 atoms in the world:
http://education.jlab.org/qa/mathatom 05.html.

optimization problems [18] as the one we face here. They are
population-based metaheuristics [16] that iterate an initial pool
of solutions, improving a user-defined fitness criterion in every
iteration. Genetic algorithms are known to yield good solutions
with very few iterations, although it may take them much
more to arrive at the global best solution possible. In some
variants, such global best solution is proven to be reached,
although no finite bound on the number of iterations can be
established [22]. Thus, in essence, they can be seen as anytime
algorithms [23]. In a wider sense, metaheuristics have been
recently introduced to the task of motif discovery, bringing in
a high degree of flexibility with regards to the definition of the
motif [15]. Such flexibility relies on the ability of metaheuristics to search complex, non-differentiable, discrete solution
spaces under incomplete or imperfect information [16].

Algorithm 1 G(z, X, lmax , s)

B. Solutions’ mapping and fitness

C. Main algorithm

Before delving into the description of the approach, we
first need to adapt the formulation of genetic algorithms
to the specific problem of time series motif discovery. In
genetic algorithms, a solution X has a set of properties,
commonly called genes or genotypes, which can be combined
and mutated. We propose to map X = {x1 , . . . xks } as a
set of tuples X = {X1 , . . . Xks } such that Xi = {f, l, c},
where f is the index of the first sample of the time series
segment, l is the length of the segment, and c is a real-valued
indicator that will be used to determine the index of the motif
to which the segment belongs to. Therefore, f ∈ [1, n − l],
l ∈ [lmin , lmax ], and c ∈ [0, 1). Note that Xi represents a time
series segment regardless of its dimensionality, thus fitting it
to multidimensional time series is directly applicable.

We are now ready to describe the main algorithm in
GENMOTIF (Algorithm 2). GENMOTIF is an instance of
a canonical genetic algorithm [16]. However, it incorporates
a basic form of elitism, performs a uniform crossover, and
employs a convolutional mutation operator [18]. In addition,
it incorporates all the necessary adaptations to work with time
series and time series segments. As an input, it takes a time
series z, together with the minimum and maximum segment
lengths of interest lmin and lmax , the number of desired motifs
k, and their support s. Its output represents the best solution X
found in the available execution time tmax . Note that all these
variables are not parameters of the algorithm, but requirements
of the task. With respect to the parameters, GENMOTIF
requires only the population size ρ and the mutation deviation
constant σ to be externally set. We will detail their use and
study their effect below.

Once we have an encoding for our solutions X, we need to
specify the mapping from X to X and the criterion that will be
used to evaluate the goodness of a solution X (Algorithm 1).
We initiate the process by verifying that X is a valid solution
(line 1). To do so, we loop over all the elements of X and
check if they overlap with any other element in X. In such
case, we conclude that X is not a valid solution and return
the value of ∞ (line 2), which is the worst possible value for
a solution, as we will try to minimize G (see below). If that
is not the case, we proceed to copy the ks segments defined
by X to the array X and upsample them to lmax samples
(line 3). For the latter we employ linear interpolation, but any
other strategy would be applicable, depending on the domain.
We next z-normalize each segment (line 4). Note that this step
can be safely skipped if the motif definition does not include
such a constraint. After that, we get all motif group indicators
contained in X (line 5): c = {c1 , . . . cks }, where ci corresponds
to the third element of the tuple Xi . We then compute the
indices o that sort c in increasing order (line 6). With o and s,
we can then group the segments in X so that each group
has a direct correspondence to a motif (line 7). To do so,
we take every s consecutive indices in o and form k groups
Xi , i = 1, . . . k. Specifically, Xi = {xu , . . . xv }, where u =
os(i−1)+1 and v = osi . Finally, we compute the goodness of the
solution (line 8) by applying a criterion of choice, as explained
above. If not stated otherwise, we here use the Davies-Bouldin
index (Eq. 3) for I, the squared Euclidean distance between
z-normalized segments, and the mean as a measure of central
tendency (Eq. 1). Note that nothing prevents us from using
another dissimilarity measurement or clustering index.

Input: A time series z, a solution X, the maximum length of
the segments lmax , and the motif support s.
Output: A goodness value g (the lower, the better).
1:
2:
3:
4:
5:
6:
7:
8:

if S OME OVERLAP(X)
return ∞
X ← C OPYA ND U PSAMPLE S EGMENTS(z, X, lmax )
X ← ZN ORMALIZE S EGMENTS(X )
c ← G ET M OTIF I NDICATORS(X)
o ← arg sort (c)
X ← G ROUP S EGMENTS(X , o, s)
return I(X )

GENMOTIF starts by setting a new population of solutions
P of size ρ, P = {X1 , . . . Xρ }, where ρ is an odd integer such
that ρ ≥ 3 (Algorithm 2, lines 1–4). To instantiate a new
solution Xi (line 3), we sample the search space uniformly at
random. For Xi to be a valid solution, the sampling needs
to be performed between reasonable limits, while avoiding
potential segment overlaps (Algorithm 3). To sample the
search space we use a uniform real random number generator
U (a, b) ∈ [a, b) and the floor operator b c. After computing the
initial set of solutions P, we enter an infinite loop (Algorithm 2,
lines 5–21). This is the loop that will evolve the solutions in
the population. It performs three main operations: (a) selecting
the best fit solution, (b) checking execution time, and (c)
constructing a new population.
For selecting the best solution (lines 6–11), we just compute the goodness value G as explained before (line 8; see
Algorithm 1) and keep the index ibest of the solution that has
the minimum value (line 11). Once all ρ solutions have been
examined, we check the set time constraint tmax (lines 12–13).
If the remaining time does not permit the new iteration, we
return the best individual found until that point, Xibest (line 13).
Alternatively, if there is time left, we continue by constructing
a new population Pnew (lines 14–20) and replacing P with
this new population (line 21). Importantly, Pnew keeps the best
solution found at every iteration, unaltered (line 14). This is
the simplest form of elitism possible [16], and the minimum
requirement for the global convergence of the algorithm [22].
The construction of Pnew continues by uniformly sampling two

Algorithm 2 GENMOTIF(z, lmin , lmax , k, s, tmax )

Algorithm 4 C ROSSOVER(Xi , Xj , ks)

Input: Time series z of length n, minimum and maximum
length of segments lmin and lmax , number of motifs k,
motif support s, and maximum execution time tmax .
Require: Setting the size of the population ρ and a mutation
deviation constant σ.
Output: Best solution found X.

Input: Two solutions Xi , Xj and number of segments ks.
Output: Solutions Xi and Xj with some genes crossed.

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

P←∅
for i = 1, . . . ρ
Xi ← N EW S OLUTION(n, lmin , lmax , ks)
P ← P ∪ {Xi }
loop
gbest ← ∞
for Xi in P
g ← G(z, Xi , lmax , s)
if g < gbest
gbest ← g
ibest ← i
if O UT O F T IME(tmax )
return Xibest
Pnew ← {Xibest }
for u = 1, . . . (ρ − 1)/2
Xi , Xj ← C HOOSE A ND C OPY(P)
Xi , Xj ← C ROSSOVER(Xi , Xj , ks)
Xi ← M UTATION(Xi , σ, n, lmin , lmax , ks)
Xj ← M UTATION(Xj , σ, n, lmin , lmax , ks)
Pnew ← Pnew ∪ {Xi , Xj }
P ← Pnew

Algorithm 3 N EW S OLUTION(n, lmin , lmax , ks)
Input: Length of the series n, minimum and maximum segment lengths lmin and lmax , and number of segments ks.
Output: A valid solution X.
1:
2:
3:
4:
5:
6:
7:
8:
9:

X←∅
while I S E MPTY(X) or S OME OVERLAP(X)
X←∅
for i = 1, . . . ks
c ← U (0, 1)
l ← bU (lmin , lmax + 1)c
f ← bU (1, n − l + 1)c
X ← X ∪ {f, l, c}
return X

individuals Xi , Xj with replacement from P, and returning
a copy of them (line 16). Next, we cross their genes by
uniform crossover (line 17) and mutate their genes according
to a mutation factor σ (lines 18–19). Finally, Xi and Xj are
appended to Pnew (line 20).
The crossover and mutation operators require a careful
design consideration. In GENMOTIF, we opted for a uniform
crossover with a fixed low probability (Algorithm 4). With
probability 1/ks (line 2), we swap the u-th segments of the
two solutions (line 3). Similarly, for the mutation operator, with
probability 1/ks (line 3), we mutate a segment u (lines 4–8).
To do so, we follow a convolutional process (Algorithm 5). At
the end of the mutation operation, we shuffle the segments in
X to favor the exploration of the search space (line 9). In preanalysis, we found this shuffling operation to have a marginal

1:
2:
3:
4:

for Xiu , Xju in Xi , Xj
if U (0, 1) < 1/ks
S WAP(Xiu , Xju )
return Xi , Xj

Algorithm 5 M UTATION(X, σ, n, lmin , lmax , ks)
Input: Solution X, mutation parameter σ, length of the time
series n, minimum and maximum segment length lmin and
lmax , and number of segments ks.
Output: A mutation of the solution X.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

r ← lmax + 1 − lmin
for Xu in X
if U (0, 1) < 1/ks
f, l, c ← Xu
c ← mod (c + σC(0, 1), 1)
l ← mod (l + bσrC(0, 1)e − lmin , r + 1) + lmin
f ← mod (f + bσ(n − l)C(0, 1)e, n − l + 1)
Xu ← {f, l, c}
S HUFFLE(X)
return X

but positive impact to the fitness of the found solutions, in
particular for short execution times.
To mutate the values f , l, and c, we employ a real random
number generator following the standard Cauchy distribution
C(0, 1), which has the location and scale parameters set to
0 and 1, respectively. The Cauchy distribution is a heavytailed distribution, with undefined mean and variance. It can be
considered to be a special case of the more general Lévy flight
distribution. Lévy flight distributions have been suggested
to be beneficial for optimization-based metaheuristics when
searching large spaces, as very long jumps can be performed
after many small ones [24]. Moreover, a Lévy flight strategy
is reported to be an efficient statistical strategy for searching
randomly located, sparse objects [25]. In the absence of a priori
knowledge about the distribution of the targets, the case
corresponding to the Cauchy distribution has been shown to
be the optimal search strategy [25].
To compute C(0, 1), we just divide two real random numbers taken from the normal distribution with zero mean and
unit variance, N (0, 1), such that C(0, 1) = N (0, 1)/ |N (0, 1)|,
where | | indicates absolute value. We then rescale C(0, 1)
by the ranges of the corresponding variables (Algorithm 5,
lines 5–7) and control the mutation variability by the parameter
σ. We additionally employ the round to the nearest integer
operator b e where needed and control the limits of the mutated
variables with the modulo operator mod().
IV.

EXPERIMENTAL VALIDATION

In this section, we evaluate GENMOTIF experimentally.
We start with a sanity check by a planted motif problem. We
then study the influence of the two parameters of the algorithm.
We run all our experiments on a 4 GB RAM laptop with a
dual core processor at 2.5 GHz. The only exception are the

Value

1.5
1.0
0.5
0.0
0.5
1.0
1.5

5
4
3
2
1
0
1
2
0

500

1000

Sample

1500

2000

Fig. 1. First samples of the random walk time series with planted square
wave motifs. In this and subsequent time series plots, horizontal and vertical
axes correspond to samples and values, respectively.

parameter setting experiments, which were run on a 15 GB
RAM machine with 24 cores at 2 GHz. Except for the planted
motif time series, which are artificially generated, all data sets
used in this section are publicly-available.

2.0
1.5
1.0
0.5
0.0
0.5
1.0
1.5
2.0

A

0

10

20

30

40

50

0

10

20

30

40

50

60

C

60

1.5
1.0
0.5
0.0
0.5
1.0
1.5
2.0
1.5
1.0
0.5
0.0
0.5
1.0
1.5
2.0

B

0

10

20

30

40

50

0

10

20

30

40

50

60

D

60

Fig. 2. Solution found in the planted motif random walk time series after
a two minutes run. Motifs A and B correspond to the planted motifs, while
motifs C and D are two motifs that are expected to be found in a sufficiently
long random walk time series.

10 1

A. Planted motifs

The results after two minutes computation time4 are already
satisfactory (Fig. 2). The algorithm is able to discover the two
planted motifs (motifs A and B) and also two clear patterns
that are trivially present in the random walk time series (motifs
C and D). The lengths for the supports of motifs A and B are
found to be between 52 and 60 samples. However, upsampling
to the largest length found in the motif supports results in motif
A having a length of 58 and motif B having a length of 60,
the former being the original motif length and the latter being
very close to it. We can also witness that motif B is not already
centered to its most optimal value. This is a typical outcome
when running time is relatively short and which improves as
time progresses5 . Note, however, that this fact does not prevent
the practitioner to ‘discover’ the two originally planted motifs.
Given the anytime nature of the proposed algorithm, it is
worth studying its convergence as execution time progresses.
To do so, we analyze the goodness of fit index IDB as a function
of the execution time t (Fig. 3). In addition, we compare it
with the IDB obtained by a simple random search strategy
that uniformly samples the search space at every iteration.
We see that both GENMOTIF and random search strategies
improve the solution fitness with t. However, GENMOTIF
performs considerably faster (notice the double logarithmic
axes). Specifically, we see that the prediction intervals of the
solutions found by the two approaches do not overlap after
100 ms. This difference steadily increases with t and, after
100 s, it goes up to two orders of magnitude (Fig. 3).
4 We run all experiments on a single core at 2.5 GHz except the parameter
setting experiments, using single cores of 2 GHz.
5 It should be mentioned that, with an execution time of 1 min, such motifs
were already visible, although with a different centering and with less defined
supports.

10 0

IDB

We first consider a planted motif task where motifs have
been downsampled uniformly at random to, at most, 90% of
their original length. We insert two different patterns corresponding to a square wave of length 58 in a random walk
time series generated by xi = xi−1 + N (0, 0.1) with x0 = 0
(Fig. 1). We arbitrarily consider 50 downsampled repetitions
for each pattern and force that they represent only 10% of the
total length of the time series, which results in 58 000 samples.
We then run GENMOTIF to find 4 motifs with a support of 5
and lengths between 50 and 60 samples.

10 -1

10 -2

Random search
GENMOTIF
10 -2

10 -1

10 0

t [s]

10 1

10 2

Fig. 3. Solution fitness IDB as a function of execution time t. The dashed
black line corresponds to a random search strategy and the solid blue line
corresponds to GENMOTIF. The shaded regions correspond to 95% prediction
intervals. Notice the double logarithmic axes.

B. Parameter setting
In the following, we study the impact that the population
size ρ and the mutation deviation constant σ make on the
goodness of the solutions obtained by GENMOTIF. We start
by setting ρ = 51 and computing IDB as a function of time
for σ = {10−5 , 10−4 , 10−3 , 10−2 , 10−1 , 1} (Fig. 4). We first
consider the EEG time series from [7] and search for 10 motifs
with a support of 5 with lengths between 150 and 250 samples.
We see that the prediction intervals for the majority of the
considered σ values highly overlap, with σ ∈ [10−1 , 10−3 ]
yielding only slightly better results than σ values outside
this range. We also see that σ = 10−5 yields the worst
performance, with a prediction interval that does not overlap
with the ones of the other σ values obtained for approximately
t > 5 min.
We repeated the experiment with the 9 time series and
motif lengths considered in [15], and obtained similar results
to the ones of the previous paragraph. In general, a value
of σ = 10−2 is expected to yield the best performance
in the big majority of the cases, with σ = 10−3 typically
performing almost as good as σ = 10−2 . Interestingly, the
value of σ = 10−2 is the default scaling value used in
other studies employing Lévy flight distributions for alternative
metaheuristic algorithms [24]. Thus, the σ value we find in our

IDB

10 1

genetic algorithm requires; and increasing the population size
is an elementary way of increasing exploration [18]. However,
as prediction intervals were found to be highly overlapping,
we are not in a position to draw any strong statement in this
regard.

10 0

V.

σ=1
σ = 10 −1
σ = 10 −2
σ = 10 −3
σ = 10 −4
σ = 10 −5

10 -1
10 -1

10 0

10 1

t [s]

10 2

10 3

10 4

Fig. 4. Solution fitness IDB as a function of execution time t, considering
different values of σ and using the EEG time series from [7]. The shaded
regions correspond to 95% prediction intervals. Notice the double logarithmic
axes.

IDB

γ = 15
γ = 25
γ = 51
γ = 101
γ = 201
10 -1

In this section, we demonstrate the usage of GENMOTIF in
three different real-world scenarios that have already attracted
the attention of the scientific community. The case studies
shown here are not designed to claim results in their respective
domains. Instead, they illustrate the applicability and the values
of GENMOTIF in such domains. We consider tree types of
signals: traffic volume, accelerometer, and telephone call data.
The first two data sets are publicly-available while the third
one is not open to the public for data proprietary reasons.
A. Traffic volume patterns
Traffic patterns and mobility of people in general is an
important variable to consider in epidemics spread modeling,
road dimensioning, and path optimization, to name a few.
Therefore, timely modeling of traffic patterns is an area of
paramount importance for both public and private sectors. To
illustrate GENMOTIF’s performance and versatility, we use
the vehicle counts measured every 5 min using an on-ramp
sensor on the 101 freeway in Los Angeles, located near the
Dodger Stadium, where the Los Angeles Dodgers baseball
team plays their home games [26]. Our goal is to evaluate
how well GENMOTIF is able to identify objectively-relevant
motifs in a real-world time series of 50 400 samples.

10 1

10 0

CASE STUDIES

10 0

10 1

t [s]

10 2

10 3

10 4

Fig. 5. Solution fitness IDB as a function of execution time t, considering
different values of ρ and using the long Insect time series from [7]. The shaded
regions correspond to 95% prediction intervals. Notice the double logarithmic
axes.

experiments is consistent with current practice. This suggests
a potentially optimal setting for these type of distributions that
could be further investigated in future works and optimization
scenarios.
We now focus on the analysis of the population size ρ.
We set σ = 10−2 and compute IDB as a function of time for
ρ = {15, 25, 51, 101, 201} (Fig. 5). We first consider the long
Insect time series from [7] and search for 10 motifs with a
support of 5 with lengths between 300 and 500 samples. We
see that, in this case, the overlap between prediction intervals
becomes considerable. This suggests that ρ has less overall
effect than σ, and therefore that its setting can be less precise.
We again repeated the experiment with the 9 time series
and motif lengths considered in [15], and obtained qualitatively
similar results to the ones of the previous paragraph. We
witnessed a minor tendency towards small population sizes
(e.g., 15 or 25 individuals) for short running times (e.g., 1 hour)
and larger population sizes (e.g., 51 or 101 individuals) for
longer running times. Such an outcome is theoretically plausible, considering the fact that the larger the search space and
the available time, the larger the exploration capabilities that a

We use the data available in the UCI archive6 [26] and
run GENMOTIF for 10 min, searching for 10 motifs with
a support of 5 and lengths between 276 and 300 samples
(corresponding to 23 and 25 hours, respectively). Among the
identified motifs, four patterns clearly stand out (Fig. 6).
By knowing the context of the patterns (the date and the
stadium events), these four patterns have straightforward and
meaningful interpretations. Firstly, it is possible to clearly
differentiate between working day patterns (motifs A and C)
and weekend day patterns (motifs B and D). Moreover, these
patterns additionally differ depending on whether the Dodgers
played in their stadium (motifs C and D) or not (motifs A
and B). The UCI archive documentation further contributes to
understanding the relevance of this result, as it states that the
sensor “is close enough to the stadium to see unusual traffic
after a Dodgers game, but not so close and heavily used by
game traffic so that the signal for the extra traffic is overly
obvious”.
B. Person verification using accelerometer data
Finding patterns in accelerometer data is an important
research area with a wide applicability that spans from user
interaction and activity tracking to health care assessment
and biometric authentication. The accelerometer signal is a
time series with a sampling rate that varies with the application: from 10–20 Hz for phone interaction applications to,
for instance, 500–1000 Hz for detecting anomalies in engines.
In our example, we apply GENMOTIF to the data captured
from a single chest accelerometer with the objective of person
6 https://archive.ics.uci.edu/ml/datasets/Dodgers+Loop+Sensor

3
2
1
0
1
2
3
2
1
0
1
2

A

0

50

100 150 200 250 300

0

50

100 150 200 250 300

C

3
2
1
0
1
2
3
2
1
0
1
2

B

0

50

100 150 200 250 300

0

50

100 150 200 250 300

D

Fig. 6.
Four motifs found in the traffic volume data used in [26] by
GENMOTIF. Motifs A and B correspond to the typical traffic volume patterns
of a work day and a weekend day, respectively. Motifs C and D correspond to
the same situation, respectively, but when there is a match taking place. The
solid black curve depicts the average of the motif supports.

A

3
2
1
0
1
2
3
2
1
0
1
2

0

20

40

60

80

100

0

20

40

60

80

100

C

B

3
2
1
0
1
2
3
2
1
0
1
2

0

20

40

60

80

100

0

20

40

60

80

100

D

Fig. 7. Four motifs found in the single chest accelerometer data from [27].
Motifs A, B, C, and D correspond to four different people. The solid black
curve depicts the average of the motif supports.

verification [27]. Our goal is to find characteristic patterns for
different persons in a time series of near 2 million samples that
features 52 Hz recordings of the daily activities of 15 people
including walking, talking, or working on a computer.
We use the data available in the UCI archive7 [27]. We
compute the modulus of the three acceleration coordinates and
concatenate all signals from the 15 participants in a single time
series. We then run GENMOTIF for a maximum execution
time of over an hour, looking for 20 motifs with a support of 5
and lengths between 100 and 108 samples (around 1 s). Among
the motifs found, we could clearly observe a number of personcharacteristic patterns (Fig. 7). Interestingly, many of them
corresponded to walking patterns, which is the main activity
considered in previous works for person verification [27].
After that, we studied the correspondence between the
obtained motifs and the labels provided in the data set (Table I).
The rationale is that, if motif supports mostly belong to a
unique person, we can hypothesize that the inferred patterns
are a characteristic of that person (in other words, his/her
‘walking fingerprint’). For each group of segments supporting
a motif, we computed the mode with respect to the person
identifier and, if there was a clear ‘winner’ (that is, if a person
had clearly more supports than any other), we assigned that
motif to the corresponding person. Depending on the algorithm’s running time, we were able to reliably identify patterns
7 https://archive.ics.uci.edu/ml/datasets/Activity+Recognition+from+Single+
Chest-Mounted+Accelerometer

TABLE I.

C OMPARING THE INFORMATION OF THE OBTAINED MOTIFS
AND SUPPORTS WITH THE GROUND TRUTH GIVEN FOR THE DATA SET
OF [27].

Runtime
(min)
1
2
4
8
16
32
64

Persons with
motif
8/15
9/15
10/15
11/15
11/15
11/15
12/15

Person dominance
in motif
51.8%
57.9%
68.0%
67.9%
74.1%
76.7%
85.3%

Task dominance
in motif
57.6%
68.4%
70.7%
68.9%
77.6%
86.7%
89.3%

from 8 to 12 out of the 15 persons in the data set (Table I,
second column). Expectedly, the number of identified personassigned patterns does not linearly depend on the execution
time: after 8 min, the number of different persons with assigned
motifs already reaches 11, which roughly corresponds to a 73%
recall, and after 64 min it reaches 12, which corresponds to an
80% recall. Interestingly, as execution time progresses, we also
see that not only more person-related motifs appear, but also
that the motif supports are increasingly becoming associated
to a single person (Table I, third column) and to a single task
(Table I, fourth column). This shows that the refinements made
by GENMOTIF to the solutions found for this task go towards
the direction of having single-person and single-task supportbased motifs.
C. Exploring personalities with outgoing call motifs
Human communication patterns have long attracted the
attention of multiple scientific disciplines. Nowadays, a considerable portion of our communications leave digital traces
(such as phone calls, emails, short messages, etc.), a fact
that provides the historical opportunity to quantify these interactions on a large-scale and to advance the theoretical
knowledge about human interaction dynamics. In particular,
patterns of mobile phone communications (that is, voice calls
and short messages) have been used to study social behavior,
to distinguish between different user profiles (such as ordinary
users versus sales persons, telecom frauds, and robot-based
callers), and even to infer the users’ personality [28]. In this
case study, we explore the applicability of GENMOTIF to
discover patterns in time series of mobile phone calls. Specifically, we are interested in sequences of total daily outgoing
call durations with lengths around 1 month. To generate the
time series, we use an internal data set of anonymized call
detail records of approximately 600 subjects who, in addition,
kindly filled out the Big 5 personality questionnaire8 [29]. We
compute the sum of daily outgoing call durations for a total
of 6 months per subject, and concatenate these into a single
time series of over 108 000 samples.
Four different patterns were identified after running GENMOTIF for 5 minutes (Fig. 8). To obtain them, we searched
for 5 motifs with a support of 20 and lengths between 14 and
31 samples (corresponding to 2 weeks and 1 month, respectively). We further analyzed how these patterns corresponded
to different personalities of the participants (as reported in
the questionnaire). It turned out that motif A predominantly
corresponded to users with low conscientious scores (70%
8 http://ipip.ori.org/New

IPIP-50-item-scale.htm

8000
6000
4000
2000
0
8000
6000
4000
2000
0

8000
6000
4000
2000
0

A

0

5

10

15

20

25

30

C

0

5

10

15

20

25

30

8000
6000
4000
2000
0

B

0

5

10

15

20

25

30

D

0

5

10

15

20

25

30

Fig. 8. Four motifs found in the telephone calls time series by GENMOTIF.
The vertical axis corresponds to the sum of call durations (in s) and the
horizontal axis corresponds to days. The solid black curve depicts the average
of the motif supports. In this case, no z-normalization was used.

of them scored lower than a mean value of the involved
sample), whereas motif C corresponded to participants who
scored above the average. We can speculate that motif A
reflects a more random pattern of calls than motif C, thus
reflecting less conscientious profiles. Similarly, motifs B and D
distinguished participants based on the extraversion component
of the questionnaire (again with 70%). Motif B corresponded
to the participants with the scores above the average and
motif D was associated to the participants who scored below
the average. Again, one may speculate that the volume of
outgoing calls reflects the level of initiated social interactions
that further mirrors the extraverted personality. Interestingly,
motifs B and C are similar with respect to a peak that
appears once in one month, yet motif B clustered mainly
extraverted individuals (without any substantial difference in
the proportion of conscientious scores) whereas the motif C
mainly grouped individuals whose conscientiousness score was
lower than the average (without any substantial difference in
the proportion of extraversion scores in this pattern). This
may indicate that the shape of the peak was a distinguishing
factor: the higher amount of durations in motif B might
indicate the extraverted nature of participants, whereas highly
conscientious individuals have a more regular baseline of their
communication patterns (perceived in motif C). Note that in
previous studies related to inferring personalities through the
call patterns (e.g., [28], [30]), several hundreds of features
were extracted to model the five components of personality,
as opposed to only one signal, namely daily call durations,
that we used in this example.
VI.

RELATED WORK

The approach that is the most similar to GENMOTIF
is the one proposed in [15]. In such work, particle swarm
optimization [17] is used to find pairs of motifs under uniform
scaling in an anytime fashion. The approach can also find
warped motifs and it can work with multidimensional time
series. However, the approach does not consider the notion
of motifs with support nor does it guarantee that the found
motifs are dissimilar between themselves. Both features are
key contributions introduced by GENMOTIF.
In [9], an anytime algorithm to find motifs in time series
is presented. It uses the minimum description length principle
as a criterion to stop its execution as well as a measure of
segment similarity. This algorithm does not consider motif

invariances such as warpings or uniform scaling, and its
application to multidimensional time series was not considered. In [8], an efficient algorithm for enumerating motifs
in a range of lengths is explained. This is not an anytime
algorithm nor does it involve the notion of motif supports. The
same happens with [13], which considers the task of finding
motifs under uniform scaling and exploits an approximate
symbolic representation. The pioneering algorithm proposed
in [7] searches for motif pairs of a specific length, and its
adaptation to a range of lengths (made by the same authors) has
been shown to underperform the approach in [8]. There other
countless approaches that could be related to GENMOTIF,
including approximate motif discovery algorithms [2], [4]–[6].
However, one can easily find some task dimension where they
significantly differ from GENMOTIF.
Other algorithms have been proposed for the task of time
series subsequence clustering [10], [31]. Though this task and
the one of finding motifs with support have common aspects,
they are conceptually different. Time series subsequence clustering aims at obtaining a good and compact representation of
the whole time series while, as shown in [10], ignoring some
data. However, motif discovery aims at finding characteristic
patterns (with support) that do not necessarily need to reliably
and compactly represent the full time series. In fact, the
segments used to derive the motifs can actually represent a
tiny part of the time series (i.e., kslmax  n, as mentioned in
the main text).
Finally, we should note that the concept of motifs’ support
has been formulated in the past by some authors in a different way, specifically involving the choice of a dissimilarity
threshold [1], [3]. Essentially, such formulations reduce the
task of motif discovery to what we could call a ‘bucketbased’ or a ‘radius-based’ approach. For instance, one can
think of using a locality-sensitive hashing algorithm which,
after selecting an appropriate threshold, could distribute all
possible segments of a time series into different buckets.
Consequently, all segments in a bucket would determine a
motif, and the support of such motif would be the number of
segments in the bucket. This type of approaches face several
limitations. Firstly, a single threshold is used for all motifs.
This implies the assumption that all motifs form ‘clusters’ of
the same similarity radius, which is not necessarily the case for
real-world data sets. Secondly, dissimilarity thresholds can be
extremely difficult to estimate. As shown elsewhere [32], the
variability of the distances between the elements in a metric
space substantially reduces due to the curse of dimensionality.
Therefore, with increasing dimensionality, setting such threshold becomes more problematic. Thirdly, different segment
lengths require specifically tailored solutions. In this regard,
if one aims at discovering motifs within a range of lengths,
the aforementioned ‘radius-based’ approach is not intuitive
anymore as in the case of a fixed length. Lastly, it becomes
challenging to include uniform scaling or other invariances in
the definition of motif. Overall, we believe that the thresholdbased definition of motif support is much more restrictive than
the notion considered here.
VII.

CONCLUSION

In this study, we tackled the problem of finding motifs
with support. We proposed GENMOTIF, a genetic algorithm
that solves the problem in an anytime fashion and that, at

the same time, is flexible enough to accommodate multiple
definitions of motif. As it is solely based on dissimilarity
measurements and clustering criteria, GENMOTIF can work,
for instance, with a range of lengths, uniformly-scaled motifs,
warped or complexity-invariant similarity measurements, and
multidimensional time series.
We demonstrated the utility of GENMOTIF in a number of
tasks, including synthetic data, traffic volume measurements,
accelerometer signals, and telephone call records. We have also
shown that the two parameters of the algorithm do not critically
affect the performance of GENMOTIF, and we have provided
a quantitative as well as conceptual discussion in this regard.
In all our experiments, we have used publicly-available data,
except for one case study where data was not open to the public
due to proprietary reasons. Finally, we made GENMOTIF’s
code available online in order to foster research in time series
motif discovery algorithms and to encourage the use of these
algorithms in further scientific domains.
ACKNOWLEDGMENT
We would like to thank all the donors of the data sets
used in this study. This research has been partially funded by
ICT-2014-15-645323 from the European Commission (JS) and
2014-SGR-118 from Generalitat de Catalunya (JLA).
R EFERENCES
[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]
[9]

[10]

[11]

[12]

A. Mueen, “Time series motif discovery: dimensions and applications,”
WIREs Data Mining and Knowledge Discovery, vol. 4, no. 2, pp. 152–
159, 2014.
B. Chiu, E. Keogh, and S. Lonardi, “Probabilistic discovery of time
series motifs,” in Proc. of the ACM SIGKDD Int. Conf. on Knowledge
Discovery and Data Mining (KDD), 2003, pp. 493–498.
J. Lin, E. Keogh, S. Lonardi, and P. Patel, “Finding motifs in time
series,” in Proc. of the Workshop on Temporal Data Mining, 2002, pp.
53–56.
N. Begum and E. Keogh, “Rare time series motif discovery from
unbounded streams,” Proc. of the VLDB Endowment, vol. 8, no. 2, pp.
149–160, 2014.
N. Castro and P. Azevedo, “Multiresolution motif discovery in time
series,” in Proc. of the SIAM Int. Conf. on Data Mining (SDM), 2010,
pp. 665–676.
Y. Li, J. Lin, and T. Oates, “Visualizing variable-length time series
motifs,” in Proc. of the SIAM Int. Conf. on Data Mining (SDM), 2012,
pp. 895–906.
A. Mueen, E. Keogh, Q. Zhu, S. Cash, and B. Westover, “Exact
discovery of time series motifs,” in Proc. of the SIAM Int. Conf. on
Data Mining (SDM), 2009, pp. 473–484.
A. Mueen, “Enumeration of time series motifs of all lengths,” in Proc.
of the IEEE Int. Conf. on Data Mining (ICDM), 2013, pp. 547–556.
S. Yingchareonthawornchai, H. Sivaraks, T. Rakthanmanon, and C. A.
Ratanamahatana, “Efficient proper length time series motif discovery,”
in Proc. of the IEEE Int. Conf. on Data Mining (ICDM), 2013, pp.
1265–1270.
T. Rakthanmanon, E. Keogh, S. Lonardi, and S. Evans, “Time series
epenthesis: clustering time series streams requires ignoring some data,”
in Proc. of the IEEE Int. Conf. on Data Mining (ICDM), 2011, pp.
547–556.
C. D. Truong and D. T. Anh, “A fast method for motif discovery in
large time series database under dynamic time warping,” in Knowledge
and Systems Engineering, ser. Advances in Intelligent Systems and
Computing, V.-H. Nguyen, A.-C. Le, and V.-N. Huynh, Eds. Berlin,
Germany: Springer, 2015, vol. 326, pp. 155–167.
G. E. A. P. A. Batista, X. Wang, and E. Keogh, “A complexity-invariant
distance measure for time series,” in Proc. of the SIAM Int. Conf. on
Data Mining (SDM), 2011, pp. 699–710.

[13]

[14]

[15]

[16]
[17]
[18]
[19]
[20]

[21]

[22]
[23]
[24]
[25]

[26]

[27]

[28]

[29]
[30]

[31]

[32]

D. Yankov, E. Keogh, J. Medina, B. Chiu, and V. Zordan, “Detecting
time series motifs under uniform scaling,” in Proc. of the ACM SIGKDD
Int. Conf. on Knowledge Discovery and Data Mining (KDD), 2007, pp.
844–853.
D. Minnen, C. Isbell, I. Essa, and T. Starner, “Detecting subdimensional
motifs: an efficient algorithm for generalized multivariate pattern discovery,” in Proc. of the IEEE Int. Conf. on Data Mining (ICDM), 2007,
pp. 601–606.
J. Serrà and J. L. Arcos, “Particle swarm optimization for time series
motif discovery,” Knowledge-Based Systems, vol. 92, pp. 127–137,
2016.
S. Luke, Essentials of metaheuristics, 2nd ed. Raleigh, USA: Lulu,
2013.
R. Poli, J. Kennedy, and T. M. Blackwell, “Particle swarm optimization,” Swarm Intelligence, vol. 1, no. 1, pp. 33–57, 2007.
L. D. Davis, Handbook of genetic algorithms. New York, USA: Van
Nostrand Reinhold, 1991.
R. Xu and D. C. Wunsch, Clustering. Hoboken, USA: Wiley, 2009.
D. L. Davies and D. W. Bouldin, “A cluster separation measure,” IEEE
Trans. on Pattern Analysis and Machine Intelligence, vol. PAMI-1,
no. 2, pp. 224–227, 1979.
P. J. Rousseeuw, “Silhouettes: a graphical aid to the interpretation and
validation of cluster analysis,” Journal of Computational and Applied
Mathematics, vol. 20, pp. 53–65, 1987.
G. Rudolph, “Convergence analysis of canonical genetic algorithms,”
IEEE Trans. on Neural Networks, vol. 5, no. 1, pp. 96–101, 1994.
S. Zilberstein, “Using anytime algorithms in intelligent systems,” AI
Magazine, vol. 17, no. 3, pp. 73–83, 1996.
X.-S. Yang, Nature-inspired metaheuristic algorithms, 2nd ed. Frome,
UK: Luniver Press, 2010.
G. M. Viswanathan, S. V. Buldyrev, S. Havlin, M. G. E. Da Luz,
E. P. Raposo, and H. E. Stanley, “Optimizing the success of random
searches,” Nature, vol. 401, pp. 911–914, 1999.
A. Ihler, J. Hutchins, and P. Smyth, “Adaptive event detection with timevarying Poisson processes,” in Proc. of the ACM SIGKDD Int. Conf.
on Knowledge Discovery and Data Mining (KDD), 2006, pp. 207–216.
P. Casale, O. Pujol, and P. Radeva, “Personalization and user verification
in wearable systems using biometric walking patterns,” Personal and
Ubiquitous Computing, vol. 16, no. 6, pp. 563–580, 2010.
R. De Oliveira, A. Karatzoglou, P. Concejero Cerezo, A. M. Lopez
de Vicuña, and N. Oliver, “Towards a psychographic user model from
mobile phone usage,” in Proc. of the Computer-Human Interaction
Conf. (CHI), Extended Abstracts on Human Factors in Social Systems,
2011, pp. 2191–2196.
L. R. Goldberg, “The development of markers for the Big-Five factor
structure,” Psychological Assessment, vol. 4, pp. 26–42, 1992.
Y.-H. De Montjoye, J. Quoidbach, F. Robic, and A. Pentland, “Predicting personality using novel mobile phone-based metrics,” in Social
Computing, Behavioral-Cultural Modeling and Prediction, ser. Lecture
Notes in Computer Science, A. M. Greenberg, W. G. Kennedy, and
N. D. Bos, Eds. Berlin, Germany: Springer, 2013, vol. 7812, pp.
48–55.
N. Madicar, H. Sivaraks, S. Rodpongpun, and C. A. Ratanamahatana,
“Parameter-free subsequences time series clustering with various-width
clusters,” in Proc. of the Int. Conf. on Knowledge and Smart Technology
(KST), 2013, pp. 150–155.
E. Chávez, G. Navarro, R. Baeza-Yates, and J. L. Marroquı́n, “Searching
in metric spaces,” ACM Computing Surveys, vol. 33, no. 3, pp. 273–321,
2001.

