3.9. METHODS FOR HIGH DEGREES OF SIMILARITY
123
a problem where there is a common preﬁx for all or most documents, yet we
need not examine entire documents unless they fall into a bucket with another
document. One problem with selecting ﬁxed positions is that if some documents
are short, they may not have some of the selected positions. However, if we are
looking for highly similar documents, we never need to compare two documents
that diﬀer signiﬁcantly in their length. We exploit this idea in Section 3.9.3.
3.9.2
Representing Sets as Strings
Now, let us focus on the harder problem of ﬁnding, in a large collection of sets,
all pairs that have a high Jaccard similarity, say at least 0.9. We can represent
a set by sorting the elements of the universal set in some ﬁxed order, and
representing any set by listing its elements in this order. The list is essentially
a string of “characters,” where the characters are the elements of the universal
set. These strings are unusual, however, in that:
1. No character appears more than once in a string, and
2. If two characters appear in two diﬀerent strings, then they appear in the
same order in both strings.
Example 3.25 : Suppose the universal set consists of the 26 lower-case letters,
and we use the normal alphabetical order. Then the set {d, a, b} is represented
by the string abd.
✷
In what follows, we shall assume all strings represent sets in the manner just
described. Thus, we shall talk about the Jaccard similarity of strings, when
strictly speaking we mean the similarity of the sets that the strings represent.
Also, we shall talk of the length of a string, as a surrogate for the number of
elements in the set that the string represents.
Note that the documents discussed in Section 3.9.1 do not exactly match
this model, even though we can see documents as strings. To ﬁt the model,
we would shingle the documents, assign an order to the shingles, and represent
each document by its list of shingles in the selected order.
3.9.3
Length-Based Filtering
The simplest way to exploit the string representation of Section 3.9.2 is to sort
the strings by length. Then, each string s is compared with those strings t that
follow s in the list, but are not too long. Suppose the lower bound on Jaccard
similarity between two strings is J. For any string x, denote its length by Lx.
Note that Ls ≤Lt. The intersection of the sets represented by s and t cannot
have more than Ls members, while their union has at least Lt members. Thus,
the Jaccard similarity of s and t, which we denote SIM(s, t), is at most Ls/Lt.
That is, in order for s and t to require comparison, it must be that J ≤Ls/Lt,
or equivalently, Lt ≤Ls/J.
