Database Reference
In-Depth Information
is
O
. If we run each tournament
v
times for better accuracy, then the overall
complexity of answering a top-
k
discriminative typicality query is
O
(
mt
)
(
kvtm
)
.
4.3.2 Local Typicality Approximation
Similar to the local simple typicality approximation discussed in Section 4.2.1, we
can define the local discriminative typicality as follows.
Definition 4.4 (Local discriminative typicality).
Given two uncertain objects ob-
jects
O
and
S
on attributes
A
1
,···,
σ
U
A
n
and a neighborhood threshold
, let
and
be the random vectors generating
O
and
S
, respectively, the
local dis-
criminative typicality
of an instance
o
V
∈
O
on attributes
A
i
1
,···,
A
i
l
is defined as
LDT
(
o
,U ,V ,
σ)=
LT
(
o
,{
o
},U ,
σ )
−
LT
(
o
,{
o
},V ,
σ )
, where
LT
(
o
,{
o
},U ,
σ )
and
LT
(
o
,{
o
},V ,
σ )
are the local simple typicality values of
o
in
U
and
V
, respec-
tively.
LDT
(
o
,U ,V ,
σ )
can be estimated using
LDT
(
o
,
O
,
S
,
σ)=
LT
(
o
,{
o
},
O
,
σ )
−
LT
(
o
,{
o
},
S
,
σ )
, where
LT
(
o
,{
o
},
O
,
σ )
and
LT
(
o
,{
o
},
S
,
σ )
are the estimators of
local simple typicality values of
o
in
O
and
S
, respectively.
Similar to Theorem 4.1, we have the following quality guarantee of local dis-
criminative typicality approximation.
Theorem 4.5 (Local discriminative typicality approximation).
Given two uncer-
tain
objects O and
S
and
a
neighborhood
threshold
σ
,
let
o
be the instance in O having the largest local
discriminative typicality value, and o
=
arg max
o
1
∈
O
{
LDT
(
o
1
,
O
,
S
,
σ )
}
=
arg max
o
2
∈
O
{
DT
(
o
,
O
,
S
)
}
be the instance
in O having the largest discriminative typicality value. Then,
2
h
√
2
e
−
σ
2
DT
(
o
,
O
,
S
)
−
DT
(
o
,
O
,
S
)
<
2
h
2
(4.8)
π
Moreover, for any x
∈
O,
1
h
√
2
e
−
σ
2
|
DT
(
x
,
O
,
S
)
−
LDT
(
x
,
O
,
S
,
σ )
|<
(4.9)
2
h
2
π
Proof.
For any instance
x
∈
O
,
1
h
|
O
|
y
∈
O
G
h
(
x
,
y
)
−
1
h
|
S
|
∑
z
DT
(
x
,
O
,
S
)=
G
h
(
x
,
z
)
(4.10)
∈
(
S
)
For simplicity, let us denote
LN
(
{
x
},
S
,
σ )
by
N
.Wehave
y
∈
O
G
h
(
x
,
y
)=
∑
∑
y
2
∈
(
G
h
(
x
,
y
1
)+
G
h
(
x
,
y
2
)
y
1
∈
O
∩
N
O
−
N
)
and
