Database Reference
In-Depth Information
Algorithm 4.3
LT3Typ(
O
,
k
,
T
)
Input:
an uncertain object
O
=
{
o
1
,...,
o
n
}
and positive integer
k
and an LT-tree
T
(with
m
levels)
built on
O
whose root node is
N
R
Output:
approximation to the answer to a top-
k
simple typicality query
A
Method:
1:
A
=
0
2:
for
j
=
m
to 0
do
3:
for all
node
N
at level
L
j
do
4:
winner
N
=
arg max
o
∈
N
{
LT
(
o
,
N
,
O
,
σ )
}
5:
N
p
=
N
p
∪{
winner
N
}
*
N
p
is the parent node of
N
{
}
6:
end for
7:
end for
8:
A
=
A
∪{
winner
N
R
}
9:
w
1
=
winner
N
R
10:
for
i
=
2to
k
do
11:
find
N
such that
w
i
−
1
∈
N
*
w
i
−
1
is the last output winner
{
}
12:
while
N
=
N
R
do
13:
winner
N
=
arg max
o
∈
N
,
o
=
w
i
−
1
{
LT
(
o
,
N
,
O
,
σ )
}
14:
N
p
=
N
p
∪{
winner
N
}
15:
N
←
N
p
16:
end while
A
=
A
17:
∪{
winner
N
R
}
18:
w
i
=
winner
N
R
19:
end for
the LT-tree in Figure 4.3, after
e
is selected as the first final winner, it is removed
from node
N
6
. Then, only the tournaments in nodes
N
6
,
N
3
and
N
1
need to be re-
conducted. Finally,
c
is selected as the final winner to approximate the second most
typical point. The complete procedure is shown in Algorithm 4.3.
The quality of the answers returned by the LT3 algorithm can be guaranteed by
the following theorem.
Theorem 4.3.
In an uncertain object O, let o be the instance with the largest simple
typicality and
o be an instance computed by the LT3 method using local typicality
approximation and the tournament group size t. Then,
1
h
√
2
2
h
2
e
−
σ
2
T
(
o
,
O
)
−
T
(
o
,
O
)
<
·
log
t
|
O
|
π
Proof.
In the worst case, instance
o
is not selected as the winner in the first level of
tournaments.
Let
o
1
be the winner of the group containing
o
in the first level of tournaments,
then we have
1
h
√
2
e
−
σ
2
(
,
)
−
(
T
o
O
T
o
1
,
O
)
<
2
h
2
π
as indicated by Inequality 4.2 in Theorem 4.1.
