Database Reference
In-Depth Information
approximating the probability that two vertices in a random graph are connected is
NP-hard.
3.7.1.1 How Is Our Study Related?
Our work is different from the above studies in the following three aspects.
First, the probabilistic graph models are different. Many existing studies focus on
simple probabilistic graphs, where probabilistic weights are independent from each
other, such as [136, 144]. Moreover, some methods only work for certain probability
distributions, such as uniform distribution [139] and the Normal distribution [143].
Last, some studies do consider correlations among edge weights. However, only cer-
tain types of correlations are considered, like the dependence with a global hidden
variable [146]. Our model considers arbitrary weight distributions and correlations
between the weights of adjacent edges. It is more capable and flexible for real road
networks.
Second, the path queries are different. Most of the above studies focus on the
optimal path query, where a utility function is adopted to evaluate the optimality
of paths. However, using a single simple aggregate as the utility score may not
capture traffic uncertainty sufficiently, since the probability of optimality is often
very small. To tackle the problem, we propose probabilistic path queries and two
top-
k
path queries.
Last, the query answering techniques are different. We propose a novel best-first
search algorithm for probabilistic path queries. Moreover, we develop a hierarchi-
cal partition tree to index the road network structure and weight distribution infor-
mation. Our query answering methods are efficient and scalable thanks to the two
techniques.
3.7.2 Path Queries on Certain Traffic Networks
The shortest path queries on traffic networks have been studied extensively before.
Please see [149] for a nice survey. The optimal algorithms often adopt dynamic pro-
gramming and are not scalable for large scale traffic networks. As a result, heuristic
algorithms that provide high quality approximate answers with short response time
are developed.
The well known A* algorithm [150, 151] uses a heuristic evaluation function
f
(
x
)=
g
(
x
)+
h
(
x
)
to measure the optimality of the current explored path, where
g
(
x
)
is the cost from the start vertex to the current vertex, and
h
(
x
)
is the heuristic
estimation of the distance to the goal. The paths with smaller
f
(
x
)
score are explored
earlier.
Sanders and Schultes [152, 153] proposed a “highway hierarchy” for large scale
traffic networks, which captures the key edges that are on the shortest paths between
two far away vertices. Then, the shortest path search is restricted to those key edges.
