Ramsey partitions and proximity data structures

This paper addresses two problems lying at the intersection of geometricanalysis and theoretical computer science: The non-linear isomorphic Dvoretzkytheorem and the design of good approximate distance oracles for largedistortion. We introduce the notion of Ramsey partitions of a finite metricspace, and show that the existence of good Ramsey partitions implies a solutionto the metric Ramsey problem for large distortion (a.k.a. the non-linearversion of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel,and Milman). We then proceed to construct optimal Ramsey partitions, and usethem to show that for every e\in (0,1), any n-point metric space has a subsetof size n^{1-e} which embeds into Hilbert space with distortion O(1/e). Thisresult is best possible and improves part of the metric Ramsey theorem ofBartal, Linial, Mendel and Naor, in addition to considerably simplifying itsproof. We use our new Ramsey partitions to design the best known approximatedistance oracles when the distortion is large, closing a gap left open byThorup and Zwick. Namely, we show that for any $n$ point metric space X, andk>1, there exists an O(k)-approximate distance oracle whose storage requirementis O(n^{1+1/k}), and whose query time is a universal constant. We also discussapplications of Ramsey partitions to various other geometric data structureproblems, such as the design of efficient data structures for approximateranking.Comment: 21 pages. Two explanatory figures were added, a few typos were fixe