88
CHAPTER 3. FINDING SIMILAR ITEMS
sense in the context of Section 3.3.6 than it did in Section 3.3.2. The reason
is that we do not need to construct a full permutation of k elements, but only
pick a small number m out of the k rows and then pick a random permutation
of those rows. Depending on the value of m and how the matrix M is stored, it
might make sense to follow the algorithm suggested by Section 3.3.6 literally.
However, it is more likely that a strategy akin to Section 3.3.5 is needed.
Now, the rows of M are ﬁxed, and not permuted. We choose a hash function
that hashes row numbers, and compute hash values for only the ﬁrst m rows.
That is, we follow the algorithm of Section 3.3.5, but only until we reach the
mth row, whereupon we stop and, and for each columns, we take the minimum
hash value seen so far as the minhash value for that column.
Since some column may have 0 in all m rows, it is possible that some of the
minhash values will be ∞. Assuming m is suﬃciently large that ∞minhash
values are rare, we still get a good estimate of the Jaccard similarity of sets by
comparing columns of the signature matrix. Suppose T is the set of elements
of the universal set that are represented by the ﬁrst m rows of matrix M. Let
S1 and S2 be the sets represented by two columns of M. Then the ﬁrst m rows
of M represent the sets S1 ∩T and S2 ∩T . If both these sets are empty (i.e.,
both columns are all-0 in their ﬁrst m rows), then this minhash function will be
∞in both columns and will be ignored when estimating the Jaccard similarity
of the columns’ underlying sets.
If at least one of the sets S1 ∩T and S2 ∩T is nonempty, then the proba-
bility of the two columns having equal values for this minhash function is the
Jaccard similarity of these two sets, that is
|S1 ∩S2 ∩T |
|(S1 ∪S2) ∩T |
As long as T is chosen to be a random subset of the universal set, the expected
value of this fraction will be the same as the Jaccard similarity of S1 and S2.
However, there will be some random variation, since depending on T , we could
ﬁnd more or less than an average number of type X rows (1’s in both columns)
and/or type Y rows (1 in one column and 0 in the other) among the ﬁrst m
rows of matrix M.
To mitigate this variation, we do not use the same set T for each minhashing
that we do. Rather, we divide the rows of M into k/m groups.4 Then for each
hash function, we compute one minhash value by examining only the ﬁrst m
rows of M, a diﬀerent minhash value by examining only the second m rows,
and so on. We thus get k/m minhash values from a single hash function and
a single pass over all the rows of M. In fact, if k/m is large enough, we may
get all the rows of the signature matrix that we need by a single hash function
applied to each of the subsets of rows of M.
4In what follows, we assume m divides k evenly, for convenience. It is unimportant, as
long as k/m is large, if some rows are not included in any group because k is not an integer
multiple of m.
