The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

Journal of the European Mathematical Society


Full-Text PDF (242 KB) | Metadata | Table of Contents | JEMS summary
Volume 9, Issue 2, 2007, pp. 253–275
DOI: 10.4171/JEMS/79

Published online: 2007-06-30

Ramsey partitions and proximity data structures

Manor Mendel[1] and Assaf Naor[2]

(1) The Open University of Israel, Raanana, Israel
(2) New York University, United States

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\in (0,1)$, every $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~\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 $n$ point metric space $X$, and $k\geq 1$, there exists an $O(k)$-approximate distance oracle whose storage requirement is $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.

Keywords: Metric Ramsey theorem, approximate distance oracle, proximity data structure

Mendel Manor, Naor Assaf: Ramsey partitions and proximity data structures. J. Eur. Math. Soc. 9 (2007), 253-275. doi: 10.4171/JEMS/79