Database Reference
In-Depth Information
use a filter-and-refine approach in which objects located far away can be
pruned (i.e. their shortest distance is larger than the longest distance
of a closer object). After filtering objects that obviously do not satisfy
the query, the space in which objects need to be evaluated (i.e. over
which the integral needs to be performed) can be bounded. Lastly, the
remaining objects are evaluated by computing the integral in Eq. 10.1.
p
i
=
f
n
i
p
i
(
r
)
|S|
(1
−
P
k
(
r
))
dr
(10.1)
k
=
i
In Eq. 10.1,
n
i
is the shortest distance from object
O
i
to the query point
q
,and
f
is the bounded region over which objects must be evaluated.
The integration can be interpreted as the probability that
O
i
is at a
distance of
r
from
q
while all other points in the candidate set,
S
,are
at a distance greater than
r
, which is evaluated over all possible values
of
r
. The authors introduce a more ecient approach to evaluating
this integral by sorting
S
and breaking up the integration limits to only
the region in which
p
i
(
r
) is non-zero. Furthermore, they also utilize
an R-tree based index structure, called the velocity constrained index
(VCI) [68], to improve processing time for large datasets.
Saltenis et al. [71] introduce a general index structure for eciently
processing queries on mobile objects called the time parameterized R-
tree (TPR-tree). The idea behind the TPR-tree is to allow MBRs to
grow and change position as a function of time in order to reduce the
number of necessary updates to the index structure from objects moving
(see
figure 2.2
). The authors propose
conservative bounds
,inwhichthe
MBR expands by the maximum velocity of the contained set of objects in
each dimension. That is, considering the number line in which values to
the left are smaller and those to the right are larger, the MBR expansions
in both directions of one dimension are given in Eq. 10.1.
x
=min
o
i
.
pos(
t
))
min(
o
i
.
vel)(
t
diff
)
x
=max
o
i
.
pos(
t
)) + max(
o
i
.
vel)(
t
diff
)
−
(10.2)
Non-leaf level MBRs are constructed by aggregating the bounds from
each of their children. For each dimension, the expansion in each direc-
tion is the maximum over all of its children.
Although the TPR-tree may be used to index mobile objects indefi-
nitely, it is optimized only for a particular time horizon, after which the
performance of the index may deteriorate. Specifically, the index struc-
ture requires two parameters: the querying window,
W
, which defines
how far queries may look into the future and the index usage time,
U
,
which defines how long users will query the index. Combining both of
