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.