84
CHAPTER 3. FINDING SIMILAR ITEMS
as a column. Thus, we can form from matrix M a signature matrix, in which
the ith column of M is replaced by the minhash signature for (the set of) the
ith column.
Note that the signature matrix has the same number of columns as M but
only n rows. Even if M is not represented explicitly, but in some compressed
form suitable for a sparse matrix (e.g., by the locations of its 1’s), it is normal
for the signature matrix to be much smaller than M.
The remarkable thing about signature matrices is that we can use their
columns to estimate the Jaccard similarity of the sets that correspond to the
columns of signature matrix. By the theorem proved in Section 3.3.3, we know
that the probability that two columns have the same value in a given row of
the signature matrix equals the Jaccard similarity of the sets corresponding to
those columns. Moreover, since the permutations on which the minhash values
are based were chosen independently, we can think of each row of the signature
matrix as an independent experiment. Thus, the expected number of rows in
which two columns agree equals the Jaccard similarity of their corresponding
sets. Moreover, the more minhashings we use, i.e., the more rows in the sig-
nature matrix, the smaller the expected error in the estimate of the Jaccard
similarity will be.
3.3.5
Computing Minhash Signatures in Practice
It is not feasible to permute a large characteristic matrix explicitly. Even picking
a random permutation of millions or billions of rows is time-consuming, and
the necessary sorting of the rows would take even more time. Thus, permuted
matrices like that suggested by Fig. 3.3, while conceptually appealing, are not
implementable.
Fortunately, it is possible to simulate the eﬀect of a random permutation by
a random hash function that maps row numbers to as many buckets as there
are rows. A hash function that maps integers 0, 1, . . ., k −1 to bucket numbers
0 through k−1 typically will map some pairs of integers to the same bucket and
leave other buckets unﬁlled. However, the diﬀerence is unimportant as long as
k is large and there are not too many collisions. We can maintain the ﬁction
that our hash function h “permutes” row r to position h(r) in the permuted
order.
Thus, instead of picking n random permutations of rows, we pick n randomly
chosen hash functions h1, h2, . . . , hn on the rows. We construct the signature
matrix by considering each row in their given order. Let SIG(i, c) be the element
of the signature matrix for the ith hash function and column c. Initially, set
SIG(i, c) to ∞for all i and c. We handle row r by doing the following:
1. Compute h1(r), h2(r), . . . , hn(r).
2. For each column c do the following:
(a) If c has 0 in row r, do nothing.
