108
CHAPTER 3. FINDING SIMILAR ITEMS
family. This choice is not necessarily the best. Although the higher probability
has moved much closer to 1, the lower probability has also raised, increasing
the number of false positives.
✷
Example 3.21 : We can cascade constructions as much as we like. For exam-
ple, we could use the construction of Example 3.19 on the family of minhash
functions and then use the construction of Example 3.20 on the resulting family.
The constructed family would then have functions each built from 256 minhash
functions. It would, for instance transform a (0.2, 0.8, 0.8, 0.2)-sensitive family
into a (0.2, 0.8, 0.9991285, 0.0000004)-sensitive family.
✷
3.6.4
Exercises for Section 3.6
Exercise 3.6.1: What is the eﬀect on probability of starting with the family
of minhash functions and applying:
(a) A 2-way AND construction followed by a 3-way OR construction.
(b) A 3-way OR construction followed by a 2-way AND construction.
(c) A 2-way AND construction followed by a 2-way OR construction, followed
by a 2-way AND construction.
(d) A 2-way OR construction followed by a 2-way AND construction, followed
by a 2-way OR construction followed by a 2-way AND construction.
Exercise 3.6.2: Find the ﬁxedpoints for each of the functions constructed in
Exercise 3.6.1.
! Exercise 3.6.3: Any function of probability p, such as that of Fig. 3.11, has
a slope given by the derivative of the function. The maximum slope is where
that derivative is a maximum. Find the value of p that gives a maximum slope
for the S-curves given by Fig. 3.11 and Fig. 3.12. What are the values of these
maximum slopes?
!! Exercise 3.6.4: Generalize Exercise 3.6.3 to give, as a function of r and b, the
point of maximum slope and the value of that slope, for families of functions
deﬁned from the minhash functions by:
(a) An r-way AND construction followed by a b-way OR construction.
(b) A b-way OR construction followed by an r-way AND construction.
3.7
LSH Families for Other Distance Measures
There is no guarantee that a distance measure has a locality-sensitive family of
hash functions. So far, we have only seen such families for the Jaccard distance.
In this section, we shall show how to construct locality-sensitive families for
Hamming distance, the cosine distance and for the normal Euclidean distance.
