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
 
Search WWH ::




Custom Search