Ramsey partitions and proximity data structures

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 epsiv isin (0, 1), any n-point metric space has a subset of size n 1-epsiv which embeds into Hilbert space with distortion O(1/epsiv). This result is best possible and improves part of the metric Ramsey theorem of Bartal et al. (2005), 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 (2005). Namely, we show that for any n point metric space X, and k ges 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 to various other geometric data structures, and the relation to well separated pair decompositions

Authors

• Manor Mendel
• Assaf Naor

Keywords

• Data structures
• Extraterrestrial measurements
• Nonlinear distortion
• Hilbert space
• Application software
• Mathematics
• Computer science
• History
• Data Structure
• Universal Constant
• Subset Size
• Optimal Partition
• Large Distortion
• Query Time
• Lower Bound
• High-dimensional
• Running Time
• Dimensional Space
• Distance Matrix
• Euclidean Space
• Lipschitz Continuous
• Storage Space
• Proof Of Result
• Computational Geometry
• Random Partition
• Ultrametric
• General Metrics
• Partition Tree
• Query Point
• Preprocessing Time