Database Reference
In-Depth Information
occupies. To process an update, the object record is found, its location
is updated and we check if it has changed road segments. If so, we
search the R-tree based on the new coordinates and fix the pointer in
the object record to point to the updated road segment. The IMORS
provides significant eciency gains in processing updates over the TPR-
tree (to which it was compared in the experiments), by utilizing the
static nature of the road network. Since locations of roads do not move,
object positions are modified by updated the road segment to which
they point, however, all searching is done over the road network indexed
R
∗
-tree.
When dealing with mobile objects that have restricted movement,
such as automobiles on a road network, this gain in eciency in index-
ing and query, and increased accuracy in predicting future locations is
common. The idea of integrating all available information about the
object movement is important as it allows us to identify object posi-
tions and movement more reliably. Utilizing extra information can help
combat against the problems of spatial and temporal uncertainty when
managing spatiotemporal data.
Additionally, there is a plethora of work in the area of eciently pro-
cessing routing queries for navigation queries. For instance, computing
the quickest (or most ecient) route between two points considering the
dynamics of the road network is of great interest. Incorporating extra in-
formation like speed limits, predicted trac patterns, and road closures
can greatly improve routing and therefore help relieve trac congestion.
Nikolova et al. [63] show several theoretical results related to problems
of optimal route planning. The authors show the surprising result that
the problem of finding an optimal route
and
start time can be solved
using standard shortest path algorithms for certain cost functions while
the optimal route planning problem when the start time is fixed is NP-
hard. Similarly, Wilkie et al. [89] consider the routing problem on a
stochastic trac network, however, they integrate the effect of the plan-
ner into future predictions. That is, vehicles will query the planning
system to ask for directions, assuming the vehicles stick to these routes,
the planner has additional information about the state of the trac in
the future. Malviya et al. [54] introduce an approach for continuously
monitoring a set of shortest path for mobile objects. The authors first
precompute a set of
good
routes using a road network and historic travel
times and then re-rank these paths by integrating information about
real-time trac. Gonzalez et al. [24] developed a fastest-path algorithm
which utilizes historic information about trac and weather conditions
to provide reliable routes. The authors also introduce a network par-
titioning algorithm which reduces the search space by focusing on the
