74
CHAPTER 3. FINDING SIMILAR ITEMS
we measure the similarity of sets by their Jaccard similarity, the ratio of the
sizes of their intersection and union. A second key trick we need is minhashing
(Section 3.3), which is a way to convert large sets into much smaller represen-
tations, called signatures, that still enable us to estimate closely the Jaccard
similarity of the represented sets. Finally, in Section 3.4 we see how to apply
the bucketing idea inherent in LSH to the signatures.
In Section 3.5 we begin our study of how to apply LSH to items other than
sets. We consider the general notion of a distance measure that tells to what
degree items are similar. Then, in Section 3.6 we consider the general idea of
locality-sensitive hashing, and in Section 3.7 we see how to do LSH for some data
types other than sets. Then, Section 3.8 examines in detail several applications
of the LSH idea. Finally, we consider in Section 3.9 some techniques for ﬁnding
similar sets that can be more eﬃcient than LSH when the degree of similarity
we want is very high.
3.1
Applications of Set Similarity
We shall focus initially on a particular notion of “similarity”: the similarity of
sets by looking at the relative size of their intersection. This notion of similarity
is called Jaccard similarity, which is introduced in Section 3.1.1.
We then
examine some of the uses of ﬁnding similar sets. These include ﬁnding textually
similar documents and collaborative ﬁltering by ﬁnding similar customers and
similar products. In order to turn the problem of textual similarity of documents
into one of set intersection, we use the technique called shingling, which is the
subject of Section 3.2.
3.1.1
Jaccard Similarity of Sets
The Jaccard similarity of sets S and T is |S ∩T |/|S ∪T |, that is, the ratio
of the size of the intersection of S and T to the size of their union. We shall
denote the Jaccard similarity of S and T by SIM(S, T ).
Example 3.1 : In Fig. 3.1 we see two sets S and T . There are three elements
in their intersection and a total of eight elements that appear in S or T or both.
Thus, SIM(S, T ) = 3/8.
✷
3.1.2
Similarity of Documents
An important class of problems that Jaccard similarity addresses well is that
of ﬁnding textually similar documents in a large corpus such as the Web or a
collection of news articles. We should understand that the aspect of similarity
we are looking at here is character-level similarity, not “similar meaning,” which
requires us to examine the words in the documents and their uses. That problem
is also interesting but is addressed by other techniques, which we hinted at in
