JournalsjemsVol. 9 , No. 2DOI 10.4171/jems/79

Ramsey partitions and proximity data structures

  • Manor Mendel

    The Open University of Israel, Raanana, Israel
  • Assaf Naor

    New York University, United States
Ramsey partitions and proximity data structures cover


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 in~\cite{BFM86}). We then proceed to construct optimal Ramsey partitions, and use them to show that for every \e(0,1)\e\in (0,1), every nn-point metric space has a subset of size n1\en^{1-\e} which embeds into Hilbert space with distortion O(1/\e)O(1/\e). This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor~\cite{BLMN05}, in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick in~\cite{TZ05}. Namely, we show that for every nn point metric space XX, and k1k\geq 1, there exists an O(k)O(k)-approximate distance oracle whose storage requirement is O(n1+1/k)O\left( n^{1+1/k}\right), 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.