SENSING FOR MOBILE OBJECTS - Managing and Mining Sensor Data - page 330

(a) Flocks (b) Convoys (c) Swarms

Figure 10.11. An example of (a) flocks, (b) convoys, and (c) swarms. Each of these
patterns captures groups of objects that tend to move together over time, though
they each specify slightly different constraints as highlighted in this figure.

In addition to the basic notions of clustering for mobile objects, newer
definitions have also been introduced which provide a stronger notion
that objects must move together. Recently, the notion of flocks , convoys
and swarms have been introduce which impose varying constraints on
how tightly packed objects must remain over time. Specifically, in [87], a
flock is defined as a set of at least μ trajectories that are located within a
given disk with radius 2 ,for δ or more time steps. A flock query returns
all sets of trajectories such that the predicate flock ( μ,,δ )ismet. To
answer the flock query, the authors propose first griding the space such
that each grid is a square with edge lengths . This reduces the necessary
number of comparisons between points and allows the authors to provide
an exact answer to the flock query in polynomial time. The authors
provide a basic query processing algorithm along with several filtering
approaches to improve the algorithm eciency.
Jeung et a. [37] relax the definition of a flock by using the notion of
density connected groups of objects over time. The new spatiotemporal
groups are called convoys and the authors introduce a filter-and-refine
algorithm called convoy discovery using trajectory simplification (CuTS)
to search for convoys in a given database. The authors first simplify
trajectories using linear approximations of subtrajectories such that a
maximum error bound is maintained. The simplified trajectories contain
fewer points than the originals and are thus easier to manage. The
filtering step in CuTS involves a trajectory simplification followed by
a density based clustering. In the refinement step, the full trajectories
are run through the density clustering again to account for the δ error
introduced in the trajectory simplification. The resulting set of clustered
trajectories are guaranteed to be convoys.
Furthermore, Li et al. [48, 49] define a swarm , which again relaxes the
notion of a convoy by removing the restriction that objects must remain