Database Reference
In-Depth Information
Algorithm 4.2
RandomTyp(
O
,
k
,
t
,
v
)
Input:
an uncertain object
O
, positive integer
k
, tournament size
t
and number of validations
v
Output:
approximation to the answer to a top-
k
simple typicality query
A
Method:
1:
A
=
0
2:
for
i
=
1to
k
do
−
A
O
=
3:
O
4:
candidate
=
0
5:
for
j
=
1to
v
do
6:
repeat
t
,
g
i
∈
G
g
i
n
t
S
)
7:
G
=
{
g
i
}
(1
≤
i
≤
,
|
g
i
|
=
=
8:
for all
group
g
∈
G
do
9:
winner
g
=
ExactTyp
(
g
,
1
)
O
=
O
−
10:
g
∪
winner
g
11:
end for
until
|
O
|
=
12:
1
13:
candidate
=
candidate
∪
O
14:
end for
15:
A
=
A
∪{
arg max
o
∈
candidate
{
T
(
o
,
O
)
}}
16:
end for
To approximate the second most typical instance, we run the randomized tourna-
ment again with the following constraint: the most typical instance already chosen
in the previous tournament cannot be selected as the winner in this tournament. The
final winner in the second tournament is the approximation of the second most typ-
ical instance. Continuing in this manner, we can find an approximation to the set of
top-
k
typical instances by running a total of
k
tournaments.
In order to achieve a higher accuracy, we can run this randomized tournament
several times for selecting the approximation of the
i
-th most typical instance
(
1
≤
i
, and pick the instance with the largest simple typicality among all the final
winners. The procedure is given in Algorithm 4.2.
The typicality computation within one group has the time complexity of
O
≤
k
)
t
2
(
)
.
There are
log
t
n
tournament rounds in total. Without loss of generality, let us as-
t
t
m
. Then, the first round has
t
n
t
2
groups,
sume
n
=
groups, the second round has
t
=
log
t
n
n
n
t
−
1
(
1
t
m
n
t
)
and so forth. The total number of groups is
∑
=
1
−
)=
O
(
. The
1
≤
i
≤
t
i
t
2
n
t
(
·
)=
(
)
complexity of selecting the final winner is
O
. If we run each tour-
nament
v
times for better accuracy, and run tournaments to choose top-
k
typical
instances, the overall complexity is
O
O
tn
.
The randomized algorithm runs in linear time with respect to the number of in-
stances. However, the accuracy of the approximation to the answer is not guaranteed
in theory, though in practice it often has reasonable performance.
(
kvtn
)
