110
CHAPTER 3. FINDING SIMILAR ITEMS
θ
x
y
Figure 3.13: Two vectors make an angle θ
sides of the hyperplane. Then the dot products v.x and v.y will have diﬀerent
signs. If we assume, for instance, that v is a vector whose projection onto the
plane of x and y is above the dashed line in Fig. 3.13, then v.x is positive,
while v.y is negative. The normal vector v instead might extend in the opposite
direction, below the dashed line. In that case v.x is negative and v.y is positive,
but the signs are still diﬀerent.
On the other hand, the randomly chosen vector v could be normal to a
hyperplane like the dotted line in Fig. 3.13. In that case, both v.x and v.y
have the same sign. If the projection of v extends to the right, then both dot
products are positive, while if v extends to the left, then both are negative.
What is the probability that the randomly chosen vector is normal to a
hyperplane that looks like the dashed line rather than the dotted line?
All
angles for the line that is the intersection of the random hyperplane and the
plane of x and y are equally likely. Thus, the hyperplane will look like the
dashed line with probability θ/180 and will look like the dotted line otherwise.
Thus, each hash function f in our locality-sensitive family F is built from
a randomly chosen vector vf. Given two vectors x and y, say f(x) = f(y) if
and only if the dot products vf.x and vf.y have the same sign. Then F is a
locality-sensitive family for the cosine distance. The parameters are essentially
the same as for the Jaccard-distance family described in Section 3.6.2, except
the scale of distances is 0–180 rather than 0–1. That is, F is a
(d1, d2, (180 −d1)/180, (180 −d2)/180)-sensitive
family of hash functions. From this basis, we can amplify the family as we wish,
just as for the minhash-based family.
