Content available in repository
Content available in repository
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
We take a first step towards a rigorous asymptotic analysis of graph-based methods for finding (approximate) nearest neighbors in high-dimensional spaces, by analyzing the complexity of randomized greedy walks on the approximate nearest neighbor graph. For random data sets of size n = 2 ^{o(d)} on the d-dimensional Euclidean unit sphere, using near neighbor graphs we can provably solve the approximate nearest neighbor problem with approximation factor c > 1 in query time n ^{ρq+o(1)} and space n ^{1+ρs+o(1)}, for arbitrary ρ _{q},ρ _{s} ≥ 0 satisfying (2c ^{2} - 1)ρq + 2c ^{2}(c ^{2} - 1)√ρ _{s}(1 - ρ _{s}) ≥ c ^{4}. (1) Graph-based near neighbor searching is especially competitive with hash-based methods for small c and near-linear memory, and in this regime the asymptotic scaling of a greedy graph-based search matches optimal hash-based trade-offs of Andoni-Laarhoven-Razenshteyn-Waingarten [5]. We further study how the trade-offs scale when the data set is of size n = 2 ^{Θ(d)}, and analyze asymptotic complexities when applying these results to lattice sieving.
Original language | English |
---|---|
Title of host publication | 34th International Symposium on Computational Geometry, SoCG 2018 |
Editors | Csaba D. Toth, Bettina Speckmann |
Place of Publication | Dagstuhl |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Number of pages | 14 |
ISBN (Print) | 978-3-95977-066-8 |
DOIs | |
Publication status | Published - 1 Jun 2018 |
Event | 34th International Symposium on Computational Geometry (SoCG 2018) - Budapest, Hungary Duration: 11 Jun 2018 → 14 Jun 2018 |
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 99 |
ISSN (Print) | 1868-8969 |
Conference | 34th International Symposium on Computational Geometry (SoCG 2018) |
---|---|
Country/Territory | Hungary |
City | Budapest |
Period | 11/06/18 → 14/06/18 |
Research output: Contribution to journal › Article › Academic