Database Reference
In-Depth Information
1
1
0.8
0.8
0.6
0.6
0.4
0.4
CDF(e_opt)
CDF(BD)
CDF(DE)
CDF(BE)
0.2
0.2
CDF(P_opt)
CDF(BDE)
0
0
0
10
20
30
40
50
60
0
10 20 30 40 50 60 70 80 90
Weight
Weight
(a) CDF of
w
e
opt
.
(b) CDF of
w
P
opt
.
Fig. 8.5
CDFs of “virtual optimal” edges and paths.
l
min
i
(
−
)
The search algorithm always visits the vertex
v
i
that maximizes the
l
-
l
min
j
weight probability of
P
1
=
,...,
,...,
(
−
)
u
v
i
. The subpaths
u
v
j
whose
l
-
weight probabilities are smaller than
τ
are pruned.
Example 8.4 (Min-value estimates). Consider the probabilistic graph in Figure 2.6
and query Q
0
.
3
again. Using the
min-value estimates
, we construct a certain
graph G
with weights w
AB
=
15
(
A
,
E
)
5
,w
AC
=
5
,w
BD
=
20
,w
BE
=
5
,w
CE
=
10
, and w
DE
=
10
.
The shortest distance from B to E through the unvisited edges in G
is
5
. The
evaluation function for B is
3
. The shortest dis-
tance from C to E in G
is
10
. The evaluation function for C is
Δ (
B
,
15
)=
∑
x
1
≤
15
−
5
f
AB
(
x
1
)=
0
.
Δ (
C
,
15
)=
∑
x
1
≤
15
−
10
f
AC
(
is larger, B should be explored first. More-
over, there is no need to visit C further because
x
1
)=
0
.
2
. Since
Δ (
B
,
15
)
Δ (
C
,
15
)
<
τ
.
Compared to the
constant estimates
, the
min-value estimates
consider more infor-
mation about the unexplored paths, and give priority to the vertices that are closer
to the end vertex
v
and are more likely to satisfy the query. The drawback of the
min-value estimates is that they do not consider the probabilistic distribution of un-
explored paths.
8.2.2.3 Stochastic Estimates
How can we incorporate the probability distribution information of the unexplored
paths in heuristic estimates? Let
P
=
{
P
2
1
,...,
P
2
m
}
be all paths from
v
i
to
v
that
do not contain any visited vertices except for
v
i
. We can construct a “virtual path”
P
opt
2
=
v
i
,...,
v
such that for any real number
x
and
P
2
i
∈P
2
,
F
P
opt
(
x
)
≥
F
P
2
i
(
x
)
.
Definition 8.1 (Stochastic order [191]).
For two random variables
r
1
and
r
2
with
distribution functions
F
r
1
(
x
)
and
F
r
2
(
x
)
, respectively,
r
1
is smaller than
r
2
in stochas-
tic order if for any real number
x
,
F
r
1
(
x
)
≥
F
r
2
(
x
)
.
