Database Reference
In-Depth Information
Algorithm 6.1.2:
nra(
v,θ
)
(
λ
1
,
1)
,...,
(
λ
v
m
,m
)
Tokenize the query:
v
=
{
}
M
is an empty map of (
s,
N
s
,B
1
,...B
m
) tuples (
B
i
are bits)
1
to
m
do
Seek to first element of
L
(
λ
i
) s.t.
for
i
←
s
1
≥
θ
v
1
while
there exists an active
L
(
λ
i
)
f
=
∞
,w
=0
for
i
←
1
to
m
if
L
(
λ
i
) is inactive
then
continue
(
s,
L
(
λ
i
)
.
next
s
1
)
←
1
>
v
1
then
make
L
(
λ
i
) inactive
and
continue
if
s
θ
1
)
,w
=
w
+
W
(
λ
i
)
(
s,N
s
,B
1
,...,B
m
)
f
= min(
f,
s
← M.
find(
s
)
for
j
1
to
m
if
j
=
i
or
L
(
λ
j
) is inactive
then
B
j
=1
if
s
←
do
∈
M
if
B
1
=1
,...,B
m
=1
N
s
+
W
(
λ
i
))
/
max(
if
(
s
1
,
v
1
)
≥
θ
then
report
s,
(
N
s
+
W
(
λ
i
))
/
max(
then
then
s
1
,
v
1
)
Remove from
M
N
s
+
W
(
λ
i
)
,B
1
,...,B
m
)
else
M
←
(
s,
else
M
(
s, W
(
λ
i
)
,B
1
,...,B
m
)
←
for all
(
s,
N
s
,B
1
,...,B
m
)
∈
M
for
j ←
1
to
m
if
L
(
λ
j
) is inactive
then
B
j
=1
if
B
1
=1
,...,B
m
=1
do
if
N
s
/
max(
s
1
,
v
1
)
≥
θ
then
report
s,
N
s
/
then
1
)
Remove from
M
max(
s
1
,
v
w
if
max(
f,v
1
)
<θ
and
M
is empty
then
break
