Database Reference
In-Depth Information
The trajectory pattern mining problem consists of finding all frequent T-patterns,
such that
suppor t
(
S
,
A
)
≥
sup
min
,
where
suppor t
(
S
,
A
) is the number of input trajectories containing the T-pattern
T
(
S
,
A
) and the
sup
min
is a minimum support threshold.
To mine frequent T-patterns, the method to mine temporally annotated sequences
(TAS) [
13
] can be applied if we first symbolize the locations using RoI. In [
14
], Gi-
annotti et al. further discuss how to dynamically identify the locations and transition
time in the pattern.
In [
29
], Monreale et al. propose WhereNext, a location prediction method using T-
Patterns. A decision tree, named T-pattern Tree, is built and evaluated in a supervised
learning framework. The tree is learned from the T-Patterns and it is used as a predictor
of the next location by finding the best matching path in the tree. Different from [
17
]
using individual frequent periodic pattern, as we discussed in Sect.
3
, WhereNext
[
29
] uses the overall traffic flows to predict the next location.
5.2
Detection of Moving Object Cluster
Moving object clusters detect groups of moving objects being spatially close for a
considerably long time. Clusters of moving objects can reveal underlying communi-
ties, such as the social groups of animals or humans, and can also indirectly identify
outliers that do not conform to general group behaviors.
In this section, we will discuss patterns
flock
[
15
],
convoy
[
18
] and
swarm
[
21
].
A moving object cluster can be loosely defined as a set of moving objects being
spatially close for
k
timestamps. The differences among flock, convoy and swarm
lie in the definitions of “spatially close” and “k (non-)consecutive timestamps”.
Gudmundsson et al. [
15
] first propose the concept of flock.
Definition 12.2 (Flock)
A set of moving objects O form a flock for timestamps T if
(1) for every timestamp in T , there is a disc with radius r containing all the objects
in O; and (2) T is consisted of at least k consecutive timestamps.
In Fig.
12.10
,
o
3
and
o
4
form a flock since they are in the same disc from
t
1
to
t
4
. Since flock defines spatial constraint as a fixed-radius disc, such definition might
be too strict and is independent of data distribution. For example, at timestamp
t
1
in
Fig.
12.10
, all the objects are in a density-connected cluster but using a disc may split
them into multiple clusters. To relax the rigid restriction on the disc-shape cluster,
Jeung et al. [
18
] proposes a new concept
convoy
to discover arbitrary-shape clusters.
Convoy uses DBSCAN [
11
] to cluster points in each timestamp. Two objects in a
cluster are density-connected to each other, if only there exists a sequence of objects
that connect them together. The definition of density-connected permits us to capture
a group of connected points with arbitrary shape.
