Database Reference
In-Depth Information
8.2.2.1 Constant Estimates
Trivially, we can set
1
,
x
2
≥
0;
h
P
2
|
e
(
x
2
|
y
)=
0
,
otherwise.
Then, the evaluation function becomes
)=
∑
x
1
+
Δ (
,
(
,
)=
F
P
1
(
)
v
i
l
f
P
1
,
e
x
1
y
l
y
≤
l
In this case, at each step, P* always visits the vertices
v
i
that maximize the
l
-weight probability of
P
1
=
u
,...,
v
i
. The subpaths
u
,...,
v
j
whose current
l
-
weight probability is smaller than
τ
are pruned.
Example 8.3 (Constant estimates). Consider the probabilistic graph in Figure 2.6.
To answer a query Q
0
.
3
15
. The search starts from A. Using the
constant esti-
mates
, the evaluation functions for B and C are:
(
A
,
E
)
)=
∑
x
1
≤
15
)=
∑
x
1
≤
15
Δ (
B
,
15
f
AB
(
x
1
)=
0
.
6
,
and
Δ (
C
,
15
f
AC
(
x
1
)=
1
.
0
.
Since
Δ (
C
,
15
)
is larger, C should be explored first.
The constant value estimates are easy to construct. But clearly, the constant value
estimates do not consider the relationship between the current vertex to the unvisited
end vertex
v
.
8.2.2.2 Min-Value Estimates
To incorporate more information about the unexplored paths into decision making,
we consider the minimal possible weights from the current vertex
v
i
to the end
vertex
v
. We construct a certain graph
G
with the same set of vertices and edges as
the uncertain graph
G
. For each edge
e
, the weight of
e
is the minimal value in
w
e
of
G
. Let
l
mi
i
be the weight of the shortest path between
v
i
and
v
, excluding the visited
edges. Let the estimation function be
1
l
min
i
,
x
2
=
;
h
P
2
|
e
(
x
2
|
y
)=
0
,
otherwise.
The evaluation function becomes
l
min
i
Δ (
v
i
,
l
)=∑
x
1
+
y
+
l
min
i
l
f
P
1
,
e
(
x
1
,
y
)
×
h
P
2
|
e
(
|
y
)
≤
= ∑
x
1
+
y
≤
l
−
l
min
i
f
P
1
,
e
(
x
1
,
y
)
l
min
i
=
F
P
1
(
l
−
)
