3.6. THE THEORY OF LOCALITY-SENSITIVE FUNCTIONS
105
Probabilty
of being
declared a
candidate
d
p
d
p
1
2
1
2
Distance
Figure 3.10: Behavior of a (d1, d2, p1, p2)-sensitive function
measure is the Jaccard distance. As before, we interpret a minhash function h
to make x and y a candidate pair if and only if h(x) = h(y).
• The family of minhash functions is a (d1, d2, 1−d1, 1−d2)-sensitive family
for any d1 and d2, where 0 ≤d1 < d2 ≤1.
The reason is that if d(x, y) ≤d1, where d is the Jaccard distance, then
SIM(x, y) = 1 −d(x, y) ≥1 −d1. But we know that the Jaccard similarity
of x and y is equal to the probability that a minhash function will hash x and
y to the same value. A similar argument applies to d2 or any distance.
Example 3.18 : We could let d1 = 0.3 and d2 = 0.6. Then we can assert that
the family of minhash functions is a (0.3, 0.6, 0.7, 0.4)-sensitive family. That is,
if the Jaccard distance between x and y is at most 0.3 (i.e., SIM(x, y) ≥0.7)
then there is at least a 0.7 chance that a minhash function will send x and y to
the same value, and if the Jaccard distance between x and y is at least 0.6 (i.e.,
SIM(x, y) ≤0.4), then there is at most a 0.4 chance that x and y will be sent
to the same value. Note that we could make the same assertion with another
choice of d1 and d2; only d1 < d2 is required.
✷
3.6.3
Amplifying a Locality-Sensitive Family
Suppose we are given a (d1, d2, p1, p2)-sensitive family F. We can construct a
new family F′ by the AND-construction on F, which is deﬁned as follows. Each
member of F′ consists of r members of F for some ﬁxed r. If f is in F′, and f is
constructed from the set {f1, f2, . . . , fr} of members of F, we say f(x) = f(y)
if and only if fi(x) = fi(y) for all i = 1, 2, . . . , r. Notice that this construction
mirrors the eﬀect of the r rows in a single band: the band makes x and y a
