Approximate line nearest neighbor in high dimensions

ABSTRACT

We consider the problem of approximate nearest neighbors in high dimensions, when the queries are lines. In this problem, given n points in R^d, we want to construct a data structure to support efficiently the following queries: given a line L, report the point p closest to L. This problem generalizes the more familiar nearest neighbor problem. From a practical perspective, lines, and low-dimensional flats in general, may model data under linear variation, such as physical objects under different lighting.

For approximation 1 + ε, we achieve a query time of d³n^0.5+t, for arbitrary small t > 0, with a space of d²n^O(1/ε²+1/t²). To the best of our knowledge, this is the first algorithm for this problem with polynomial space and sub-linear query time.

REFERENCES

• 1: {BHZ07} Ronen Basri, Tal Hassner, and Lihi Zelnik-Manor. Approximate nearest subspace search with applications to pattern recognition. In Computer Vision and Pattern Recognition (CVPR'07), pages 1--8, June 2007.
• 2: Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
• 3: {DG99} S. Dasgupta and A. Gupta. An elementary proof of the johnson-lindenstrauss lemma. ICSI technical report TR-99-006, Berkeley, CA, 1999.
• 4: 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
• 5: 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]
• 6: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces, SIAM Journal on Computing, v.30 n.2, p.457-474, 2000 [doi>10.1137/S0097539798347177]
• 7: Avner Magen, Dimensionality Reductions in ℓ₂ that Preserve Volumes and Distance to Affine Spaces, Discrete & Computational Geometry, v.38 n.1, p.139-153, July 2007 [doi>10.1007/s00454-007-1329-4]
• 8: S. Meiser, Point location in arrangements of hyperplanes, Information and Computation, v.106 n.2, p.286-303, Oct. 1993 [doi>10.1006/inco.1993.1057]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.0 General

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

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