  We study the problem of representing all distances between $n$ points in
$\mathbb R^d$, with arbitrarily small distortion, using as few bits as
possible. We give asymptotically tight bounds for this problem, for Euclidean
metrics, for $\ell_1$ (a.k.a.~Manhattan) metrics, and for general metrics.
  Our bounds for Euclidean metrics mark the first improvement over compression
schemes based on discretizing the classical dimensionality reduction theorem of
Johnson and Lindenstrauss (Contemp.~Math.~1984). Since it is known that no
better dimension reduction is possible, our results establish that Euclidean
metric compression is possible beyond dimension reduction.
