3.7. LSH FAMILIES FOR OTHER DISTANCE MEASURES
111
3.7.3
Sketches
Instead of chosing a random vector from all possible vectors, it turns out to be
suﬃciently random if we restrict our choice to vectors whose components are
+1 and −1. The dot product of any vector x with a vector v of +1’s and −1’s
is formed by adding the components of x where v is +1 and then subtracting
the other components of x – those where v is −1.
If we pick a collection of random vectors, say v1, v2, . . . , vn, then we can
apply them to an arbitrary vector x by computing v1.x, v2.x, . . . , vn.x and then
replacing any positive value by +1 and any negative value by −1. The result is
called the sketch of x. You can handle 0’s arbitrarily, e.g., by chosing a result +1
or −1 at random. Since there is only a tiny probability of a zero dot product,
the choice has essentially no eﬀect.
Example 3.22 : Suppose our space consists of 4-dimensional vectors, and we
pick three random vectors: v1 = [+1, −1, +1, +1], v2 = [−1, +1, −1, +1], and
v3 = [+1, +1, −1, −1]. For the vector x = [3, 4, 5, 6], the sketch is [+1, +1, −1].
That is, v1.x = 3−4+5+6 = 10. Since the result is positive, the ﬁrst component
of the sketch is +1. Similarly, v2.x = 2 and v3.x = −4, so the second component
of the sketch is +1 and the third component is −1.
Consider the vector y = [4, 3, 2, 1]. We can similarly compute its sketch to
be [+1, −1, +1]. Since the sketches for x and y agree in 1/3 of the positions,
we estimate that the angle between them is 120 degrees. That is, a randomly
chosen hyperplane is twice as likely to look like the dashed line in Fig. 3.13 than
like the dotted line.
The above conclusion turns out to be quite wrong. We can calculate the
cosine of the angle between x and y to be x.y, which is
6 × 1 + 5 × 2 + 4 × 3 + 3 × 4 = 40
divided by the magnitudes of the two vectors. These magnitudes are
p
62 + 52 + 42 + 32 = 9.274
and
√
12 + 22 + 32 + 42 = 5.477. Thus, the cosine of the angle between x and
y is 0.7875, and this angle is about 38 degrees. However, if you look at all
16 diﬀerent vectors v of length 4 that have +1 and −1 as components, you
ﬁnd that there are only four of these whose dot products with x and y have
a diﬀerent sign, namely v2, v3, and their complements [+1, −1, +1, −1] and
[−1, −1, +1, +1]. Thus, had we picked all sixteen of these vectors to form a
sketch, the estimate of the angle would have been 180/4 = 45 degrees.
✷
3.7.4
LSH Families for Euclidean Distance
Now, let us turn to the Euclidean distance (Section 3.5.2), and see if we can
develop a locality-sensitive family of hash functions for this distance. We shall
start with a 2-dimensional Euclidean space. Each hash function f in our family
