Information Technology Reference
In-Depth Information
expressed through piece-wise linkage, as is often used in convoy definitions (Jeung
et al.
2008a
,
b
).
Borrowing from the application literature can be a blessing and a curse when it
comes to terminology. Clearly, using established terminology and respective defi-
nitions helps conceptualizing useful and understandable patterns (see Sect.
3.1.1
).
However, problems can emerge when conceptually identical patterns have differ-
ent yet similar terms in different fields (e.g., flocks, convoys, herds), or even worse
when identical terms have differing meanings in different fields. For that reason it
can be observed that terminology in movement pattern mining has evolved towards
more structural terms (moving cluster) rather than semantically loaded terms (flock,
convoy).
3.2.3.2 Increasing Levels of Complexity
The research summarized in this chapter indicates that novel (non-trivial and unex-
pected) movement patterns can often be decomposed into more primitive building
blocks. These building blocks in turn are often spatial proximity- or topology-based
relations or set relations. For example,
leadership
in Andersson et al. (
P5
.
2008
)
requires the spatial relation “
e
j
is in front of
e
i
”, which is in turn based on the con-
cept of a front region
front
.
This very same front region is also featured in Merki and Laube (
P16
.
2012
), here,
however, acting as a building block of the interaction pattern
pursuit and escape
(see
Fig.
3.7
). The latter piece furthermore features very similar pattern primitives for
“proximity” (even in two different ways for both the Lagrangian and the Eulerian
The sequence patterns in Bleisch et al. (
P20
.
2014
) are per definition chained-up
simple movement or environmental events (“rapid upstream movement”, “moderate
water temperature”), building more complex sequences. Such a sequence could, for
example, comprise of a moderate water temperature event, followed by two rapid
upstream movement events (
(
e
i
)
, a wedge with edge length
r
and apex angle
α
).
The hierarchical decomposition of movement patterns furthermore assists the
development of algorithms for detecting the patterns. Andersson et al. (
P5
.
2008
)
first introduce a series of auxiliary data structures in the form of precomputed data
arrays that are then later combined for an efficient detection of the patterns. These
arrays store for each moving entity the number of consecutive unit time intervals
expressing a certain follow-behavior. For example, leadership can be derived from
the arrays “the number of time units
e
j
has at least
m
followers” and “the number
of time units
e
j
is not following anyone else”. The algorithmic procedure in Merki
and Laube (
P16
.
2012
) computes in a very similar way first all primitive events
contributing to a pattern and then investigates the required sequences (see Fig.
3.7
,
approach
, followed by
follow
after a delay, followed by
separate
).
The usefulness of such a hierarchical composition of movement patterns is further
emphasized through several attempts of a categorization or ontology of movement
patterns. Dodge et al. (
2008
) refer to
primitive patterns
and
compound patterns
,
{
wt
3
e
}
,
{
u
e
}
,
{
u
e
}
