Document Open Access Logo

Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats

Authors Pankaj K. Agarwal, Natan Rubin, Micha Sharir

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.4.pdf
  • Filesize: 0.54 MB
  • 13 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
Natan Rubin
Micha Sharir

Cite As Get BibTex

Pankaj K. Agarwal, Natan Rubin, and Micha Sharir. Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.4

Abstract

We consider the Approximate Nearest Neighbor (ANN) problem where the input set consists of n k-flats in the Euclidean Rd, for any fixed parameters k<d, and where, for each query point q, we want to return an input flat whose distance from q is at most (1 + epsilon) times the shortest such distance, where epsilon > 0 is another prespecified parameter. We present an algorithm that achieves this task with n^{k+1}(log(n)/epsilon)^O(1) storage and preprocessing (where the constant of proportionality in the big-O notation depends on d), and can answer a query in O(polylog(n)) time (where the power of the logarithm depends on d and k). In particular, we need only near-quadratic storage to answer ANN queries amidst a set of n lines in any fixed-dimensional Euclidean space. As a by-product, our approach also yields an algorithm, with similar performance bounds, for answering exact nearest neighbor queries amidst k-flats with respect to any polyhedral distance function. Our results are more general, in that they also
provide a tradeoff between storage and query time.

Subject Classification

Keywords
  • Approximate nearest neighbor search
  • k-flats
  • Polyhedral distance functions
  • Linear programming queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K. Agarwal. Geometric range searching. In J. E. Goodman, J. O'Rourke, and Cs. D. Tóth, editors, Handbook of Discrete and Computational Geometry. CRC Press LLC, Boca Raton, FL, 3rd edition, 2017 (to appear). Google Scholar
  2. Pankaj K. Agarwal. Simplex range searching. In M. Loebl, J. Nešetril, and R. Thomas, editors, Journey Through Discrete Mathematics. Springer, Heidelberg, to appear. Google Scholar
  3. Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM, 51(1):117-122, January 2008. URL: http://dx.doi.org/10.1145/1327452.1327494.
  4. Alexandr Andoni and Piotr Indyk. Nearest neighbors in high-dimensional spaces. In J. E. Goodman, J. O'Rourke, and Cs. D. Tóth, editors, Handbook of Discrete and Computational Geometry. CRC Press LLC, Boca Raton, FL, 3rd edition, 2017 (to appear). Google Scholar
  5. Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, and Huy L. Nguyen. Approximate line nearest neighbor in high dimensions. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'09, pages 293-301, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1496770.1496803.
  6. Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'14, pages 1018-1028, Philadelphia, PA, USA, 2014. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2634074.2634150.
  7. Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Optimal approximate polytope membership. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'17, pages 270-288, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3039686.3039704.
  8. Sunil Arya and Theocharis Malamatos. Linear-size approximate voronoi diagrams. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'02, pages 147-155, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=545381.545400.
  9. Sunil Arya, Theocharis Malamatos, and David M. Mount. Space-efficient approximate voronoi diagrams. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC'02, pages 721-730, New York, NY, USA, 2002. ACM. URL: http://dx.doi.org/10.1145/509907.510011.
  10. Sunil Arya and David M. Mount. Approximate range searching. Computational Geometry, 17(3):135-152, 2000. URL: http://dx.doi.org/10.1016/S0925-7721(00)00022-5.
  11. Sunil Arya and David M. Mount. Computational geometry: Proximity and location. In D. P. Mehta and S. Sahni, editors, Handbook of Data Structures and Applications, chapter 3. Chapman and Hall/CRC, Boca Raton, FL, 2004. Google Scholar
  12. Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM, 45(6):891-923, November 1998. URL: http://dx.doi.org/10.1145/293347.293348.
  13. Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee. Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Co., Inc., River Edge, NJ, USA, 1st edition, 2013. Google Scholar
  14. Ronen Basri, Tal Hassner, and Lihi Zelnik-Manor. Approximate nearest subspace search. IEEE Trans. Pattern Anal. Mach. Intell., 33(2):266-278, February 2011. URL: http://dx.doi.org/10.1109/TPAMI.2010.110.
  15. Marshall Bern. Approximate closest-point queries in high dimensions. Information Processing Letters, 45(2):95-99, 1993. URL: http://dx.doi.org/10.1016/0020-0190(93)90222-U.
  16. Timothy M. Chan. Optimal partition trees. Discrete Comput. Geom., 47(4):661-690, June 2012. URL: http://dx.doi.org/10.1007/s00454-012-9410-z.
  17. L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, and Emo Welzl. Voronoi diagrams of lines in 3-space under polyhedral convex distance functions. Journal of Algorithms, 29(2):238-255, 1998. URL: http://dx.doi.org/10.1006/jagm.1998.0957.
  18. R. M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. Journal of Approximation Theory, 10(3):227-236, 1974. URL: http://dx.doi.org/10.1016/0021-9045(74)90120-8.
  19. Rex A. Dwyer. Higher-dimensional voronoi diagrams in linear expected time. Discrete & Computational Geometry, 6(3):343-367, Sep 1991. URL: http://dx.doi.org/10.1007/BF02574694.
  20. S. Har-Peled. A replacement for voronoi diagrams of near linear size. In Proceedings of the 42Nd IEEE Symposium on Foundations of Computer Science, FOCS'01, pages 94-, Washington, DC, USA, 2001. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=874063.875592.
  21. Sariel Har-Peled. Geometric Approximation Algorithms. American Mathematical Society, Boston, MA, USA, 2011. Google Scholar
  22. Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC'98, pages 604-613, New York, NY, USA, 1998. ACM. URL: http://dx.doi.org/10.1145/276698.276876.
  23. Donald E. Knuth. The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998. Google Scholar
  24. Vladlen Koltun and Micha Sharir. 3-dimensionall euclidean voronoi diagrams of lines with a fixed number of orientations. SIAM J. Comput., 32(3):616-642, March 2003. URL: http://dx.doi.org/10.1137/S0097539702408387.
  25. Vladlen Koltun and Micha Sharir. Polyhedral voronoi diagrams of polyhedra in three dimensions. Discrete & Computational Geometry, 31(1):83-124, Jan 2004. URL: http://dx.doi.org/10.1007/s00454-003-2950-5.
  26. Avner Magen. Dimensionality reductions in ℓ2 that preserve volumes and distance to affine spaces. Discrete Comput. Geom., 38(1):139-153, July 2007. URL: http://dx.doi.org/10.1007/s00454-007-1329-4.
  27. Sepideh Mahabadi. Approximate nearest line search in high dimensions. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 337-354, Philadelphia, PA, USA, 2015. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2722129.2722154.
  28. Jiří Matoušek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(1):157-182, December 1993. URL: http://dx.doi.org/10.1007/BF02573972.
  29. Wolfgang Mulzer, Huy L. Nguyên, Paul Seiferth, and Yannik Stein. Approximate k-flat nearest neighbor search. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC'15, pages 783-792, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2746539.2746559.
  30. Gregory Shakhnarovich, Trevor Darrell, and Piotr Indyk. Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Neural Information Processing). The MIT Press, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact