Nearest-neighbor-preserving embeddings

ABSTRACT

In this article we introduce the notion of nearest-neighbor-preserving embeddings. These are randomized embeddings between two metric spaces which preserve the (approximate) nearest-neighbors. We give two examples of such embeddings for Euclidean metrics with low “intrinsic” dimension. Combining the embeddings with known data structures yields the best-known approximate nearest-neighbor data structures for such metrics.

REFERENCES

• 1: Dimitris Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journal of Computer and System Sciences, v.66 n.4, p.671-687, 1 June 2003 [doi>10.1016/S0022-0000(03)00025-4]
• 2: Alon, N. 2003. Problems and results in extremal combinatorics. I. Discrete Math. 273, 1--3, 31--53.
• 3: Andoni, A., Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. 2005. Locality-Sensitive hashing scheme based on stable distributions. In Nearest-Neighbor Methods for Learning and Vision: Theory and Practice. MIT Press, Cambridge, MA.
• 4: Sunil Arya , Theocharis Malamatos, Linear-size approximate voronoi diagrams, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.147-155, January 06-08, 2002, San Francisco, California
• 5: Alexander Barvinok, Approximate counting via random optimization, Random Structures & Algorithms, v.11 n.2, p.187-198, Sept. 1997 [doi>10.1002/(SICI)1098-2418(199709)11:2<187::AID-RSA6>3.0.CO;2-O]
• 6: Barvinok, A., and Samorodnitsky, A. 2001. The distance approach to approximate combinatorial counting. Geom. Funct. Anal. 11, 5, 871--899.
• 7: Barvinok, A., and Samorodnitsky, A. 2004. Random weighting, asymptotic counting, and inverse isoperimetry. Preprint.
• 8: Bo Brinkman , Moses Charikar, On the Impossibility of Dimension Reduction in \ell _1, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.514, October 11-14, 2003
• 9: Clarkson, K. 2005. Nearest-Neighbor searching and metric space dimensions. In Nearest-Neighbor Methods for Learning and Vision: Theory and Practice. MIT Press, Cambridge, MA.
• 10: Sanjoy Dasgupta , Anupam Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures & Algorithms, v.22 n.1, p.60-65, January 2003 [doi>10.1002/rsa.10073]
• 11: Durrett, R. 1996. Probability: Theory and Examples, 2nd ed. Duxbury Press, Belmont, CA.
• 12: P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
• 13: Gordon, Y. 1988. On Milman's inequality and random subspaces which escape through a mesh in Rⁿ. In Geometric Aspects of Functional Analysis. Lecture Notes in Math., vol. 1317. Springer, Berlin, 84--106.
• 14: Guedon, O., and Zvavitch, A. 2003. Supremum of a process in terms of trees. In Geometric Aspects of Functional Analysis. Lecture Notes in Math., vol. 1807. Springer, Berlin, 136--147.
• 15: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 16: S. Har-Peled, A Replacement for Voronoi Diagrams of Near Linear Size, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.94, October 14-17, 2001
• 17: Heinonen, J. 2001. Lectures on Analysis on Metric Spaces. Universitext. Springer, New York.
• 18: P. Indyk, On Approximate Nearest Neighbors in Non-Euclidean Spaces, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.148, November 08-11, 1998
• 19: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 20: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 21: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 22: Johnson, W. B., and Lindenstrauss, J. 1984. Extensions of Lipschitz mappings into a Hilbert space. In Proceedings of the Conference in Modern Analysis and Probability (New Haven, Conn., 1982). American Mathematics Society Providence, RI, 189--206.
• 23: Klartag, B., and Mendelson, S. Empirical processes and random projections. J. Funct. Anal. To appear.
• 24: Konyagin, S. V., and Voll′berg, A. L. 1987. On measures with the doubling condition. Izv. Akad. Nauk SSSR Ser. Mat. 51, 3, 666--675.
• 25: Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 26: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
• 27: Lang, U., and Plaut, C. 2001. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata 87, 1--3, 285--307.
• 28: Ledoux, M., and Talagrand, M. 1991. Probability in Banach spaces. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) {Results in Mathematics and Related Areas (3)}, vol. 23. Springer, Berlin. Isoperimetry and processes.
• 29: James R. Lee , Manor Mendel , Assaf Naor, Metric structures in L1: dimension, snowflakes, and average distortion, European Journal of Combinatorics, v.26 n.8, p.1180-1190, November 2005 [doi>10.1016/j.ejc.2004.07.002]
• 30: Lee, J. R., and Naor, A. 2004. Embedding the diamond graph in L_p and dimension reduction in l₁. Geom. Funct. Anal. 14, 4, 745--747.
• 31: Avner Magen, Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.239-253, September 13-15, 2002
• 32: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 33: Schechtman, G. Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math. To appear.
• 34: Schechtman, G. 1989. A remark concerning the dependence on ε in Dvoretzky's theorem. In Geometric Aspects of Functional Analysis (1987--88). Lecture Notes in Math., vol. 1376. Springer, Berlin, 274--277.
• 35: Talagrand, M. 2001. Majorizing measures without measures. Ann. Probab. 29, 1, 411--417.
• 36: Talagrand, M. 1996. Majorizing measures: The generic chaining. Ann. Probab. 24, 3, 1049--1103.
• 37: Talagrand, M. 1987. Regularity of Gaussian processes. Acta Math. 159, 1-2, 99--149.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Nearest neighbor, dimensionality reduction, doubling spaces, embeddings