Database Reference
In-Depth Information
x
n
x
d
=
0
Pr
(
G
t
,
x
d
)
·
g
t
−
1
(
v
i
−
x
d
)
g
t
(
v
i
)=
Therefore,
x
d
=
0
Pr
(
G
t
,
x
d
)
·
g
t
−
1
(
v
i
−
x
d
)
−
g
t
−
1
(
v
i
−
x
d
)
|
x
n
g
t
(
|
g
t
(
v
i
)
−
v
i
)
|
=
|
Let
x
c
(1
. Suppose
x
c
−
1
≤
x
c
≤
c
≤
ρ
) be the
ρ
-quantiles of
f
t
−
1
(
x
)
v
i
−
x
d
≤
(1
≤
), there are two cases:
First, if
v
i
−
c
≤
ρ
x
c
−
1
+
x
c
c
−
1
c
−
1
ρ
≤
c
ρ
, then
g
t
−
1
(
x
d
≤
v
i
−
x
d
)=
and
g
t
−
1
(
v
i
−
x
d
)
≤
.
2
ρ
1
ρ
g
t
−
1
(
Thus, 0
≤
g
t
−
1
(
v
i
−
x
d
)
−
v
i
−
x
d
)
≤
.
x
c
−
1
+
x
c
, then
g
t
−
1
(
c
ρ
c
−
1
c
ρ
Second, if
v
i
−
x
d
>
v
i
−
x
d
)=
and
ρ
≤
g
t
−
1
(
v
i
−
x
d
)
≤
.
2
1
g
t
−
1
(
Thus,
−
ρ
≤
g
t
−
1
(
v
i
−
x
d
)
−
v
i
−
x
d
)
≤
0.
g
t
−
1
(
1
ρ
In both cases,
|
g
t
−
1
(
v
i
−
x
d
)
−
v
i
−
x
d
)
|≤
. Therefore,
x
n
x
d
=
0
Pr
(
G
t
,
x
d
)
·
1
ρ
=
1
ρ
.
g
t
(
|
g
t
(
v
i
)
−
v
i
)
|≤
Using the above approximation method, the overall complexity of computing the
approximate
k
equi-depth histogram answer is
O
2
(
m
ρ
)
, where
m
is the number of
connected components.
7.6.2.3 Sum/Average Queries
The query answering algorithm for
count
queries can be extended to evaluate
sum
and
average
queries with minor changes.
To answer a
sum
query
Q
sum
, we apply the same preprocessing techniques dis-
cussed in Sections 7.3 and 7.4. The only difference is that the private vertices in
the same clique with the same value in attribute
are compressed as one vertex.
When scanning each clique, the
sum
distribution of its subtree are computed and
passed to its parent clique. The overall complexity is
O
A
n
2
, where
n
is the number
of values in
v
min
, the smallest value of any linkage in attribute
(
)
A
, and
v
max
, the sum
of the values of all linkages in attribute
A
. The
average
query can be evaluated
similarly.
