3.5. DISTANCE MEASURES
97
also have an LSH technique that allows us to focus on nearby points without
comparing all points. Other applications of distance measures will appear when
we study clustering in Chapter 7.
3.5.1
Deﬁnition of a Distance Measure
Suppose we have a set of points, called a space. A distance measure on this
space is a function d(x, y) that takes two points in the space as arguments and
produces a real number, and satisﬁes the following axioms:
1. d(x, y) ≥0 (no negative distances).
2. d(x, y) = 0 if and only if x = y (distances are positive, except for the
distance from a point to itself).
3. d(x, y) = d(y, x) (distance is symmetric).
4. d(x, y) ≤d(x, z) + d(z, y) (the triangle inequality).
The triangle inequality is the most complex condition. It says, intuitively, that
to travel from x to y, we cannot obtain any beneﬁt if we are forced to travel via
some particular third point z. The triangle-inequality axiom is what makes all
distance measures behave as if distance describes the length of a shortest path
from one point to another.
3.5.2
Euclidean Distances
The most familiar distance measure is the one we normally think of as “dis-
tance.” An n-dimensional Euclidean space is one where points are vectors of n
real numbers. The conventional distance measure in this space, which we shall
refer to as the L2-norm, is deﬁned:
d([x1, x2, . . . , xn], [y1, y2, . . . , yn]) =
v
u
u
t
n
X
i=1
(xi −yi)2
That is, we square the distance in each dimension, sum the squares, and take
the positive square root.
It is easy to verify the ﬁrst three requirements for a distance measure are
satisﬁed. The Euclidean distance between two points cannot be negative, be-
cause the positive square root is intended. Since all squares of real numbers are
nonnegative, any i such that xi ̸= yi forces the distance to be strictly positive.
On the other hand, if xi = yi for all i, then the distance is clearly 0. Symmetry
follows because (xi −yi)2 = (yi −xi)2. The triangle inequality requires a good
deal of algebra to verify. However, it is well understood to be a property of
Euclidean space: the sum of the lengths of any two sides of a triangle is no less
than the length of the third side.
