3.7. LSH FAMILIES FOR OTHER DISTANCE MEASURES
113
the same bucket is at most 1/3. We can amplify this family as we like, just as
for the other examples of locality-sensitive hash functions we have discussed.
3.7.5
More LSH Families for Euclidean Spaces
There is something unsatisfying about the family of hash functions developed
in Section 3.7.4. First, the technique was only described for two-dimensional
Euclidean spaces. What happens if our data is points in a space with many
dimensions? Second, for Jaccard and cosine distances, we were able to develop
locality-sensitive families for any pair of distances d1 and d2 as long as d1 < d2.
In Section 3.7.4 we appear to need the stronger condition d1 < 4d2.
However, we claim that there is a locality-sensitive family of hash func-
tions for any d1 < d2 and for any number of dimensions. The family’s hash
functions still derive from random lines through the space and a bucket size
a that partitions the line. We still hash points by projecting them onto the
line. Given that d1 < d2, we may not know what the probability p1 is that two
points at distance d1 hash to the same bucket, but we can be certain that it
is greater than p2, the probability that two points at distance d2 hash to the
same bucket. The reason is that this probability surely grows as the distance
shrinks. Thus, even if we cannot calculate p1 and p2 easily, we know that there
is a (d1, d2, p1, p2)-sensitive family of hash functions for any d1 < d2 and any
given number of dimensions.
Using the ampliﬁcation techniques of Section 3.6.3, we can then adjust the
two probabilities to surround any particular value we like, and to be as far apart
as we like. Of course, the further apart we want the probabilities to be, the
larger the number of basic hash functions in F we must use.
3.7.6
Exercises for Section 3.7
Exercise 3.7.1: Suppose we construct the basic family of six locality-sensitive
functions for vectors of length six. For each pair of the vectors 000000, 110011,
010101, and 011100, which of the six functions makes them candidates?
Exercise 3.7.2: Let us compute sketches using the following four “random”
vectors:
v1 = [+1, +1, +1, −1]
v2 = [+1, +1, −1, +1]
v3 = [+1, −1, +1, +1]
v4 = [−1, +1, +1, +1]
Compute the sketches of the following vectors.
(a) [2, 3, 4, 5].
(b) [−2, 3, −4, 5].
(c) [2, −3, 4, −5].
