Ramsey partitions and proximity data structures

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 (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman). We then proceed to construct optimal Ramsey partitions, and use them to show that for every e\in (0,1), any 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, in addition to considerably simplifying its proof. We use our new Ramsey partitions to design the best known approximate distance oracles when the distortion is large, closing a gap left open by Thorup and Zwick. 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(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.

21 pages. Two explanatory figures were added, a few typos were fixed

References in corpus (3)

• Fast Construction of Nets in Low Dimensional Metrics, and Their Applications
• On metric Ramsey-type phenomena
• Euclidean quotients of finite metric spaces

Cited by in corpus (15)

• Ultrametric subsets with large Hausdorff dimension
• Ultrametric skeletons
• Scalable Nearest Neighbor Search for Optimal Transport
• Maximum gradient embeddings and monotone clustering
• Approximate Distance Oracle with Constant Query Time
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Embedding proper ultrametric spaces into ${\ell }_p$ and its application to nonlinear Dvoretzky's theorem
• Clan Embeddings into Trees, and Low Treewidth Graphs
• Random Martingales and localization of maximal inequalities
• Fast C-K-R Partitions of Sparse Graphs
• Reliable Spanners for Metric Spaces
• Improved Distance Oracles and Spanners for Vertex-Labeled Graphs
• Two infinite versions of nonlinear Dvoretzky's theorem
• Metric Decompositions of Path-Separable Graphs
• A note on extensions of approximate ultrametrics