On low dimensional local embeddings

ABSTRACT

We study the problem of embedding metric spaces into low dimensional l_p spaces while faithfully preserving distances from each point to its k nearest neighbors. We show that any metric space can be embedded into [EQUATION] with k-local distortion of O ((log k)/p). We also show that any ultrametric can be embedded into [EQUATION] with k-local distortion 1 + ε.

Our embedding results have immediate applications to local Distance Oracles. We show how to preprocess a graph in polynomial time to obtain a data structure of O(nk^1/t log² k) bits, such that distance queries from any node to its k nearest neighbors can be answered with stretch O(t).

REFERENCES

• 1: Ittai Abraham , Yair Bartal , Ofer Neimany, Advances in metric embedding theory, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132557]
• 2: Ittai Abraham , Yair Bartal , Ofer Neiman, Local embeddings of metric spaces, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250883]
• 3: Noga Alon. Problems and results in extremal combinatorics--i. Discrete Mathematics, 273(6):31--53, 2003.
• 4: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 5: Yair Bartal , Manor Mendel, Dimension reduction for ultrametrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 6: J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1--2):46--52, 1985.
• 7: Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation algorithms for the 0-extension problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.8-16, January 07-09, 2001, Washington, D.C., United States
• 8: Moses Charikar , Konstantin Makarychev , Yury Makarychev, Local Global Tradeoffs in Metric Embeddings, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.713-723, October 21-23, 2007 [doi>10.1109/FOCS.2007.37]
• 9: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 10: W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189--206. Amer. Math. Soc., Providence, RI, 1984.
• 11: J. Matoušek. On embedding expanders into l_p spaces. Israel J. Math., 102:189--197, 1997.
• 12: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 13: Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304983]
• 14: Gideon Schechtman and Adi Shraibman. Lower bounds for local versions of dimension reductions, 2007. Personal communication.
• 15: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005 [doi>10.1145/1044731.1044732]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms