126
CHAPTER 3. FINDING SIMILAR ITEMS
end, their intersection is 9 symbols and their union is 11; thus SIM(s, t) = 9/11,
which is less than 0.9.
If we build our index based not only on the symbol, but on the position of
the symbol within the string, we could avoid comparing s and t above. That
is, let our index have a bucket for each pair (x, i), containing the strings that
have symbol x in position i of their preﬁx. Given a string s, and assuming J is
the minimum desired Jaccard similarity, we look at the preﬁx of s, that is, the
positions 1 through ⌊(1 −J)Ls⌋+ 1. If the symbol in position i of the preﬁx is
x, add s to the index bucket for (x, i).
Now consider s as a probe string. With what buckets must it be compared?
We shall visit the symbols of the preﬁx of s from the left, and we shall take
advantage of the fact that we only need to ﬁnd a possible matching string t if
none of the previous buckets we have examined for matches held t. That is, we
only need to ﬁnd a candidate match once. Thus, if we ﬁnd that the ith symbol
of s is x, then we need look in the bucket (x, j) for certain small values of j.
j
s
t
Symbols definitely
appearing in
only one string
i
Figure 3.15: Strings s and t begin with i −1 and j −1 unique symbols, respec-
tively, and then agree beyond that
To compute the upper bound on j, suppose t is a string none of whose ﬁrst
j −1 symbols matched anything in s, but the ith symbol of s is the same as the
jth symbol of t. The highest value of SIM(s, t) occurs if s and t are identical
beyond their ith and jth symbols, respectively, as suggested by Fig. 3.15. If
that is the case, the size of their intersection is Ls −i + 1, since that is the
number of symbols of s that could possibly be in t. The size of their union is
at least Ls + j −1. That is, s surely contributes Ls symbols to the union, and
there are also at least j −1 symbols of t that are not in s. The ratio of the sizes
of the intersection and union must be at least J, so we must have:
Ls −i + 1
Ls + j −1 ≥J
If we isolate j in this inequality, we have j ≤
Ls(1 −J) −i + 1 + J

/J.
Example 3.28 : Consider the string s = acdefghijk with J = 0.9 discussed
at the beginning of this section. Suppose s is now a probe string. We already
established that we need to consider the ﬁrst two positions; that is, i can be 1
