3.7. LSH FAMILIES FOR OTHER DISTANCE MEASURES
109
3.7.1
LSH Families for Hamming Distance
It is quite simple to build a locality-sensitive family of functions for the Ham-
ming distance. Suppose we have a space of d-dimensional vectors, and h(x, y)
denotes the Hamming distance between vectors x and y. If we take any one
position of the vectors, say the ith position, we can deﬁne the function fi(x)
to be the ith bit of vector x. Then fi(x) = fi(y) if and only if vectors x and
y agree in the ith position. Then the probability that fi(x) = fi(y) for a ran-
domly chosen i is exactly 1 −h(x, y)/d; i.e., it is the fraction of positions in
which x and y agree.
This situation is almost exactly like the one we encountered for minhashing.
Thus, the family F consisting of the functions {f1, f2, . . . , fd} is a
(d1, d2, 1 −d1/d, 1 −d2/d)-sensitive
family of hash functions, for any d1 < d2.
There are only two diﬀerences
between this family and the family of minhash functions.
1. While Jaccard distance runs from 0 to 1, the Hamming distance on a
vector space of dimension d runs from 0 to d. It is therefore necessary to
scale the distances by dividing by d, to turn them into probabilities.
2. While there is essentially an unlimited supply of minhash functions, the
size of the family F for Hamming distance is only d.
The ﬁrst point is of no consequence; it only requires that we divide by d at
appropriate times. The second point is more serious. If d is relatively small,
then we are limited in the number of functions that can be composed using
the AND and OR constructions, thereby limiting how steep we can make the
S-curve be.
3.7.2
Random Hyperplanes and the Cosine Distance
Recall from Section 3.5.4 that the cosine distance between two vectors is the
angle between the vectors.
For instance, we see in Fig. 3.13 two vectors x
and y that make an angle θ between them. Note that these vectors may be
in a space of many dimensions, but they always deﬁne a plane, and the angle
between them is measured in this plane. Figure 3.13 is a “top-view” of the
plane containing x and y.
Suppose we pick a hyperplane through the origin. This hyperplane intersects
the plane of x and y in a line. Figure 3.13 suggests two possible hyperplanes,
one whose intersection is the dashed line and the other’s intersection is the
dotted line. To pick a random hyperplane, we actually pick the normal vector
to the hyperplane, say v. The hyperplane is then the set of points whose dot
product with v is 0.
First, consider a vector v that is normal to the hyperplane whose projection
is represented by the dashed line in Fig. 3.13; that is, x and y are on diﬀerent
