Mikkel Thorup (AT&T Labs)
Suppose we want to store all distances between cities in US. In general, to store exact distances between n points, we need n^2 space, which is prohibitive. For example, the software product MapQuest for finding directions would be a lot faster if they could precompute and store all possible distances, but distinguishing between several million addresses gives several trillion possible distances, which is too much for most computers.
However, if we are willing to settle for approximate distances, we can do significantly better. If we allow distances to be stretched by up to a factor 3, we can represent all the distances in space proportional to n^{3/2} (which in the example above is "only" some billions) so that the distance between any pair of points can be reported in constant time. The above representation is what we call an "approximate distance oracle", and this approximate distance oracle can itself be constructed much more efficiently than all pair-wise distances. Including the construction time, we thus get the fastest known way of finding all pair-wise (approximate) distances between selected cities. For many problems concerning placement of resources, say in the Internet, getting a timely estimate of distances is better than waiting forever.
The above result is best possible in that storing distances with stretch strictly below 3, e.g. 2.99, requires n^2 space, and a stretch stricly below 5 requires n^{3/2} space.
We present a general trade-off between stretch and the space of approximate distance oracles. A conjecture of Erdos from 1964 implies that our trade-off is optimal.
This is joint work with Uri Zwick.