  This paper addresses two problems lying at the intersection of geometric
analysis and theoretical computer science: The non-linear isomorphic Dvoretzky
theorem and the design of good approximate distance oracles for large
distortion. We introduce the notion of Ramsey partitions of a finite metric
space, and show that the existence of good Ramsey partitions implies a solution
to the metric Ramsey problem for large distortion (a.k.a. the non-linear
version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel,
and Milman). We then proceed to construct optimal Ramsey partitions, and use
them to show that for every e\in (0,1), any n-point metric space has a subset
of size n^{1-e} which embeds into Hilbert space with distortion O(1/e). This
result is best possible and improves part of the metric Ramsey theorem of
Bartal, Linial, Mendel and Naor, in addition to considerably simplifying its
proof. We use our new Ramsey partitions to design the best known approximate
distance oracles when the distortion is large, closing a gap left open by
Thorup and Zwick. Namely, we show that for any $n$ point metric space X, and
k>1, there exists an O(k)-approximate distance oracle whose storage requirement
is O(n^{1+1/k}), and whose query time is a universal constant. We also discuss
applications of Ramsey partitions to various other geometric data structure
problems, such as the design of efficient data structures for approximate
ranking.
