Database Reference
In-Depth Information
Zheng et al. [100] address the problem of managing moving objects
on road networks where the specific path traveled by an object is un-
certain. The authors represent the uncertain locations of objects as
time-dependent probability distributions and develop methods to e-
ciently query the objects. They represent a road network as a graph
in which the edges have two attributes, the length of the road and the
maximum allowed speed along that path. There are two kinds of uncer-
tainty in this work:
path uncertainty
,thatis,whichpath(sequenceof
edges) did the object take to get from the last position to the next, and
location uncertainty
, given the path, the actual location of the object at
time
t
. Path uncertainty arises from the object selecting a specific route
due to some criteria (i.e. trac, road work, landmarks) and location
uncertainty arises from the fact that we don't know how fast the object
was moving the entire time, though we can bound this by the maximum
allowable speed on each segment.
In [100], the authors propose a novel index structure for processing
range queries on uncertain objects over road networks called the Uncer-
tain Trajectory Hierarchy (UTH). The UTH consists of three levels: (i)
a network edge hash table, (ii) a movement R-tree, and (iii) a trajec-
tory list. The edge hash table allows fast retrieval of any specific road
segment. The movement R-tree is an index over time for a specific road
segment which allows us to identify the set of objects traveling along
a road over a given time interval. Lastly, the trajectory list stores the
actual trajectory for each object. A filter and refinement approach to
answering uncertain path queries on road networks is developed by the
authors by leveraging the UTH index.
Hua and Pei [32] also study the problem of answering path queries
on road networks, however, in this case it is the edge speeds (or flow)
that are uncertain, not the positions of the moving objects. The authors
introduced a network model in which adjacent edges in the road network
were correlated and they introduce exact and more ecient approximate
methods for computing the probability of paths. They also provide an
A
∗
-like algorithm for eciently finding the most probable paths under
specific speed constraints.
Kim et al. [43] develop an index structure for objects with movements
that are restricted to a road network called
Indexing Moving Objects on
road sectors
(IMORS). The index is composed of a static component,
that is made up of an
R
∗
-tree over the road segments, and a dynamic
component, which contains a mapping from road segments to mobile
objects. The dynamic module of the index structure is essentially a
table indexed by object identifiers' that contains attributes of the object
as well as its location and a pointer to the road segment it currently
