Database Reference
In-Depth Information
1
∑
μ
≤
h
≤
m
f
t
−
1
(
x
h
)
≥
−
ε
On the other hand,
∑
μ
≤
h
≤
m
f
t
−
1
(
x
h
)
≥
1
−
ε
, and thus 1
−
.
1
−
ε
p
i
−
ε
1
Moreover,
p
i
−
p
i
−
ε
. Therefore,
p
i
−
p
i
≥−
ε
×
A
≥
−
ε
≥−
ε
.
Therefore, after integrating
m
components, we have
|
p
i
−
p
i
|≤
ε
.
After the probability adjustment,
f
i
−
1
(
holds for each value
x
with non-
zero probability. Thus, the number of values with non-zero probability is at most
1
ε
x
)
>
ε
. Therefore, the overall complexity of computing the
ε
-approximation of
f
i
(
x
)
is
1
ε
m
ε
O
(
)
. The overall complexity is
O
(
)
, where
m
is the number of components in
2
2
G
.
7.6.2.2 Equi-depth Histogram Answer Approximation
To accelerate probability calculation for equi-depth histogram answers, we intro-
duce an approximation method that keeps a constant number of values in the inter-
mediate results.
In theorem 7.5, if
f
i
−
1
(
x
)
contains values
x
1
,···,
x
n
i
−
1
(
n
i
−
1
>
k
) in the value
-quantiles
x
i
=
ascending order, then we compute the
ρ
arg min
x
{
Pr
(
Q
(
G
)
≤
x
)
≥
i
ρ
}
(0
≤
i
≤
ρ
). From the
ρ +
1 values, we construct an approximation of
f
i
−
1
(
x
)
as:
1
x
i
−
1
+
x
i
2
ρ
,
x
=
(1
≤
i
≤
ρ
);
f
i
−
1
(
x
)=
(7.11)
0
,
otherwise.
Then, the convolution of
f
i
−
1
(
x
)
and
Q
(
G
i
)
are used to estimate
f
i
(
x
)
. The ap-
proximation quality is guaranteed by the following theorem.
Theorem 7.8 (Approximation quality).
Given a query Q on a PME-graph G with
m components, an integer k
>
0
, let
(φ
i
,
p
i
)
, where
φ
i
=[
v
i
−
1
,
v
i
)(
1
≤
i
≤
k
)
,bethe
equi-depth histogram answer computed using the
ρ
-quantile approximation, then
m
ρ
Pr
(
|
Pr
(
Q
(
G
)
≤
v
i
)
−
Q
(
G
)
≤
v
i
)
|<
where Pr
(
is the probability computed using Equation 7.11.
Proof.
We only need to show that each time when we integrate one connected com-
ponent
G
t
(2
Q
(
G
)
≤
v
i
)
1
ρ
≤
t
≤
m
), we introduce an approximation error of
.
Let
g
t
(
v
i
)=
Pr
(
Q
(
G
)
≤
v
i
)=∑
x
≤
v
i
f
t
(
x
)
and
g
t
−
1
(
x
b
)=∑
x
≤
x
b
f
t
−
1
(
x
)
. Then,
according to Theorem 7.5,
x
n
x
d
=
0
Pr
(
G
t
,
x
d
)
·
g
t
−
1
(
v
i
−
x
d
)
g
t
(
v
i
)=
where
x
n
is the number of cliques in
G
t
.
Let
g
t
−
1
(
Pr
(
f
t
−
1
(
where
f
t
−
1
(
x
b
)=
Q
(
G
)
≤
v
i
)=
∑
x
≤
x
b
x
)
x
)
is the approxima-
tion of
f
t
−
1
(
x
)
using Equation 7.11, then