Ramsey partitions and proximity data structures

Manor Mendel; Assaf Naor

Journal of the European Mathematical Society (2007)

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

Abstract

top
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 ε ( 0 , 1 ) , every n -point metric space has a subset of size n 1 ε which embeds into Hilbert space with distortion O ( 1 / ε ) . 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 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.

How to cite

top

Mendel, 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.