124
CHAPTER 3. FINDING SIMILAR ITEMS
A Better Ordering for Symbols
Instead of using the obvious order for elements of the universal set, e.g.,
lexicographic order for shingles, we can order symbols rarest ﬁrst. That
is, determine how many times each element appears in the collection of
sets, and order them by this count, lowest ﬁrst. The advantage of doing
so is that the symbols in preﬁxes will tend to be rare. Thus, they will
cause that string to be placed in index buckets that have relatively few
members. Then, when we need to examine a string for possible matches,
we shall ﬁnd few other strings that are candidates for comparison.
Example 3.26 : Suppose that s is a string of length 9, and we are looking for
strings with at least 0.9 Jaccard similarity. Then we have only to compare s
with strings following it in the length-based sorted order that have length at
most 9/0.9 = 10. That is, we compare s with those strings of length 9 that
follow it in order, and all strings of length 10. We have no need to compare s
with any other string.
Suppose the length of s were 8 instead. Then s would be compared with
following strings of length up to 8/0.9 = 8.89. That is, a string of length 9
would be too long to have a Jaccard similarity of 0.9 with s, so we only have to
compare s with the strings that have length 8 but follow it in the sorted order.
✷
3.9.4
Preﬁx Indexing
In addition to length, there are several other features of strings that can be
exploited to limit the number of comparisons that must be made to identify
all pairs of similar strings. The simplest of these options is to create an index
for each symbol; recall a symbol of a string is any one of the elements of the
universal set. For each string s, we select a preﬁx of s consisting of the ﬁrst p
symbols of s. How large p must be depends on Ls and J, the lower bound on
Jaccard similarity. We add string s to the index for each of its ﬁrst p symbols.
In eﬀect, the index for each symbol becomes a bucket of strings that must be
compared. We must be certain that any other string t such that SIM(s, t) ≥J
will have at least one symbol in its preﬁx that also appears in the preﬁx of s.
Suppose not; rather SIM(s, t) ≥J, but t has none of the ﬁrst p symbols of
s. Then the highest Jaccard similarity that s and t can have occurs when t is
a suﬃx of s, consisting of everything but the ﬁrst p symbols of s. The Jaccard
similarity of s and t would then be (Ls −p)/Ls. To be sure that we do not
have to compare s with t, we must be certain that J > (Ls −p)/Ls. That
is, p must be at least ⌊(1 −J)Ls⌋+ 1. Of course we want p to be as small as
possible, so we do not index string s in more buckets than we need to. Thus,
we shall hereafter take p = ⌊(1 −J)Ls⌋+ 1 to be the length of the preﬁx that
