Database Reference
In-Depth Information
Algorithm 6.1.3:
Optimized Multiway Merge(
v,θ
)
(
λ
1
,
1)
,...,
(
λ
v
m
,m
)
Tokenize the query:
v
=
{
}
M
is an empty heap of (
s,
s
1
,
I
s
,i
) tuples, sorted on
s
1
, s
S
is a stack of indexes
i
(
f
1
,
1
)
...,
(
f
m
,
f
1
f
m
1
) are the frontier elements
f
i
=0
,
for
i
←
1
to
m
do
f
i
1
=
θ
v
1
and
S
←
i
while
M
is not empty
or
S
is not empty
if
M
is empty
and
enough lists are inactive
then
break
while
S
is not empty
i
=
S.
pop
Seek to first element of
L
(
λ
i
) s.t.
s
1
≥
f
i
1
f
i
=
s,
1
)=
L
(
λ
i
)
.
next
and
(
s,
s
f
i
s
1
=
1
1
>
v
1
then
make
L
(
λ
i
) inactive
and
if
s
θ
do
continue
if
s
∈
M
then
(
s,
s
1
,
I
s
,j
)
←
M.
find(
s
)
s
+=
W
(
λ
i
)
and
S
I
←
i
1
,W
(
λ
i
)
,i
)
else
M
←
(
s,
s
while
M
is not empty
do
(
r,
r
1
,
I
r
,j
)
←
M.
peek
if
I
r
/
max(
r
1
,
v
1
)
≥
θ
then
Report (
r,I
r
/
max(
r
1
,v
1
))
M.
pop
,S
←
j,
break
τ
=0
for
i
do
←
1
to
m
f
i
if
i
=
j
and
f
i
≤
r
1
and
≤
r
1
then
τ
+=
W
(
λ
i
)
else
if
(
I
r
+
τ
)
/
max(
r
1
,
v
1
)
≥
θ
then
break
else
M.
pop
,S ← j
(
r,
r
1
,
I
r
,j
)
←
M.
peek
1
, f
i
=
r
for all
i
∈
S
do
(
f
i
1
<
r
1
)?
f
i
1
=
r
