Database Reference
In-Depth Information
frequent disk accesses for deleting old record entries. This reduces the
cost of an updating an object's position simply to that of inserting a
new object into the R-tree and old entries are deleted in batches. The
B
dual
-tree and STRIPES are both indexes that utilize dual space. The
B
dual
-tree maps an objects location and velocity to a 1-dimensional point
using a Hilbert curve. STRIPES maps a mobile object to a four dimen-
sional point and applies a quad-tree based structure to index the space.
The experimental evaluation provides a thorough comparison between
the different index structures on several aspects of updating and query-
ing mobile objects. Although each index performs well under certain
circumstances, the B
x
-tree consistently performed near the top over all
experiments never costing more that 2X the best index structure. While
the TPR-trees were
the
most ecient indexes for the querying exper-
iments (in terms of time and I/O), they also performed the worst for
updates. Overall, this work highlights the need to clearly identify the
expected query workload distribution in order to select the most ecient
structure.
A problem that has received far less attention in the spatiotemporal
data management community is that of how to most eciently update
the database with new positions for mobile objects. Wolfson et al. [90]
address this problem by framing it as an optimization problem. The au-
thors provide a model of the cost to poll an object in order to update its
location and a cost for answering a query given the current (estimated)
location uncertainty (i.e. how much error are we willing to tolerate)
and aim to minimize their total costs while handling a query workload.
The authors also introduce a spatial indexing scheme for moving objects
that considers the possible location error. For this, they use an
R
+
-
tree [73] over three dimensions (the
x,y
plane and time). The index is
updated only when objects report their position to the database (using
the derived update policy).
2.3 Mobile Objects on Road Networks
The queries and index structures discussed thus far consider the case
of unrestricted movement, however, movement is often restricted to a
transportation network (i.e. road network). If the structure of the un-
derlying transportation network is known, then incorporating this ad-
ditional information can provide more accurate tracking and prediction
of object locations (and therefore more meaningful queries). Restricting
movement to the network structure brings about its own set of chal-
lenges.
