76
CHAPTER 3. FINDING SIMILAR ITEMS
Articles from the Same Source
It is common for one reporter to write a news article that gets distributed,
say through the Associated Press, to many newspapers, which then publish
the article on their Web sites. Each newspaper changes the article somewhat.
They may cut out paragraphs, or even add material of their own. They most
likely will surround the article by their own logo, ads, and links to other articles
at their site. However, the core of each newspaper’s page will be the original
article. News aggregators, such as Google News, try to ﬁnd all versions of such
an article, in order to show only one, and that task requires ﬁnding when two
Web pages are textually similar, although not identical.1
3.1.3
Collaborative Filtering as a Similar-Sets Problem
Another class of applications where similarity of sets is very important is called
collaborative ﬁltering, a process whereby we recommend to users items that were
liked by other users who have exhibited similar tastes. We shall investigate
collaborative ﬁltering in detail in Section 9.3, but for the moment let us see
some common examples.
On-Line Purchases
Amazon.com has millions of customers and sells millions of items. Its database
records which items have been bought by which customers. We can say two cus-
tomers are similar if their sets of purchased items have a high Jaccard similarity.
Likewise, two items that have sets of purchasers with high Jaccard similarity
will be deemed similar. Note that, while we might expect mirror sites to have
Jaccard similarity above 90%, it is unlikely that any two customers have Jac-
card similarity that high (unless they have purchased only one item). Even a
Jaccard similarity like 20% might be unusual enough to identify customers with
similar tastes. The same observation holds for items; Jaccard similarities need
not be very high to be signiﬁcant.
Collaborative ﬁltering requires several tools, in addition to ﬁnding similar
customers or items, as we discuss in Chapter 9. For example, two Amazon
customers who like science-ﬁction might each buy many science-ﬁction books,
but only a few of these will be in common. However, by combining similarity-
ﬁnding with clustering (Chapter 7), we might be able to discover that science-
ﬁction books are mutually similar and put them in one group. Then, we can
get a more powerful notion of customer-similarity by asking whether they made
purchases within many of the same groups.
1News aggregation also involves ﬁnding articles that are about the same topic, even though
not textually similar.
This problem too can yield to a similarity search, but it requires
techniques other than Jaccard similarity of sets.
