Database Reference
In-Depth Information
Applying Inequality 4.14 to
o
and
o
,wehave
1
h
√
2
e
−
σ
2
|
RT
(
o
,
A
,
O
)
−
LRT
(
o
,
A
,
O
,
σ )
|<
2
h
2
π
and
1
h
√
2
e
−
σ
2
|
RT
(
o
,
A
,
O
)
−
LRT
(
o
,
A
,
O
,
σ )
|<
2
h
2
π
Since
LRT
(
o
,
A
,
O
,
σ )
≥
LRT
(
o
,
A
,
O
,
σ )
RT
(
o
,
A
,
O
)
−
RT
(
o
,
A
,
O
)
(
(
=(
RT
(
o
,
A
,
O
)
−
LRT
(
o
,
A
,
O
,
σ ))
−
(
RT
o
,
A
,
O
)
−
LRT
o
,
A
,
O
,
σ ))
e
−
σ
2
2
h
√
2
+(
LRT
(
o
,
A
,
O
,
σ )
−
LRT
(
o
,
A
,
O
,
σ ))
≤
2
h
2
π
Inequality 4.13 is shown.
4.4.3.1 DLTA: Direct Local Typicality Approximation
Direct local representative typicality approximation (DLTA) follows the similar
framework of the exact algorithm described in Section 4.4.1. The only difference
is that the local representative typicality score instead of the representative typical-
ity score is computed.
To compute the local representative typicality score of an instance
o
given
answer set
A
, one critical step is to compute the local group typicality score
LGT
. The computation is similar to the exact algorithm elaborated in
Section 4.4.1, except that the local simple typicality instead of the simple typicality
of
o
in
N
(
A
∪{
o
},
O
,
σ )
(
o
,
A
,
O
)
is used to compute
LGT
(
A
∪{
o
},
O
,
σ )
.
0) contains the first
i
answers to a top-
k
representative typicality query, computing the local simple
typicality of an instance
o
Suppose the current reported answer
A
i
(0
≤
i
<
k
,
A
0
=
∈
(
−
)
(
|
(
{
},
(
,
,
)
,
σ )
|
)
O
A
i
takes
O
LN
o
N
o
A
O
, where
LN
(
{
o
},
N
(
o
,
A
,
O
)
,
σ )
is the
σ
-neighborhood of
o
in the set of its represented
members
N
(
o
,
A
,
O
)
. Thus, the complexity of computing the
(
i
+
1
)
-th answer is
O
(
∑
o
∈
(
O
−
A
i
)
|
.
The overall complexity of answering a top-
k
representative typicality query is
LN
(
{
o
},
N
(
o
,
A
,
O
)
,
σ )
|
)
k
−
1
i
=
0
O
. In the worst case, the local neighbor-
hood of any instance
o
may contain the whole data set. Moreover,
A
i
contains
i
ob-
jects, so
(
∑
∑
o
∈
(
O
−
A
i
)
|
LN
(
{
o
},
N
(
o
,
A
,
O
)
,
σ )
|
)
|
O
−
A
i
|
=
n
−
i
. Therefore, the overall complexity of the DLTA algorithm
k
−
1
i
=
0
((
·
(
2
n
−
k
−
1
)
k
2
kn
2
is
O
(
∑
n
−
i
)
·
n
)) =
O
(
n
)=
O
(
)
.
4.4.3.2 LT3: Local Typicality Approximation Using Tournaments
The LT3 algorithm for simple typicality approximation can be used to answer top-
k
representative typicality queries. To find the instance with the largest representative
