Approxiamate Nearest Neighbor Search in High Dimensions
The nearest neighbor problem is defined as follows: Given a set P of n points in some metric space (X; D), build a data structure that, given any point q, returns a point in P that is closest to q (its “nearest neighbor” in P). The data structure stores additional information about the set P, which...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
International Mathematical Union
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129551 |
| _version_ | 1826199731991216128 |
|---|---|
| author | Andoni, Alexandr Indyk, Piotr Razenshteyn, Ilya |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Andoni, Alexandr Indyk, Piotr Razenshteyn, Ilya |
| author_sort | Andoni, Alexandr |
| collection | MIT |
| description | The nearest neighbor problem is defined as follows: Given a set P of n points in some metric space (X; D), build a data structure that, given any point q, returns a point in P that is closest to q (its “nearest neighbor” in P). The data structure stores additional information about the set P, which is then used to find the nearest neighbor without computing all distances between q and P . The problem has a wide range of applications in machine learning, computer vision, databases and other fields. To reduce the time needed to find nearest neighbors and the amount of memory used by the data structure, one can formulate the approximate nearest neighbor problem, where the the goal is to return any point p′ ∊ P such that the distance from q to p′ is at most c minp∊P D(q; p), for some c ≥ 1. Over the last two decades many efficient solutions to this problem were developed. In this article we survey these developments, as well as their connections to questions in geometric functional analysis and combinatorial geometry. |
| first_indexed | 2024-09-23T11:25:11Z |
| format | Article |
| id | mit-1721.1/129551 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:25:11Z |
| publishDate | 2021 |
| publisher | International Mathematical Union |
| record_format | dspace |
| spelling | mit-1721.1/1295512022-10-01T03:28:37Z Approxiamate Nearest Neighbor Search in High Dimensions Andoni, Alexandr Indyk, Piotr Razenshteyn, Ilya Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science The nearest neighbor problem is defined as follows: Given a set P of n points in some metric space (X; D), build a data structure that, given any point q, returns a point in P that is closest to q (its “nearest neighbor” in P). The data structure stores additional information about the set P, which is then used to find the nearest neighbor without computing all distances between q and P . The problem has a wide range of applications in machine learning, computer vision, databases and other fields. To reduce the time needed to find nearest neighbors and the amount of memory used by the data structure, one can formulate the approximate nearest neighbor problem, where the the goal is to return any point p′ ∊ P such that the distance from q to p′ is at most c minp∊P D(q; p), for some c ≥ 1. Over the last two decades many efficient solutions to this problem were developed. In this article we survey these developments, as well as their connections to questions in geometric functional analysis and combinatorial geometry. 2021-01-25T19:16:02Z 2021-01-25T19:16:02Z 2018-08 2020-12-18T16:08:02Z Article http://purl.org/eprint/type/ConferencePaper 1041-4347 https://hdl.handle.net/1721.1/129551 Andoni, Alexandr et al. “Approximate Nearest Neighbor Search in High Dimensions.” Proceedings of the International Congress of Mathematicians, Volume 4, August 2018, Rio de Janeiro, Brazil, International Mathematical Union, 2018. © 2018 Sociedade Brasileira de Matemática and International Mathematical Union. en 10.1142/9789813272880_0182 https://www.mathunion.org/icm/proceedings Proceedings of the International Congress of Mathematicians Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf International Mathematical Union arXiv |
| spellingShingle | Andoni, Alexandr Indyk, Piotr Razenshteyn, Ilya Approxiamate Nearest Neighbor Search in High Dimensions |
| title | Approxiamate Nearest Neighbor Search in High Dimensions |
| title_full | Approxiamate Nearest Neighbor Search in High Dimensions |
| title_fullStr | Approxiamate Nearest Neighbor Search in High Dimensions |
| title_full_unstemmed | Approxiamate Nearest Neighbor Search in High Dimensions |
| title_short | Approxiamate Nearest Neighbor Search in High Dimensions |
| title_sort | approxiamate nearest neighbor search in high dimensions |
| url | https://hdl.handle.net/1721.1/129551 |
| work_keys_str_mv | AT andonialexandr approxiamatenearestneighborsearchinhighdimensions AT indykpiotr approxiamatenearestneighborsearchinhighdimensions AT razenshteynilya approxiamatenearestneighborsearchinhighdimensions |