Database Reference
In-Depth Information
Algorithm 4 Input:
n
objects
G
1
,...,G
n
, where each
G
i
describes the following data:
(1) a tuple
t
i
(2) an unknown probability
p
i
(3) a lower bound
L
i
and an upper bound
U
i
such that
p
i
∈[
L
i
,U
i
]
.
Output:
The set
Top
k
.
1:
while
true
do
2:
L
c
max
k
(L
1
,...,L
n
)U
c
=
=
max
k
(U
1
,...,U
n
)
B
k
={
t
i
|
U
i
≤
L
c
}
T
k
={
t
i
|
U
c
≤
L
i
}
3:
if
U
c
L
c
≤
then
4:
return
Top
k
=
T
k
5:
end if
6:
such that
L
i
<L
c
,
U
c
<U
i
[
L
i
,U
i
]
if
exists
then
7:
G
i
is a
double crosser
: simulate
G
i
one step.
8:
end if
9:
such that
L
i
<L
c
<U
c
=
L
c
<U
c
<U
j
then
if
exists
[
L
i
,U
i
]
,
[
L
j
,U
j
]
=
U
i
,
L
j
10:
G
i
,G
j
are
lower/upper crossers
: simulate both
G
i
,G
j
one step.
11:
end if
12:
such that
L
i
≤
L
c
,
U
c
Choose a
maximal crosser
[
L
i
,U
i
]
≤
U
i
.
13:
Simulate
G
i
one step.
14:
15:
end while
the condition
L
i
<L
c
continues to hold after any number of simulation steps; hence, we always
have
t
i
∈
T
k
. By the same argument
t
i
∈
B
k
.By
6.2
, when the critical region becomes empty, then
B
k
∪
T
k
=[
B
k
nor
T
k
contains
t
i
. Consider now case
n
]
, but this contradicts the fact that neither
2, and let
L
i
<L
c
<U
c
=
U
i
and
L
j
=
L
c
<U
c
<U
j
be a lower and upper crosser, respectively.
Then
t
i
∈
T
k
and
t
j
∈
B
k
. Consider any sequence of simulations that does not touch the tuples
t
i
or
t
j
but causes the critical region to become empty. That sequence must either decrease
U
c
,
causing
t
i
∈
B
k
, or it must increase
L
c
, causing
t
j
∈
T
k
, both contradicting the fact that, when
B
k
∪
T
k
=[
n
]
the critical region becomes empty,
. Finally, for case 3, assume there are only upper
crossers, and that
L
i
=
L
c
<U
c
≤
U
i
is a maximal upper crosser; then
t
i
∈
B
k
. Assume a sequence
of simulations that do not touch the tuple
t
i
: it will continue to hold that
t
i
∈
B
k
; hence, when the
algorithm terminates, it must be the case that, upon termination,
t
i
∈
T
k
: this means that
L
c
will
remain unchanged during these simulations, implying that
T
k
also remains unchanged during these
additional simulation steps. That means that at the time the algorithm inspected the crosser
t
i
we
|
T
k
|=
had
k
, contradicting the fact that the critical region is non-empty.
Finally, we consider the case when some probabilities are equal,
p
i
=
p
j
. If the set
Top
k
is
uniquely defined, then one can show that the algorithm works unchanged. However, if the ties
between probabilities cause
Top
k
to be ill-defined, then the algorithm will never terminate, and the
