Database Reference
In-Depth Information
objects or grouping similar trajectories. Clustering is a crucial task in
many data management and analysis tasks since it can be used for com-
pression and indexing as well as understanding similarities in the move-
ments of objects. Second, we cover work on popular route detection.
This section reviews some recently developed methods for identifying
often-traveled paths. The intuition is that the transportation network
may not represent all of the factors that influence the decision to take
one path over another (e.g. long stop lights, trac congestion, etc.). By
mining previous travel patterns, it is possible to identify the frequently
traveled paths. This information can then be used for managing trac
congestion, finding ecient routes, or simply studying the effectiveness
of the given road network. The third section focuses on problems related
to quantitatively assessing individual user movement patterns. Instead
of looking at aggregate behavior, as the work in popular route detec-
tion does, the work in this section focuses on the individual. Here the
interesting problems are predicting future locations and high-order un-
derstanding of user movement (e.g. is the user going to work or to the
store?).
Clustering.
In the spatiotemporal data setting, clustering aims to
group together objects which are within close proximity of one another
and
will remain so over time. Li et al. [47] propose a technique for clus-
tering moving objects by extending the ideas of micro-clustering [99] to
handle data that changes over time. To maintain good clusters over time,
the authors propose computing a minimum bounding rectangle (MBR)
for each cluster. When the MBR reaches a predefined threshold, a split
event occurs in which the object furthest from the center of the cluster is
removed and reassigned to the nearest microclucster. The resulting time
complexity of the clustering approach is
O
((
N
+
T
)
log
2
(
N
+
T
)
log
(
N
)),
where
N
is the number of mobile objects and
T
is the total time over
which the clustering is to be maintained. Similarly, Jensen et al. [36]
also propose an online method for eciently clustering moving objects
based on [99]. The authors introduce a dissimilarity measure for mobile
objects which takes the weighted sum of the differences between the lo-
cations of two objects over
m
time steps. The weights are monotonically
decreasing as they become further into the future i.e. the current time is
weighted more heavily than future positions. Utilizing the BIRCH clus-
tering framework [99], the authors extend the clustering feature vector
to include object positions and velocities in a format that is ecient to
update. Computing a radius for each cluster (at each time step), fu-
ture necessary cluster split points can be predicted and then processed
eciently by reassigning.
