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
 
Search WWH ::




Custom Search