Database Reference
In-Depth Information
Algorithm 6.1.4:
Heaviest First(
v,θ
)
(
λ
1
,
1)
,...,
(
λ
v
m
,m
)
s.t.
W
(
λ
i
)
W
(
λ
j
)
,i<j
Tokenize query:
v
=
{
}
≥
M
is a list of (
s,
N
s
,
s
1
) sorted in (
s
1
, s
) order
M
←∅
τ
=
v
1
for
i
←
1
to
m
Seek to first element of
L
(
λ
i
) with
s
≥
θ
v
1
1
(
r,
N
r
,
r
1
)
←
M.
last
1
,
θ
)
µ
= max(
r
W
(
λ
i
)
τ
=
τ
−
(
r,
M.
first
while
not at end of
L
(
λ
i
)
N
r
,
r
1
)
←
L
(
λ
i
)
.
next
(
s,
s
1
)
←
if
1
>µ
then
break
while
r
1
≤s
1
and
r
=
s
s
if
N
r
+
τ
≤
θ
max(
r
|
1
,
v
1
)
then
do
remove
r
from
M
(
r,N
r
,r
1
)=
M.
next
if
r
=
s
then
M
do
N
r
+
W
(
λ
i
)
,
←
(
r,
r
1
)
else if
W
(
λ
i
)+
τ
≥
θ
max(
s
1
,
v
1
)
then
Insert (
s, W
(
λ
i
)
,
s
1
) at current position in M
while
not at end of
M
(
r,
N
r
,
r
1
)=
M.
next
do
if
N
r
+
τ<θ
max(
r
1
,
v
1
)
then
remove
r
from
M
Report (
s,
N
s
,
s
1
)
∈
M
s.t.
N
≥
θ
max(
s
1
,
v
1
)
s
first
algorithm with the only difference being that once the potential
score of an unseen candidate (a candidate that might be included in
all remaining lists) is smaller than the query threshold, the algorithm
reverts to random access mode that probes the remaining lists to
complete the scores of all candidates left in the candidate set. If an
