98
CHAPTER 3. FINDING SIMILAR ITEMS
There are other distance measures that have been used for Euclidean spaces.
For any constant r, we can deﬁne the Lr-norm to be the distance measure d
deﬁned by:
d([x1, x2, . . . , xn], [y1, y2, . . . , yn]) = (
n
X
i=1
|xi −yi|r)1/r
The case r = 2 is the usual L2-norm just mentioned. Another common distance
measure is the L1-norm, or Manhattan distance. There, the distance between
two points is the sum of the magnitudes of the diﬀerences in each dimension.
It is called “Manhattan distance” because it is the distance one would have to
travel between points if one were constrained to travel along grid lines, as on
the streets of a city such as Manhattan.
Another interesting distance measure is the L∞-norm, which is the limit
as r approaches inﬁnity of the Lr-norm. As r gets larger, only the dimension
with the largest diﬀerence matters, so formally, the L∞-norm is deﬁned as the
maximum of |xi −yi| over all dimensions i.
Example 3.13 : Consider the two-dimensional Euclidean space (the custom-
ary plane) and the points (2, 7) and (6, 4).
The L2-norm gives a distance
of
p
(2 −6)2 + (7 −4)2 =
√
42 + 32 = 5.
The L1-norm gives a distance of
|2 −6| + |7 −4| = 4 + 3 = 7. The L∞-norm gives a distance of
max(|2 −6|, |7 −4|) = max(4, 3) = 4
✷
3.5.3
Jaccard Distance
As mentioned at the beginning of the section, we deﬁne the Jaccard distance
of sets by d(x, y) = 1 −SIM(x, y). That is, the Jaccard distance is 1 minus the
ratio of the sizes of the intersection and union of sets x and y. We must verify
that this function is a distance measure.
1. d(x, y) is nonnegative because the size of the intersection cannot exceed
the size of the union.
2. d(x, y) = 0 if x = y, because x ∪x = x ∩x = x. However, if x ̸= y, then
the size of x ∩y is strictly less than the size of x ∪y, so d(x, y) is strictly
positive.
3. d(x, y) = d(y, x) because both union and intersection are symmetric; i.e.,
x ∪y = y ∪x and x ∩y = y ∩x.
4. For the triangle inequality, recall from Section 3.3.3 that SIM(x, y) is the
probability a random minhash function maps x and y to the same value.
Thus, the Jaccard distance d(x, y) is the probability that a random min-
hash function does not send x and y to the same value. We can therefore
