Database Reference
In-Depth Information
Figure 10.4.
AnexampleofhowtheTPRoptimizesMBRsovertime. Theright
panel (A) shows the MBR optimized for the current configuration, whereas the left
(B) considers both the current object position as well as velocity.
a probability thereby constructing a discrete distribution over possible
locations (velocities). Combining the current location and velocity dis-
tributions, it is then possible to predict an object's future location. Uti-
lizing a gridded space technique allows the representation of arbitrary
distributions, however, it also incurs a heavier cost for prediction since
sampling must be employed. The authors then adapt the B
x
-tree [35] to
handle objects with uncertain locations. For each object, every non-zero
probability grid cell of the object's location is inserted into the index
structure, thus accounting for location uncertainty. Thus a trade-off is
made between location accuracy and the space consumption and search
time of the index structure.
Chung et al. [17] develop query processing and indexing techniques
to eciently answer probabilistic range queries when uncertainty in the
trajectories is described with Gaussian noise. The authors assume that
objects are moving along a known path and thus treat each object as
moving in 1-dimensional space over time. The movement uncertainty for
each object is modeled by Brownian motion in which the object's velocity
is normally distributed. To avoid the linear scan of the database, the
authors apply the Hough transform, which maps lines to points, to the
expected trajectory of an object and use an R-tree to index these points
in the dual space. Queries are then transformed in the same manner,
although some additional work is required since the trajectories contain
some location uncertainty. The query region is expanded depending on
the probability threshold issued in the query. Although this approach
provides ecient processing of probabilistic range queries, it makes the
limiting assumption that objects move in 1-dimensional space.
Chen et al. [12] perform an experimental investigation of the effec-
tiveness of several index structures for MODs under various conditions.
The authors compare the TPR-tree [71], TPR*-tree [78], B
x
-tree [35],
B
dual
-tree [95], STRIPES [65], and RUM*-tree [92]. The R-tree with
Update Memo (RUM*-tree) employs main-memory memos to help avoid
