Database Reference
In-Depth Information
together over consecutive time steps. A swarm is defined as a set of at
least
min
o
objects that remain clustered for at least
min
t
time steps
over a given interval. That is, a swarm is defined by a set of objects,
O
and a set of time steps,
T
, over which the objects remain clustered. To
avoid repeatedly identifying subsets of the same objectset, the authors
define a
closed swarm
to be a swarm such that the objectset and the
timeset are maximal (i.e. adding another object will shrink the timeset
and adding another time step will shrink the valid objectset).
Li et al. [48, 49] develop an algorithm for finding swarms which is
based on the Apriori (frequent itemset) framework. To manage the
exponential search space, three pruning rules are introduced. The first
rule says that if
in which
the time constraint will be satisfied, thus we can stop growing this set.
The second pruning rule, backward pruning, states that if the maximum
time set of an objectset,
|
T
|
<min
t
, then there is no superset of
O
O
, does not decrease by adding one more object,
then
O
, may be pruned and we can continue expanding the new objectset
O
=
. Lastly, forward pruning, by similar means to backward
pruning, allows us to determine if an objectset is not closed. Using these
pruning rules, the
ObjectGrowth
algorithm performs a depth-first search
(on the space of swarms) and identifies all closed swarms.
{O ∪
o
i
}
Popular Route Discovery.
Closely related to the problem of
clustering, is that of discovering popular routes. Whereas clustering is
an object-centric task, the goal of popular route discovery is to identify
specific
paths
that are heavily traveled. We review two recent approaches
to this problem, the first finds heavily traveled paths conditioned upon
a specific origin and destination and the second finds all paths such that
the amount of trac is greater than a given threshold.
Chen et al. [14] introduce a new approach for discovering popular
routes only given a set of GPS trajectories. The authors assume that a
road network is not available and construct one directly from the data.
They use a density based clustering routine for identifying the underlying
road network (specifically the intersections) from a set of individual GPS
trajectories. The clustering algorithm is an adaptation of DBSCAN [21]
with a different connectivity metric which is based on the angle of in-
tersection between trajectories (since roads typically intersect at nearly
right angles).
Using the constructed road network, Chen et al. [14] a random walk
based approach for identifying popular paths with respect to a specific
destination node. The authors assign a transition probability at each
intersection by counting the number of objects that took each path from
the GPS trajectories. Since the objective is to identify popular routes
