Database Reference
In-Depth Information
A* is used to find the shortest path between two vertices u and v in a certain
graph. Therefore, the heuristic evaluation function for each vertex v i is simply the
sum of the actual distance between u and v i and the estimated distance between v i
and v .
P* aims to find the paths that satisfy the weight threshold l and probability thresh-
old p between two vertices u and v in a probabilistic graph with complex correlations
among edge weights. Therefore, the heuristic evaluation function for each vertex v i
is the complex joint distribution on a set of correlated random variables. This posts
serious challenges in designing heuristic evaluation functions and calculation.
In this section, we first introduce the intuition of the P* algorithm. Then, we
design three heuristic evaluation functions that can be used in the P* algorithm. In
Section 8.3, a hierarchical index is developed to support efficient query answering
using the P* algorithm.
8.2.1 The P* Algorithm
To answer a probabilistic path query Q l (
, we search the paths from vertex u .
The situation during the search is illustrated in Figure 8.4. Generally, before we
decide to visit a vertex v i , we want to evaluate how likely v i would be included in an
answer path. Suppose P 1 is the explored path from u to v i , and P 2 is an unexplored
path from v i to v , then the probability distribution of the path P from u to v that
contains P 1 and P 2 is given by the following theorem.
u
,
v
)
Theorem 8.4 (Super path probability). Let P 1 =
u
,...,
v i
,P 2 =
v i ,...,
v
such
that
(
P 1
P 2 = {
v i } )
and e
=(
v i 1 ,
v i )
, the l-weight probability of super path P
=
u
,...,
v i ,...,
v
is
(
)=
(
,
) ×
f P 2 | e (
|
)
F P
l
f P 1 , e
x 1
y
x 2
y
(8.7)
x 1 +
y
+
x 2
l
Proof. The weight of P is w P =
w P 1 +
w P 2 . Therefore,
(
)=
[
]=
[
w P 1 +
w P 2
]
F P
l
Pr
w P
l
Pr
l
= x 1 + x 2 l Pr
[
w P 1 =
,
w P 2 =
]
x 1
x 2
= x 1 + x 2 l Pr
[
w P 1 =
]
[
w P 2 =
|
w P 1 =
]
x 1
Pr
x 2
x 1
Since w P 1 and w P 2 are conditionally independent given w e ,wehave
Pr
[
w P 2 =
x 2
|
w P 1 =
x 1
]=∑ y x 1 Pr
[
w P 2 =
x 2
|
w e =
y
]
Equation 8.7 follows directly.
can be easily calculated according to Theorem 8.1.
It also can be computed using the approximation methods discussed in Section 8.1.
However, f P 2 | e (
In Equation 8.7, f P 1 , e (
x 1
,
y
)
|
)
x 2
y
, the probability distribution of P 2 given edge e , is unknown.
 
Search WWH ::




Custom Search