3.3. SIMILARITY-PRESERVING SUMMARIES OF SETS
87
to the model of Section 3.3.2, where we imagine rows are actually permuted.
But to compute one minhash function on all the columns, we shall not go all
the way to the end of the permutation, but only look at the ﬁrst m out of k
rows. If we make m small compared with k, we reduce the work by a large
factor, k/m.
However, there is a downside to making m small. As long as each column
has at least one 1 in the ﬁrst m rows in permuted order, the rows after the mth
have no eﬀect on any minhash value and may as well not be looked at. But
what if some columns are all-0’s in the ﬁrst m rows? We have no minhash value
for those columns, and will instead have to use a special symbol, for which we
shall use ∞.
When we examine the minhash signatures of two columns in order to esti-
mate the Jaccard similarity of their underlying sets, as in Section 3.3.4, we have
to take into account the possibility that one or both columns have ∞as their
minhash value for some components of the signature. There are three cases:
1. If neither column has ∞in a given row, then there is no change needed.
Count this row as an example of equal values if the two values are the
same, and as an example of unequal values if not.
2. One column has ∞and the other does not. In this case, had we used
all the rows of the original permuted matrix M, the column that has the
∞would eventually have been given some row number, and that number
will surely not be one of the ﬁrst m rows in the permuted order. But the
other column does have a value that is one of the ﬁrst m rows. Thus, we
surely have an example of unequal minhash values, and we count this row
of the signature matrix as such an example.
3. Now, suppose both columns have ∞in row. Then in the original permuted
matrix M, the ﬁrst m rows of both columns were all 0’s. We thus have no
information about the Jaccard similarity of the corresponding sets; that
similarity is only a function of the last k −m rows, which we have chosen
not to look at. We therefore count this row of the signature matrix as
neither an example of equal values nor of unequal values.
As long as the third case, where both columns have ∞, is rare, we get
almost as many examples to average as there are rows in the signature matrix.
That eﬀect will reduce the accuracy of our estimates of the Jaccard distance
somewhat, but not much.
And since we are now able to compute minhash
values for all the columns much faster than if we examined all the rows of M,
we can aﬀord the time to apply a few more minhash functions. We get even
better accuracy than originally, and we do so faster than before.
3.3.7
Speedup Using Hash Functions
As before, there are reasons not to physically permute rows in the manner
assumed in Section 3.3.6. However, the idea of true permutations makes more
