Database Reference
In-Depth Information
-th level of tournaments, let
o
i
+
1
be the winner of the group
containing
o
i
in this tournament, then again we have
If
o
i
fails the
(
i
+
1
)
1
h
√
2
e
−
σ
2
T
(
o
i
,
O
)
−
T
(
o
i
+
1
,
O
)
<
2
h
2
π
For a set of instances in
O
, there are
log
t
|
O
|
levels of tournaments. The final win-
ner
o
is the winner in the
log
t
|
O
|
-th level of tournaments. That is,
o
=
o
log
t
|
O
|
.
Then,
T
(
o
,
O
)
−
T
(
o
,
O
)=
T
(
o
,
O
)
−
T
(
o
1
,
O
)+
T
(
o
1
,
O
)
−
T
(
o
2
,
O
)+
...
e
−
σ
2
1
h
√
2
+
T
(
o
log
t
|
O
|−
1
,
O
)
−
T
(
o
log
t
|
O
|
,
O
)
<
·
log
t
|
O
|
2
h
2
π
The inequality in the theorem holds.
The LT3 algorithm combines the merits of both local typicality approximation
and the tournament mechanism. It achieves better accuracy than the randomized
tournament algorithm, thanks to the local grouping. It is more efficient than the
DLTA algorithm because of the tournament mechanism. As shown in our experi-
ments, the approximations of the most typical instances computed by the LT3 algo-
rithm are very close to the exact ones. LT3 is very efficient and scalable.
4.2.3.3 A Sampling Method for Bounding Runtime
To make the analysis complete, here we provide a sampling method which provides
an upper bound on the cost of local typicality computation with quality guarantee.
Suppose we want to compute the local simple typicality
LT
(
p
,
C
,
O
,
σ )
. We con-
sider the contribution of an object
o
∈
LN
(
C
,
O
,
σ )
to
LT
(
p
,
C
,
O
,
σ )
, denoted by
2
d
(
p
,
o
)
e
−
1
2
h
2
√
2
η(
o
)=
G
h
(
p
,
o
)=
|
(
,
,
σ )
|
h
LN
C
O
h
|
LN
(
C
,
O
,
σ )
|
π
(
,
,
σ )
η(
)
We can draw a sample of
LN
C
O
to estimate the expectation of
o
. Please
note that
LT
(
p
,
C
,
O
,
σ)=
|
LN
(
C
,
O
,
σ )
|·
E
[η(
o
)]
where
E
.
Using the Chernoff-Hoeffding bound [181], we derive the minimum sample size
to achieve the required accuracy.
Theorem 4.4.
For any
[η(
o
)]
is the expectation of
η(
o
)
for
o
∈
LN
(
C
,
O
,
σ )
δ (
0
<
δ
<
1
)
and
ε (ε
>
0
)
and a sample R of LN
(
C
,
O
,
σ )
,
2
2
h
2
3
h
√
2
π
·
e
σ
ln
2
δ
·
if
|
R
|>
, then
2
ε
{|
|
LN
(
C
,
O
,
σ )
|
o
∈
R
η(
o
)
−
LT
(
p
,
C
,
O
,
σ )
|>
ε
·
LT
(
p
,
C
,
O
,
σ )
}<
δ
Pr
|
R
|
