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 |
| Summary: | 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). |
|---|