TY - GEN

T1 - Ramsey partitions and proximity data structures

AU - Mendel, Manor

AU - Naor, Assaf

PY - 2006

Y1 - 2006

N2 - This paper addresses the non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce and construct optimal Ramsey partitions, and use them to show that for every ε ∈ (0,1), any n-point metric space has a subset of size n 1-ε which embeds into Hilbert space with distortion 0(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 [26]. Namely, we show that for any n point metric space X, and k > 1, there exists an O (k)-approximate distance oracle whose storage requirement is O(n1+1/k), and whose query time is a universal constant. We also discuss applications to various other geometric data structures, and the relation to well separated pair decompositions.

AB - This paper addresses the non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce and construct optimal Ramsey partitions, and use them to show that for every ε ∈ (0,1), any n-point metric space has a subset of size n 1-ε which embeds into Hilbert space with distortion 0(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 [26]. Namely, we show that for any n point metric space X, and k > 1, there exists an O (k)-approximate distance oracle whose storage requirement is O(n1+1/k), and whose query time is a universal constant. We also discuss applications to various other geometric data structures, and the relation to well separated pair decompositions.

UR - http://www.scopus.com/inward/record.url?scp=35448988431&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35448988431&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2006.65

DO - 10.1109/FOCS.2006.65

M3 - Conference contribution

AN - SCOPUS:35448988431

SN - 0769527205

SN - 9780769527208

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 109

EP - 118

BT - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

T2 - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

Y2 - 21 October 2006 through 24 October 2006

ER -