Chapter 3
Finding Similar Items
A fundamental data-mining problem is to examine data for “similar” items. We
shall take up applications in Section 3.1, but an example would be looking at a
collection of Web pages and ﬁnding near-duplicate pages. These pages could be
plagiarisms, for example, or they could be mirrors that have almost the same
content but diﬀer in information about the host and about other mirrors.
The naive approach to ﬁnding pairs of similar items requires us to look at ev-
ery pair of items. When we are dealing with a large dataset, looking at all pairs
of items may be prohibitive, even given an abundance of hardware resources.
For example, even a million items gives us half a trillion pairs to examine, and
a million items is considered a “small” dataset by today’s standards.
It is therefore a pleasant surprise to learn of a family of techniques called
locality-sensitive hashing, or LSH, that allows us to focus on pairs that are likely
to be similar, without having to look at all pairs. Thus, it is possible that we
can avoid the quadratic growth in computation time that is required by the
naive algorithm. There is usually a downside to locality-sensitive hashing, due
to the presence of false negatives, that is, pairs of items that are similar, yet
are not included in the set of pairs that we examine, but by careful tuning we
can reduce the fraction of false negatives by increasing the number of pairs we
consider.
The general idea behind LSH is that we hash items using many diﬀerent
hash functions.
These hash functions are not the conventional sort of hash
functions. Rather, they are carefully designed to have the property that pairs
are much more likely to wind up in the same bucket of a hash function if the
items are similar than if they are not similar. We then can examine only the
candidate pairs, which are pairs of items that wind up in the same bucket for
at least one of the hash functions.
We begin our discussion of LSH with an examination of the problem of ﬁnd-
ing similar documents – those that share a lot of common text. We ﬁrst show
how to convert documents into sets (Section 3.2) in a way that lets us view
textual similarity of documents as sets having a large overlap. More precisely,
73
