# Ramsey partitions and proximity data structures

Journal of the European Mathematical Society (2007)

- Volume: 009, Issue: 2, page 253-275
- ISSN: 1435-9855

## Access Full Article

top## Abstract

top## How to cite

topMendel, Manor, and Naor, Assaf. "Ramsey partitions and proximity data structures." Journal of the European Mathematical Society 009.2 (2007): 253-275. <http://eudml.org/doc/277787>.

@article{Mendel2007,

abstract = {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 (also known as the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman in [8]). We then proceed to
construct optimal Ramsey partitions, and use them to show that for every $\varepsilon \in (0,1)$, every $n$-point
metric space has a subset of size $n^\{1−\varepsilon \}$ which embeds into Hilbert space with distortion $O(1/\varepsilon )$. This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor [5], 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 [32]. Namely, we show that for every $n$-point metric space $X$, and $k\ge 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.},

author = {Mendel, Manor, Naor, Assaf},

journal = {Journal of the European Mathematical Society},

keywords = {metric Ramsey theorem; approximate distance oracle; proximity data structure},

language = {eng},

number = {2},

pages = {253-275},

publisher = {European Mathematical Society Publishing House},

title = {Ramsey partitions and proximity data structures},

url = {http://eudml.org/doc/277787},

volume = {009},

year = {2007},

}

TY - JOUR

AU - Mendel, Manor

AU - Naor, Assaf

TI - Ramsey partitions and proximity data structures

JO - Journal of the European Mathematical Society

PY - 2007

PB - European Mathematical Society Publishing House

VL - 009

IS - 2

SP - 253

EP - 275

AB - 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 (also known as the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman in [8]). We then proceed to
construct optimal Ramsey partitions, and use them to show that for every $\varepsilon \in (0,1)$, every $n$-point
metric space has a subset of size $n^{1−\varepsilon }$ which embeds into Hilbert space with distortion $O(1/\varepsilon )$. This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor [5], 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 [32]. Namely, we show that for every $n$-point metric space $X$, and $k\ge 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.

LA - eng

KW - metric Ramsey theorem; approximate distance oracle; proximity data structure

UR - http://eudml.org/doc/277787

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.