Database Reference
In-Depth Information
Lemma 8.3 (Approximation quality).
Given a real value l
>
0
and an integer t
>
be a set of buckets of w
P
m
. Let F
P
m
+
1
(
and F
P
m
+
1
(
0
, let
{
φ
i
=[
x
z
i
,
x
z
i
]
}
l
)
l
)
be the
l-weight probabilities computed using
{
min
(φ
i
)
}
and
{
max
(φ
i
)
}
, respectively, then,
1
t
F
P
m
+
1
(
F
P
m
+
1
(
l
)
−
l
)
≤
(8.4)
Moreover,
1
2
t
|
F
P
m
+
1
(
l
)
−
F
P
m
+
1
(
l
)
|≤
(8.5)
F
P
m
+
1
(
F
P
m
+
1
(
l
)+
l
)
where F
P
m
+
1
(
)=
l
.
2
Proof.
F
P
m
+
1
(
F
P
m
+
1
(
is the sum of the probability of the shaded area in Fig-
ures 8.3(a) and 8.3(b). In each bucket
b
i
, the width of the shaded area is
Pr
l
)
−
l
)
1
t
.
The length sum of all pieces of shaded are is at most 1. Thus, the probability of the
shaded area is at most
(
b
i
)
<
1
t
. Inequality 8.4 is proved.
Conclusion 8.5 is derived from Inequalities 8.4 directly.
1
t
×
1
=
After obtaining the approximate probability distribution of
w
P
m
+
1
, we can further
divide the approximate
w
P
m
+
1
into buckets, and compute the approximate probability
distribution of
w
P
m
+
2
. By applying the bucket approximation iteratively, we finally
obtain an approximate
l
-weight probability of path
P
, and the approximation quality
is guaranteed by the following theorem.
Theorem 8.2 (Overall approximation quality).
Given a real value l
>
0
, an inte-
>
=
,...,
(
)
ger t
0
, and a path P
v
1
v
m
+
1
containing m edges, let F
P
l
be the exact
l-weight probability and F
P
be the approximate l-weight probability computed
using iterative bucket approximation, then
(
l
)
|
F
P
m
−
1
(
l
)
−
F
P
(
l
)
|≤
.
2
t
Proof.
P
contains
m
edges, so
m
1 steps of bucket approximation are needed to
compute the probability distribution of
P
. We prove the theorem using Mathematical
Induction.
In the first step (computing the probability of
P
3
=
−
|
F
P
3
(
v
1
,
v
2
,
v
3
), we have
l
)
−
1
F
P
3
(
2
t
, which is shown in Lemma 8.3.
Suppose the conclusion holds for the
l
)
|≤
(
j
−
1
)
-th step (computing the probability
of
P
j
+
1
). That is,
j
−
1
|
F
P
j
+
1
(
)
−
F
P
j
+
1
(
)
|≤
l
l
(8.6)
2
t
for any real value
l
0.
To compute the probability distribution of
w
P
j
+
2
, the approximate weight of
w
P
j
+
1
is divided into buckets, such that the probability of each bucket
b
i
=[
>
x
i
]
x
i
,
is at most
1
t
. Since the buckets are constructed based on the approximation probability distri-
bution of
P
j
+
1
,wehave
Pr
b
i
)=
F
P
j
+
1
(
x
i
)
−
F
P
j
+
1
(
x
i
−
1
)
≤
1
(
t
. From Inequality 8.6,
|
F
P
j
+
1
(
j
−
1
|
F
P
j
+
1
(
j
−
1
x
i
)
−
x
i
)
|≤
x
i
−
1
)
−
x
i
−
1
)
|≤
we have
F
P
j
+
1
(
and
F
P
j
+
1
(
, the ac-
2
t
2
t
j
t
. Using
the similar proof of Lemma 8.3, the approximation quality of
P
j
+
2
(the
j
-th step)
can be derived as
1
t
+
j
−
1
2
t
×
x
i
)
−
x
i
−
1
)=
tual probability of
b
i
is
Pr
(
b
i
)=
F
P
j
+
1
(
F
P
j
+
1
(
2
=
|
F
P
j
+
2
(
j
2
t
.
x
)
−
F
P
j
+
2
(
x
)
|≤
