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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
25 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publication34th International Symposium on Computational Geometry, SoCG 2018
EditorsBettina Speckmann, Csaba Toth
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-14
Volume99
ISBN (Electronic)9783959770668
ISBN (Print)978-3-95977-066-8
DOIs
Publication statusPublished - 24 May 2018
Event34th International Symposium on Computational Geometry (SoCG 2018) - Budapest, Hungary
Duration: 11 Jun 201814 Jun 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl - Leibniz-Zentrum fur Informatik
Volume99

Conference

Conference34th International Symposium on Computational Geometry (SoCG 2018)
CountryHungary
CityBudapest
Period11/06/1814/06/18

Keywords

  • Approximate nearest neighbor problem
  • Locality-sensitive filters
  • Locality-sensitive hashing
  • Near neighbor graphs
  • Similarity search

Fingerprint

Dive into the research topics of 'Graph-based time-space trade-offs for approximate near neighbors'. Together they form a unique fingerprint.

Cite this