3.5. DISTANCE MEASURES
99
translate the condition d(x, y) ≤d(x, z) + d(z, y) to the statement that if
h is a random minhash function, then the probability that h(x) ̸= h(y)
is no greater than the sum of the probability that h(x) ̸= h(z) and the
probability that h(z) ̸= h(y). However, this statement is true because
whenever h(x) ̸= h(y), at least one of h(x) and h(y) must be diﬀerent
from h(z). They could not both be h(z), because then h(x) and h(y)
would be the same.
.
3.5.4
Cosine Distance
The cosine distance makes sense in spaces that have dimensions, including Eu-
clidean spaces and discrete versions of Euclidean spaces, such as spaces where
points are vectors with integer components or Boolean (0 or 1) components. In
such a space, points may be thought of as directions. We do not distinguish be-
tween a vector and a multiple of that vector. Then the cosine distance between
two points is the angle that the vectors to those points make. This angle will
be in the range 0 to 180 degrees, regardless of how many dimensions the space
has.
We can calculate the cosine distance by ﬁrst computing the cosine of the
angle, and then applying the arc-cosine function to translate to an angle in the
0-180 degree range. Given two vectors x and y, the cosine of the angle between
them is the dot product x.y divided by the L2-norms of x and y (i.e., their
Euclidean distances from the origin). Recall that the dot product of vectors
[x1, x2, . . . , xn].[y1, y2, . . . , yn] is Pn
i=1 xiyi.
Example 3.14 : Let our two vectors be x = [1, 2, −1] and = [2, 1, 1]. The dot
product x.y is 1 × 2 + 2 × 1 + (−1) × 1 = 3. The L2-norm of both vectors is
√
6. For example, x has L2-norm
p
12 + 22 + (−1)2 =
√
6. Thus, the cosine of
the angle between x and y is 3/(
√
6
√
6) or 1/2. The angle whose cosine is 1/2
is 60 degrees, so that is the cosine distance between x and y.
✷
We must show that the cosine distance is indeed a distance measure. We
have deﬁned it so the values are in the range 0 to 180, so no negative distances
are possible. Two vectors have angle 0 if and only if they are the same direction.5
Symmetry is obvious: the angle between x and y is the same as the angle
between y and x. The triangle inequality is best argued by physical reasoning.
One way to rotate from x to y is to rotate to z and thence to y. The sum of
those two rotations cannot be less than the rotation directly from x to y.
5Notice that to satisfy the second axiom, we have to treat vectors that are multiples of
one another, e.g. [1, 2] and [3, 6], as the same direction, which they are. If we regarded these
as diﬀerent vectors, we would give them distance 0 and thus violate the condition that only
d(x, x) is 0.
