3.4. LOCALITY-SENSITIVE HASHING FOR DOCUMENTS
93
1 0 0 0 2
3 2 1 2 2
0 1 3 1 1
. . .
. . .
band 1
band 2
band 3
band 4
Figure 3.7: Dividing a signature matrix into four bands of three rows per band
will deﬁnitely hash to the same bucket in the hashing for the ﬁrst band. Thus,
regardless of what those columns look like in the other three bands, this pair
of columns will be a candidate pair. It is possible that other columns, such as
the ﬁrst two shown explicitly, will also hash to the same bucket according to
the hashing of the ﬁrst band. However, since their column vectors are diﬀerent,
[1, 3, 0] and [0, 2, 1], and there are many buckets for each hashing, we expect the
chances of an accidental collision to be very small. We shall normally assume
that two vectors hash to the same bucket if and only if they are identical.
Two columns that do not agree in band 1 have three other chances to become
a candidate pair; they might be identical in any one of these other bands.
However, observe that the more similar two columns are, the more likely it is
that they will be identical in some band. Thus, intuitively the banding strategy
makes similar columns much more likely to be candidate pairs than dissimilar
pairs.
✷
3.4.2
Analysis of the Banding Technique
Suppose we use b bands of r rows each, and suppose that a particular pair of
documents have Jaccard similarity s. Recall from Section 3.3.3 that the prob-
ability the minhash signatures for these documents agree in any one particular
row of the signature matrix is s. We can calculate the probability that these
documents (or rather their signatures) become a candidate pair as follows:
1. The probability that the signatures agree in all rows of one particular
band is sr.
2. The probability that the signatures disagree in at least one row of a par-
ticular band is 1 −sr.
3. The probability that the signatures disagree in at least one row of each
of the bands is (1 −sr)b.
