Database Reference
In-Depth Information
Algorithm 6.2.1:
Heaviest First top-k(
v,k
)
(
λ
1
,
1)
,...,
(
λ
v
m
,m
)
s.t.
W
(
λ
i
)
W
(
λ
j
)
,i<j
Tokenize query:
v
=
{
}
≥
M
is a list of (
s,
I
s
) pairs sorted in
s
order
H
is a min-heap of at most
k
pairs (
s,
I
s
)
,
sorted in
I
s
order
M
←∅
,H
←∅
τ
=
v
1
,θ
=0
for
i
←
1
to
m
if
τ<θ
and
M
is empty
then
break
τ
=
τ
W
(
λ
i
)
−
(
r,
M.
first
while
not at end of
L
(
λ
i
)
I
r
)
←
L
(
λ
i
)
.
next
while
r
(
s
)
←
≤
s
do
if
θ
then
remove
r
from
M
(
r,I
r
)
← M.
next
I
r
+
τ
≤
if
r
=
s
I
r
+
W
(
λ
i
))
if
|H| <k
then
H ←
(
r,I
r
+
W
(
λ
i
))
else if
r
M
←
(
r,
∈
H
then
H.
pop(
r
)
,H
then
I
r
+
W
(
λ
i
))
else if
I
r
+
W
(
λ
i
)
>θ
then
H
←
←
(
r,
do
r
+
W
(
λ
i
))
,H.
pop
else if
W
(
λ
i
)+
τ>θ
(
r,
I
Insert (
s, W
(
λ
i
)) at current position in
M
if
(
s, W
(
λ
i
))
else if
W
(
λ
i
)
>θ
then
H
then
|
H
|
<k
then
H
←
(
s, W
(
λ
i
))
,H.
pop
←
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,
I
s
)
∈
H