Database Reference
In-Depth Information
finds all pairs of objects with (nearly) matching subtrajectories over a
given time interval. This query could be useful in clustering subtra-
jectories or simply identifying groups of mobile objects that traversed
similar paths. More formally, the authors define the spatiotemporal join
query to take two sets of trajectories, a distance threshold,
,andtime
interval,
δ
t
, and returns all pairs such that there exists a subregion of
each trajectory of length
δ
t
where the distance between the subregions
is at most
. The query is called a time relaxed spatiotemporal trajec-
tory join (TRSTJ), because the query only constrains the length of the
trajectory subregion, not the specific start time. To answer the TRSTJ,
the authors propose a filter and refine approach where they use a com-
pact trajectory representation and lower bound the Euclidean distance
between trajectories.
2.2 Moving Object Databases
Unlike STDBs, a
moving object database
(MOD) only stores the
cur-
rent
position of each object. MODs constantly contain up-to-date in-
formation about the location of each object and are therefore useful in
real-time applications of managing a large number of mobile objects (e.g.
navigation or emergency response dispatch). Similar types of queries are
supported on MODs, however, the time intervals over which the data
may be queries is limited to the present and future. Instead of asking
where an object
has
been, a MOD answers the query “where is object
A now”? or “where will it be in 5 minutes”? In order to answer such
queries, the system must have some method to predict the future location
of each object given its current location and its velocity. We will cover
different approaches for updating and predicting location information in
detail in section 3.
Similar to STDBs, a primary diculty for MODs is constructing and
maintaining an index structure. However, the
cause
of the diculty
in the two systems is quite different. Here, the problem is keeping the
location information for all objects up to date, which requires frequent
updates to the index. Continually modifying an index structure is likely
to cause the discriminative capabilities of the structure to degrade over
time unless special care is taken.
Cheng et al. [15] introduce a method for answering range queries and
nearest neighbor queries with probabilistic guarantees when the location
of objects is uncertain. The authors propose an uncertainty model that
specifies a bounded region within which a mobile objects may be located
with equal probability. The authors were the first to define and propose
a solution to the probabilistic nearest neighbor query (PNNQ). They
