Beyond locality-sensitive hashing
We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in R[superscript d], our algorithm achieves O[subscript c](n[superscript ρ] + d log n) query time and O[subscript c](n[superscript 1+ρ] + d log n) space, where ρ ≤ 7/(8c[superscript...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2018
|
| Online Access: | http://hdl.handle.net/1721.1/114155 https://orcid.org/0000-0002-7983-9524 https://orcid.org/0000-0002-3962-721X |
| _version_ | 1826189171258032128 |
|---|---|
| author | Andoni, Alexandr Nguyen, Huy L. 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 Nguyen, Huy L. Indyk, Piotr Razenshteyn, Ilya |
| author_sort | Andoni, Alexandr |
| collection | MIT |
| description | We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in R[superscript d], our algorithm achieves O[subscript c](n[superscript ρ] + d log n) query time and O[subscript c](n[superscript 1+ρ] + d log n) space, where ρ ≤ 7/(8c[superscript 2]) + O(1/c[superscript 3]) + o[subscript c](1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By a standard reduction we obtain a data structure for the Hamming space and ℓ[subscript 1] norm with ρ ≤ 7/(8c)+ O(1/c[superscript 3/2])+ o[superscript c](1), which is the first improvement over the result of Indyk and Motwani (STOC 1998). |
| first_indexed | 2024-09-23T08:10:57Z |
| format | Article |
| id | mit-1721.1/114155 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:10:57Z |
| publishDate | 2018 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/1141552022-09-30T08:07:51Z Beyond locality-sensitive hashing Andoni, Alexandr Nguyen, Huy L. Indyk, Piotr Razenshteyn, Ilya Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Indyk, Piotr Razenshteyn, Ilya We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in R[superscript d], our algorithm achieves O[subscript c](n[superscript ρ] + d log n) query time and O[subscript c](n[superscript 1+ρ] + d log n) space, where ρ ≤ 7/(8c[superscript 2]) + O(1/c[superscript 3]) + o[subscript c](1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By a standard reduction we obtain a data structure for the Hamming space and ℓ[subscript 1] norm with ρ ≤ 7/(8c)+ O(1/c[superscript 3/2])+ o[superscript c](1), which is the first improvement over the result of Indyk and Motwani (STOC 1998). 2018-03-14T18:14:06Z 2018-03-14T18:14:06Z 2014-01 Article http://purl.org/eprint/type/ConferencePaper 978-1-611973-38-9 http://hdl.handle.net/1721.1/114155 Andoni, Alexandr. "Beyond Locality-Sensitive Hashing." SODA '14 Proceedings of the Twenty-fifth Annual ACM-SIAM Aymposium on Discrete Algorithms, 5-7 January, 2014, Philadelphia, Pennsylvania, Association for Computing Machinery, 2014, pp. 1018-1028. https://orcid.org/0000-0002-7983-9524 https://orcid.org/0000-0002-3962-721X en_US http://dl.acm.org/citation.cfm?id=2634150&CFID=969998081&CFTOKEN=28708107 SODA '14 Proceedings of the Twenty-Fifth annual ACM-SIAM Symposium on Discrete Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery MIT Web Domain |
| spellingShingle | Andoni, Alexandr Nguyen, Huy L. Indyk, Piotr Razenshteyn, Ilya Beyond locality-sensitive hashing |
| title | Beyond locality-sensitive hashing |
| title_full | Beyond locality-sensitive hashing |
| title_fullStr | Beyond locality-sensitive hashing |
| title_full_unstemmed | Beyond locality-sensitive hashing |
| title_short | Beyond locality-sensitive hashing |
| title_sort | beyond locality sensitive hashing |
| url | http://hdl.handle.net/1721.1/114155 https://orcid.org/0000-0002-7983-9524 https://orcid.org/0000-0002-3962-721X |
| work_keys_str_mv | AT andonialexandr beyondlocalitysensitivehashing AT nguyenhuyl beyondlocalitysensitivehashing AT indykpiotr beyondlocalitysensitivehashing AT razenshteynilya beyondlocalitysensitivehashing |