Database Reference
In-Depth Information
between a given source and destination, each trajectory is weighted by
the likelihood that it is heading toward the specified destination. That
is, separate random walk probabilities are constructed for each specified
destination. Using this network, the authors run a random walk using
the destination node as an absorbing state to compute a score for each
node. The paths are scored by computing the product of the individual
node popularity scores (i.e.
v∈V
p
(
v
)) and the path with the maximum
popularity is computed using an adaptation of Dijkstra's shortest path
search. Although it is not clear if the algorithms will scale to large
networks or answering queries online (due to the preprocessing costs),
the experimental results presented in [14] are promising.
Similarly, Li et al. [46] propose a method for identifying all of the
heavily traveled routes in a given road network, independent of a spe-
cific starting and stopping point. The authors introduce a new al-
gorithm, called
FlowScan
, which combines ideas from both individual
and aggregate-level analyses over trajectories to identify popular routes.
FlowScan iteratively expands a route starting with a given road edge,
r
, by identifying those edges that are within
hops of
r
and satisfy the
minimum
trac
support (i.e. number of trajectories that pass through
that road segment). The trac support is computed as
|
traffic
(
r
)
∩
traffic
(
s
)
MinTraffic
, which says that the two roads must
share
some minimum amount of trac (i.e. the same trajectories must travel
through both road segments). Starting from an edge satisfying the min-
imum trac threshold, the algorithm proceeds by adding edges until the
conditions are not satisfiable.
The proposed algorithm manages finding popular routes even in di
-
cult instances where routes may partially overlap with one another and
there may be sparse regions in which objects may choose from several
roads to connect two portions of the same 'route'. The authors exper-
iment with their method on simulated data on a real road network to
show the quality of the identified routes obtained by their approach and
compare it to prior work. They show that FlowScan is able to identify
correct popular routes when the other methods failed, either by grouping
overlapping routes together or missing parts of routes due to gaps.
|≥
Mobility Patterns.
The last group of work we discuss is broadly
categorized as mining mobility patterns. By mobility patterns, we refer
to the common movements exhibited either by the same object over a
long history, or movements repeated by several different objects. For
instance, it may be common for residents to use a similar path during
their morning commute to get from the suburbs where they live to the
downtown area in which they work. Identifying such patterns may be
