Database Reference
In-Depth Information
f
e
c
h
a
d
g
b
Fig. 4.1
Decomposing a set of instances in a VP-tree.
L
(
o
|
LN
(
o
,
C
,
σ ))
, where
L
(
o
|
LN
(
o
,
C
,
σ )
is the likelihood of
o
given objects
LN
.
The following result uses local simple typicality to approximate the simple typi-
cality with a quality guarantee.
(
o
,
C
,
σ )
Final winner:
e
Center(N6)=e
Radius(N6)=dist(e,f)
Neighborhood(N6)={N6,N7,c}
Winner(N6)=e
N1
c
e
N2
N3
e
b
c
h
N4
N5
N6
N7
g
ab
c
d
e
f
h
Fig. 4.2
Computing the approximate most typical instance.
Theorem 4.1 (Local typicality approximation).
Given an uncertain object O,
neighborhood threshold
,
σ )
}
be the instance in C having the largest local simple typicality value, and o
σ
, and a subset C
⊆
O, let
o
=
arg max
o
1
∈
C
{
LT
(
o
1
,
C
,
O
=
arg max
o
2
∈
C
{
T
(
o
2
,
O
)
}
be the instance in C having the largest simple typicality
value. Then,
e
−
σ
2
1
h
√
2
T
(
o
,
O
)
−
T
(
o
,
O
)
≤
(4.2)
2
h
2
π
Moreover, for any object x
∈
C,
1
h
√
2
e
−
σ
2
1
h
√
2
T
(
x
,
O
)
−
LT
(
x
,
C
,
O
,
σ )
<
≤
(4.3)
2
h
2
π
π