3.9. METHODS FOR HIGH DEGREES OF SIMILARITY
125
gets indexed.
Example 3.27 : Suppose J = 0.9.
If Ls = 9, then p = ⌊0.1 × 9⌋+ 1 =
⌊0.9⌋+ 1 = 1. That is, we need to index s under only its ﬁrst symbol. Any
string t that does not have the ﬁrst symbol of s in a position such that t is
indexed by that symbol will have Jaccard similarity with s that is less than 0.9.
Suppose s is bcdefghij. Then s is indexed under b only. Suppose t does not
begin with b. There are two cases to consider.
1. If t begins with a, and SIM(s, t) ≥0.9, then it can only be that t is
abcdefghij. But if that is the case, t will be indexed under both a and
b. The reason is that Lt = 10, so t will be indexed under the symbols of
its preﬁx of length ⌊0.1 × 10⌋+ 1 = 2.
2. If t begins with c or a later letter, then the maximum value of SIM(s, t)
occurs when t is cdefghij. But then SIM(s, t) = 8/9 < 0.9.
In general, with J = 0.9, strings of length up to 9 are indexed by their ﬁrst
symbol, strings of lengths 10–19 are indexed under their ﬁrst two symbols,
strings of length 20–29 are indexed under their ﬁrst three symbols, and so on.
✷
We can use the indexing scheme in two ways, depending on whether we
are trying to solve the many-many problem or a many-one problem; recall the
distinction was introduced in Section 3.8.4.
For the many-one problem, we
create the index for the entire database. To query for matches to a new set
S, we convert that set to a string s, which we call the probe string. Determine
the length of the preﬁx that must be considered, that is, ⌊(1 −J)Ls⌋+ 1. For
each symbol appearing in one of the preﬁx positions of s, we look in the index
bucket for that symbol, and we compare s with all the strings appearing in that
bucket.
If we want to solve the many-many problem, start with an empty database
of strings and indexes. For each set S, we treat S as a new set for the many-one
problem. We convert S to a string s, which we treat as a probe string in the
many-one problem. However, after we examine an index bucket, we also add s
to that bucket, so s will be compared with later strings that could be matches.
3.9.5
Using Position Information
Consider the strings s = acdefghijk and t = bcdefghijk, and assume J = 0.9.
Since both strings are of length 10, they are indexed under their ﬁrst two
symbols. Thus, s is indexed under a and c, while t is indexed under b and c.
Whichever is added last will ﬁnd the other in the bucket for c, and they will be
compared. However, since c is the second symbol of both, we know there will
be two symbols, a and b in this case, that are in the union of the two sets but
not in the intersection. Indeed, even though s and t are identical from c to the
