86
CHAPTER 3. FINDING SIMILAR ITEMS
The row of Fig. 3.4 numbered 2 has 1’s in the columns for S2 and S4, and
its hash values are h1(2) = 3 and h2(2) = 2. We could change the values in the
signature for S4, but the values in this column of the signature matrix, [1, 1], are
each less than the corresponding hash values [3, 2]. However, since the column
for S2 still has ∞’s, we replace it by [3, 2], resulting in:
S1
S2
S3
S4
h1
1
3
2
1
h2
1
2
4
1
Next comes the row numbered 3 in Fig. 3.4. Here, all columns but S2 have
1, and the hash values are h1(3) = 4 and h2(3) = 0. The value 4 for h1 exceeds
what is already in the signature matrix for all the columns, so we shall not
change any values in the ﬁrst row of the signature matrix. However, the value
0 for h2 is less than what is already present, so we lower SIG(2, 1), SIG(2, 3) and
SIG(2, 4) to 0. Note that we cannot lower SIG(2, 2) because the column for S2 in
Fig. 3.4 has 0 in the row we are currently considering. The resulting signature
matrix:
S1
S2
S3
S4
h1
1
3
2
1
h2
0
2
0
0
Finally, consider the row of Fig. 3.4 numbered 4. h1(4) = 0 and h2(4) = 3.
Since row 4 has 1 only in the column for S3, we only compare the current
signature column for that set, [2, 0] with the hash values [0, 3]. Since 0 < 2, we
change SIG(1, 3) to 0, but since 3 > 0 we do not change SIG(2, 3). The ﬁnal
signature matrix is:
S1
S2
S3
S4
h1
1
3
0
1
h2
0
2
0
0
We can estimate the Jaccard similarities of the underlying sets from this
signature matrix. Notice that columns 1 and 4 are identical, so we guess that
SIM(S1, S4) = 1.0. If we look at Fig. 3.4, we see that the true Jaccard similarity
of S1 and S4 is 2/3. Remember that the fraction of rows that agree in the
signature matrix is only an estimate of the true Jaccard similarity, and this
example is much too small for the law of large numbers to assure that the
estimates are close. For additional examples, the signature columns for S1 and
S3 agree in half the rows (true similarity 1/4), while the signatures of S1 and
S2 estimate 0 as their Jaccard similarity (the correct value).
✷
3.3.6
Speeding Up Minhashing
The process of minhashing is time-consuming, since we need to examine the
entire k-row matrix M for each minhash function we want. Let us ﬁrst return
