Graph-based time-space trade-offs for approximate near neighbors

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)
16 Downloads (Pure)

Samenvatting

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 = 2o(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 n1+ρs+o(1), for arbitrary ρqs ≥ 0 satisfying (2c2 - 1)ρq + 2c2(c2 - 1)√ρs(1 - ρs) ≥ c4. (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.

Originele taal-2Engels
Titel34th International Symposium on Computational Geometry, SoCG 2018
RedacteurenBettina Speckmann, Csaba Toth
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's1-14
Volume99
ISBN van elektronische versie9783959770668
ISBN van geprinte versie978-3-95977-066-8
DOI's
StatusGepubliceerd - 24 mei 2018
Evenement34th International Symposium on Computational Geometry (SoCG 2018) - Budapest, Hongarije
Duur: 11 jun 201814 jun 2018

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum fur Informatik
Volume99

Congres

Congres34th International Symposium on Computational Geometry (SoCG 2018)
LandHongarije
StadBudapest
Periode11/06/1814/06/18

Vingerafdruk Duik in de onderzoeksthema's van 'Graph-based time-space trade-offs for approximate near neighbors'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Laarhoven, T. (2018). Graph-based time-space trade-offs for approximate near neighbors. In B. Speckmann, & C. Toth (editors), 34th International Symposium on Computational Geometry, SoCG 2018 (Vol. 99, blz. 1-14). [57] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 99). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.57