94
CHAPTER 3. FINDING SIMILAR ITEMS
4. The probability that the signatures agree in all the rows of at least one
band, and therefore become a candidate pair, is 1 −(1 −sr)b.
0
1
 of documents
Jaccard similarity
Probability
of becoming
a candidate
Figure 3.8: The S-curve
It may not be obvious, but regardless of the chosen constants b and r, this
function has the form of an S-curve, as suggested in Fig. 3.8. The threshold,
that is, the value of similarity s at which the probability of becoming a candi-
date is 1/2, is a function of b and r. The threshold is roughly where the rise is
the steepest, and for large b and r we ﬁnd that pairs with similarity above the
threshold are very likely to become candidates, while those below the threshold
are unlikely to become candidates – exactly the situation we want. An approx-
imation to the threshold is (1/b)1/r. For example, if b = 16 and r = 4, then the
threshold is approximately at s = 1/2, since the 4th root of 1/16 is 1/2.
Example 3.12 : Let us consider the case b = 20 and r = 5. That is, we suppose
we have signatures of length 100, divided into twenty bands of ﬁve rows each.
Figure 3.9 tabulates some of the values of the function 1 −(1 −s5)20. Notice
that the threshold, the value of s at which the curve has risen halfway, is just
slightly more than 0.5. Also notice that the curve is not exactly the ideal step
function that jumps from 0 to 1 at the threshold, but the slope of the curve
in the middle is signiﬁcant. For example, it rises by more than 0.6 going from
s = 0.4 to s = 0.6, so the slope in the middle is greater than 3.
For example, at s = 0.8, 1 −(0.8)5 is about 0.672. If you raise this number
to the 20th power, you get about 0.00035. Subtracting this fraction from 1
yields 0.99965. That is, if we consider two documents with 80% similarity, then
in any one band, they have only about a 33% chance of agreeing in all ﬁve rows
and thus becoming a candidate pair. However, there are 20 bands and thus 20
