Database Reference
In-Depth Information
useful in designing an ecient highway system or estimating road wear
over time.
Perhaps the most basic problem involving movement patterns is that
of predicting an object's future position given its current location. Tao
et al. [76] introduce the
recursive motion function
(RMF) for predict-
ing the future position of a moving object. It formulates an object's
location at time
t
as loc
t
=
i
K
m
(
i
)loc
t−i
,where
K
m
(
i
)isaconstant
matrix that represents the type of motion performed by the object and
f
, called retrospect, is the minimum number of the most recent times-
tamps which are required to compute the elements of all
K
m
(
i
). The
K
m
(
i
) matrices represent
m
=1
..M
different motion types (e.g. linear,
circular, sine, polynomial, ...) and the motion estimation is done by de-
termining which pattern results in the lowest summed squared distances
between the object's actual and predicted trajectory. To manage the
large set of potential motion patterns, the authors also propose the spa-
tiotemporal prediction tree (STP-tree), an R-tree based index mobility
functions. The STP-tree maintains a set of polynomial curves which
represent object movement over time, in the case when the all of the
predicted patterns produce linear functions, the STP-tree reduces to the
TPR-tree. Although RMFs have performed very well at predicting fu-
ture locations of mobile objects with complex mobility patterns, they
have some weaknesses. Because predictions are based on past move-
ments, RMFs are not able to capture sudden changes in direction (such
as a U-turn). Additionally, predictions made several time steps into the
future tend to loose accuracy since objects tend to only follow a given
motion type for a limited time.
To address these issues, Jeung et al. [37] use previous trajectories
from objects to provide a method that is able to accurately predict an
object's location multiple time steps in the future. The authors utilize
the object's past behavior by performing frequent item-set mining to
find common locations (i.e.
given that the object is at the mall at
4
pm,
shewillbeatthebeachat
5
pm with confidence
c
). This work addresses
the problem of answering prediction queries by assuming each object
has an underlying repetitive pattern. The proposed algorithms are ex-
perimentally shown to outperform RMFs, previously the state-of-the-art
method for predicting future locations.
Another important aspect of mobility is periodicity as users tend to
exhibit many regularities in their movements (e.g. going to work every
morning). Li et al. [48, 49] develop a novel technique for identifying pe-
riodic movements of a user where the period lengths are also extracted
from the data. To robustly identify periodic patterns at various reso-
lutions, the authors propose the idea of using references spots for each
