Database Reference
In-Depth Information
t
4
y
t
3
o
2
o
1
t
2
o
3
o
3
t
1
x
Fig. 12.10
An example of flock [
15
], convoy [
18
] and swarm [
21
]. If we set time constraint
k
=
3
(i.e., number of timestamps being spatially close),
o
3
and
o
4
form a flock since they are in a disc
for four consecutive timestamps.
o
1
,
o
3
and
o
4
form a convoy since they are in the same density-
connected cluster for four consecutive timestamps. Swarm considers all these four objects as a
cluster since it treats
o
1
at
t
2
as a short deviation from the cluster
Table 12.3
Summary of moving object clusters
Pattern
Spatial constraint
Temporal constraint
Flock [
15
]
Disc shape
k
consecutive timestamps
Convoy [
18
]
Arbitrary shape
k
consecutive timestamps
Swarm [
21
]
Arbitrary shape
k
(non-)consecutive timestamps
Definition 12.3 (Convoy)
A set of moving objects O form a convoy for timestamps T
if (1) for every timestamp in T , all the objects in O are in the same density-connected
cluster; and (2) T is consisted of at least k consecutive timestamps.
In Fig.
12.10
, three objects
o
1
,
o
3
and
o
4
are in the same density-connected cluster
during the time interval [
t
1
,
t
4
]. Although the convoy model is much flexible than the
flock, the time constraint on
k consecutive
timestamps is still too strict. The moving
objects may temporarily leave the group. For example,
o
1
temporarily leaves the
group at
t
2
. If we enforce the “consecutive” time constraint,
o
1
is not considered to
be in the same group with other objects. Motivated by this important observation,
Li et al. [
21
] propose the concept of
swarm
to relax the time constraint. Instead of
requiring the objects being in the same cluster for
consecutive
timestamps, swarm
allows the timestamps to be
non-consecutive
.
Definition 12.4 (Swarm)
A set of moving objects O form a swarm for timestamps T
if (1) for every timestamp in T , all the objects in O are in the same density-connected
cluster; and (2) T is consisted of at least k timestamps that are not necessarily
consecutive.
In Fig.
12.10
, we can see that all the objects form a group even though
o
1
tem-
porarily leaves the cluster at
t
2
. Swarm is able to capture
as one cluster.
Table
12.3
summarizes the three different patterns: flock, convoy and swarm.
The definition of the swarm is the most flexible one in terms of the spatial and
{
o
1
,
o
2
,
o
3
,
o
4
}