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

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

4 Citations (Scopus)
35 Downloads (Pure)


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 ρ qs ≥ 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 languageEnglish
Title of host publication34th International Symposium on Computational Geometry, SoCG 2018
EditorsCsaba D. Toth, Bettina Speckmann
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages14
ISBN (Print)978-3-95977-066-8
Publication statusPublished - 1 Jun 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
ISSN (Print)1868-8969


Conference34th International Symposium on Computational Geometry (SoCG 2018)


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


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

Cite this