Database Reference
In-Depth Information
And for case (2)
π
r
s
∪
r
≥
s
r
−
r
J
1
+
1
1
1
π
r
J
1
J
π
r
≥
r
+
r
−
r
J
⇒
1
1
s
J
(
s, r
)=
s
∩
r
1
s
∪
r
1
π
r
r
J
1
≤
1
J
π
π
r
r
+
r
−
r
J
r
J
s
1
1
π
r
s
J
J
≤
.
π
r
π
r
J
s
+
J
−J
s
J
We denote the new similarity upper bound with
π
r
s
J
J
J
=
.
J
s
+
J
π
r
−J
s
J
π
r
The following holds
xy
Lemma 7.7.
The function
f
(
x, y
)=
x
+
y−xy
is monotonically increas-
ing in
x
and
y
.
Proof.
f
(
x, y
) is monotonically increasing in
x
and
y
if and only if the
function
g
(
x, y
)=
1
f
(
x,y
)
is monotonically decreasing in
x
and
y
. But
g
(
x, y
)=
1
x
+
1
y
−
1
,
which is clearly monotonically decreasing in
x
and
y
.
J
is monotonically
Hence the new upper bound similarity threshold
π
r
. Since by construction strings are processed
s
and
J
J
increasing in
s
, they are also processed in decreasing order
in decreasing order of
J
J
. Given a new string
r
, ready to be inserted in list
L
(
λ
π
), as we
are scanning
L
(
λ
π
) to identify new candidate pairs with respect to
r
,
we can stop scanning once we encounter the first string
s
s.t.
of
J
<
J
k
.
No subsequent string can have a larger similarity upper bound, since,
by construction, they have been inserted in
L
(
λ
π
) in decreasing order
