Database Reference
In-Depth Information
0
,
1
≤
i
≤
μ
;
f
i
−
1
(
x
i
)=
(7.9)
x
i
)
∑
μ
≤
h
≤
m
Pr
f
i
−
1
(
x
h
)
,
μ
<
x
≤
m
.
(
-approximation
of the histogram answer. The
quality of the approximation answer is guaranteed by the following theorem.
ε
The computed answer is called the
Theorem 7.7 (Approximation Quality).
Given a query Q on linkages with z com-
ponents, a bucket width parameter
η
, and a minimum probability threshold
τ
, let
(φ
i
,
p
i
)
be the equi-width histogram answer to Q, and
(φ
i
,
p
i
)
be the
ε
-approximation
v
max
−
v
min
of
.
Proof.
We only need to show that each time when we integrate one connected com-
ponent
G
t
(2
(φ
,
p
i
)
, then
|
p
i
−
p
i
|<
z
ε
for
1
≤
i
≤
η
≤
t
≤
m
), we introduce an approximation error of
ε
. Let
x
1
,···,
x
m
be
the list of values in
f
t
−
1
(
x
)
in the probability ascending order,
v
1
=
v
min
+(
i
−
1
)η
. Let
p
i
=
∑
v
1
≤
x
≤
v
2
and
v
2
=
v
min
+
i
η
f
t
(
x
)
be the probability of bucket
[
v
1
,
v
2
)
.
According to Theorem 7.5,
p
i
= ∑
v
1
≤
x
≤
v
2
∑
m
b
=
1
f
t
−
1
(
x
b
)
Pr
(
Q
(
G
t
)=
x
−
x
b
)
m
b
=
1
f
t
−
1
(
x
b
)
∑
v
1
−
x
b
≤
x
≤
v
2
−
x
b
Pr
(
(
)=
)
,
= ∑
Q
G
t
x
where
f
t
−
1
(
x
b
)
is the exact count distribution in components
{
G
1
,···,
G
t
−
1
}
. Let
p
i
= ∑
f
t
(
x
)
be the approximate probability computed based on the
ε
-
v
1
≤
x
≤
v
2
approximation
f
t
−
1
(
x
)
, then
p
i
=
∑
v
1
≤
x
≤
v
2
∑
m
b
=
1
f
t
−
1
(
x
b
)
(
(
)=
−
x
b
)
Pr
Q
G
t
x
m
b
=
1
f
t
−
1
(
=
∑
x
b
)
∑
v
1
−
x
b
≤
x
≤
v
2
−
x
b
Pr
(
(
)=
)
.
Q
G
t
x
Let
g
(
v
1
−
x
b
,
v
2
−
x
b
)
denote
∑
x
b
Pr
(
Q
(
G
t
)=
x
)
.Wehave
v
1
−
x
b
≤
x
≤
v
2
−
m
b
m
b
p
i
−
p
i
= ∑
1
f
t
−
1
(
1
f
t
−
1
(
x
b
)
g
(
v
1
−
x
b
,
v
2
−
x
b
)
−
∑
x
b
)
g
(
v
1
−
x
b
,
v
2
−
x
b
)
=
=
d
=
∑
f
t
−
1
(
x
d
)
g
(
v
1
−
x
d
,
v
2
−
x
d
)
1
f
t
−
1
(
x
b
)
·
=
1
m
b
=μ+
f
t
−
1
(
+
∑
x
b
)
−
g
(
v
1
−
x
b
,
v
2
−
x
b
)
(7.10)
d
Let
A
=
∑
1
f
t
−
1
(
x
d
)
g
(
v
1
−
x
d
,
v
2
−
x
d
)
, then
=
m
∑
p
i
−
f
t
−
1
(
x
b
)
g
(
v
1
−
x
b
,
v
2
−
x
b
)=
A
.
b
=μ+
1
According to Equation 7.9, Equation 7.10 can be rewritten as
1
1
∑
μ
≤
h
≤
m
f
t
−
1
(
p
i
−
p
i
=
p
i
−
A
+
−
(
A
)
x
h
)
1 and
p
i
>
A
,wehave
p
i
−
p
i
≤
On the one hand, since
∑
μ
≤
h
≤
m
f
t
−
1
(
x
h
)
≤
A
.
d
d
. Thus,
p
i
−
Moreover,
A
= ∑
1
f
t
−
1
(
x
d
)
g
(
v
1
−
x
d
,
v
2
−
x
d
)
≤
∑
1
f
t
−
1
(
x
d
)
≤
ε
=
=
p
i
≤
ε
.
