Data-dependent hashing via nonlinear spectral gaps

Alexandr Andoni; Assaf Naor; Aleksandar Nikolov; Ilya Razenshteyn; Erik Waingarten

doi:https://doi.org/10.1145/3188745.3188846

Data-dependent hashing via nonlinear spectral gaps

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten · 2018

We establish a generic reduction from _nonlinear spectral gaps_ of metric spaces to data-dependent Locality-Sensitive Hashing, yielding a new approach to the high-dimensional Approximate Near Neighbor Search problem (ANN) under various distance functions. Using this reduction, we obtain the following results:

Read the paper · More papers on PaperTik