Database Reference
In-Depth Information
thesevalueswegetthetimehorizon,
H
=
U
+
W
, which is the time over
which the index structure must be able to answer queries. Using these
values, the index structure can be optimized since there is a limit as to
how far into the future the index will be required to answer queries.
The TPR-tree uses the same optimization concepts from the R*-
tree [5], specifically the area of MBRs, perimeter length, and overlap
area, except they are minimized over a time horizon instead of simply
minimizing the current state of the index. If we consider an objective
function that minimizes overlap between MBRs
A
(
t
), then we would like
to optimize this function over the given time horizon:
t
+
t
A
(
t
)
dt
.The
operations used in the TPR-tree are all analogous to the R*-tree, with
the only difference being the function
splitNode
(), which determines how
objects contained in full nodes should be partitioned. Since MBRs are
dynamic, the TPR-tree split is based on optimizing over both the current
positions
and
velocities.
Query processing in the TPR-tree is similar to the R-tree [28]. Since
all of the MBRs are parameterized by time, answering a time-slice range
query remains completely unchanged. To answer a time-interval range
query or a moving range query, it is necessary to identify intersections
between the MBR and the query region over the specified time interval
in each dimension and check that the intersections happened over the
same time interval in all dimensions. This is computed in a straight for-
ward manner by comparing line segments of the query region and MBR
boundaries in each dimension over time (the lines describing movement
in the both the
x
and
y
dimensions over a time interval).
The simplicity of the TPR-tree has made it a popular choice for in-
dexing MODs. Tao et al. [78] have extended the original work by intro-
ducing the TPR*-tree, where they improve upon the optimizations in-
troduced in [71]. The TPR*-tree tightens the bounds of the MBRs thus
making the index more discriminative. Experiments show substantial
improvements in performance over the TPR-tree for large datasets. To
handle spatial uncertainty in mobile objects, Hosbond et al. [31] adapt
the TPR-tree to index moving objects with inexact location informa-
tion. The authors essentially model location uncertainty as a Δ term in
which each object can vary some amount from its stated position. They
incorporate this error term into the MBR parameterization to guarantee
each object is properly bounded over time.
In [98], the authors present both a movement model for mobile objects
with uncertainty as well as an index structure for ecient query process-
ing. The proposed uncertain moving object model defines a probabil-
ity distribution over location and velocity (independently). The model
works by griding the space at some resolution and assigning each cell
