3.3. SIMILARITY-PRESERVING SUMMARIES OF SETS
89
Moreover, by using each of the rows of M to compute one of these minhash
values, we tend to balance out the errors in estimation of the Jaccard similarity
due to any one particular subset of the rows. That is, the Jaccard similarity
of S1 and S2 determines the ratio of type X and type Y rows. All the type X
rows are distributed among the k/m sets of rows, and likewise the type Y rows.
Thus, while one set of m rows may have more of one type of row than average,
there must then be some other set of m rows with fewer than average of that
same type.
Example 3.9 : In Fig. 3.5 we see a matrix representing three sets S1, S2, and
S3, with a universal set of eight elements; i.e., k = 8. Let us pick m = 4, so one
pass through the rows yields two minhash values, one based on the ﬁrst four
rows and the other on the second four rows.
S1
S2
S3
0
0
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
0
1
0
0
0
0
0
Figure 3.5: A Boolean matrix representing three sets
First, note that the Jaccard similarities of the three sets are SIM(S1, S2) =
1/2, SIM(S1, S3) = 1/5, and SIM(S2, S3) = 1/2. Now, look at the ﬁrst four
rows only. Whatever hash function we use, the minhash value for S1 will be
∞, the minhash value for S2 will be the hash value of the 4th row, and the
minhash value for S3 will be the smaller of the hash values for the third and
fourth rows. Thus, the minhash values for S1 and S2 will never agree. That
makes sense, since if T is the set of elements represented by the ﬁrst four rows,
then S1 ∩T = ∅, and therefore SIM(S1 ∩T, S2 ∩T ) = 0. However, in the
second four rows, the Jaccard similarity of S1 and S2 restricted to the elements
represented by the last four rows is 2/3.
We conclude that if we generate signatures consisting of two minhash values
using this hash function, one based on the ﬁrst four rows and the second based
on the last four rows, the expected number of matches we get between the
signatures for S1 and S2 is the average of 0 and 2/3, or 1/3. Since the actual
Jaccard similarity of S1 and S2 is 1/2, there is an error, but not too great an
error. In larger examples, where minhash values are based on far more than
four rows, the expected error will approach zero.
Similarly, we can see the eﬀect of splitting the rows on the other two pairs
of columns. Between S1 and S3, the top half represents sets with a Jaccard
