Database Reference
In-Depth Information
e
−
σ
2
1
1
√
2
∑
z
∈
(
O
−
LN
(
C
,
O
,
σ ))
(
G
h
(
o
,
z
)
−
G
h
(
o
,
z
))
≤
2
h
2
|
O
|
π
(
,
,
,
σ )
≥
(
,
,
,
σ )
(
,
,
,
σ )
−
(
,
,
,
σ )
≤
Since
LT
o
C
O
LT
o
C
O
,
LT
o
C
O
LT
o
C
O
0. Thus,
1
h
√
2
e
−
σ
2
(
,
)
−
(
,
)
≤
T
o
O
T
o
O
2
h
2
π
Inequality 4.2 is shown.
From Theorem 4.1, we can also derive the minimum neighborhood threshold
value
σ
to satisfy certain approximation quality.
Corollary 4.1 (Choosing neighborhood threshold).
Given
an uncertain o
bject O,
an instance x
2ln
√
2
∈
S, and a quality requirement
θ
,if
σ
≥
−
πθ
h
·
h, then
T
(
x
,
O
)
−
LT
(
x
,
C
,
O
,
σ )
<
θ
for any subset C
(
x
∈
C
)
.
Proof.
From Theorem 4.1, for any instance
o
∈
C
, subset
C
⊆
O
and neighborhood
threshold
σ
,wehave
1
h
√
2
e
−
σ
2
T
(
x
,
O
)
−
LT
(
x
,
C
,
O
,
σ )
<
2
h
2
π
e
−
σ
2
1
h
√
2
θ
≤
θ
In order to meet the quality requirement
, it should hold that
2
h
2
.
π
2ln
√
2
Therefore,
σ
≥
−
πθ
h
·
h
.
4.2.2 DLTA: Direct Local Typicality Approximation Using
VP-trees
Inequality 4.3 in Theorem 4.1 can be used immediately to approximate simple typ-
icality computation with quality guarantee. Given a neighborhood threshold
σ
, for
∈
each instance
x
S
, the direct local typicality approximation (DLTA) algorithm
σ
{
}
(
{
},
,
σ )
computes the
-neighborhood of
x
, i.e.,
LN
x
O
and the local simple typi-
cality
LT
(
x
,{
x
},
O
,
σ )
. Then, it returns the
k
instances with the highest local simple
typicality values as the approximation to the answer of the top-
k
simple typicality
query.
The quality of the approximation answer is guaranteed by the following theorem.
Theorem 4.2 (Approximation quality).
Given an uncertain object O, neighbor-
hood threshold
and integer k, let A be the k instances with the highest simple
typicality values, and A be the k instances with the highest local simple typicality
values. Then,
σ
A
T
(
o
,
O
)
−
∑
o
∈
A
T
(
o
,
O
)
∑
1
h
√
2
e
−
σ
2
o
∈
<
(4.7)
2
h
2
k
π
