92
CHAPTER 3. FINDING SIMILAR ITEMS
reason is that the number of pairs of documents may be too large, even if there
are not too many documents.
Example 3.10 : Suppose we have a million documents, and we use signatures
of length 250. Then we use 1000 bytes per document for the signatures, and
the entire data ﬁts in a gigabyte – less than a typical main memory of a laptop.
However, there are
1,000,000
2

or half a trillion pairs of documents. If it takes a
microsecond to compute the similarity of two signatures, then it takes almost
six days to compute all the similarities on that laptop.
✷
If our goal is to compute the similarity of every pair, there is nothing we
can do to reduce the work, although parallelism can reduce the elapsed time.
However, often we want only the most similar pairs or all pairs that are above
some lower bound in similarity. If so, then we need to focus our attention only
on pairs that are likely to be similar, without investigating every pair. There is
a general theory of how to provide such focus, called locality-sensitive hashing
(LSH) or near-neighbor search.
In this section we shall consider a speciﬁc form
of LSH, designed for the particular problem we have been studying: documents,
represented by shingle-sets, then minhashed to short signatures. In Section 3.6
we present the general theory of locality-sensitive hashing and a number of
applications and related techniques.
3.4.1
LSH for Minhash Signatures
One general approach to LSH is to “hash” items several times, in such a way that
similar items are more likely to be hashed to the same bucket than dissimilar
items are. We then consider any pair that hashed to the same bucket for any
of the hashings to be a candidate pair. We check only the candidate pairs for
similarity. The hope is that most of the dissimilar pairs will never hash to the
same bucket, and therefore will never be checked. Those dissimilar pairs that
do hash to the same bucket are false positives; we hope these will be only a
small fraction of all pairs. We also hope that most of the truly similar pairs
will hash to the same bucket under at least one of the hash functions. Those
that do not are false negatives; we hope these will be only a small fraction of
the truly similar pairs.
If we have minhash signatures for the items, an eﬀective way to choose the
hashings is to divide the signature matrix into b bands consisting
of r rows
each. For each band, there is a hash function that takes vectors of r integers
(the portion of one column within that band) and hashes them to some large
number of buckets. We can use the same hash function for all the bands, but
we use a separate bucket array for each band, so columns with the same vector
in diﬀerent bands will not hash to the same bucket.
Example 3.11 : Figure 3.7 shows part of a signature matrix of 12 rows divided
into four bands of three rows each. The second and fourth of the explicitly
shown columns each have the column vector [0, 2, 1] in the ﬁrst band, so they
