Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search
Tobias Christiani . Lecture Notes in Computer Science 2017 – 3 citations
[Paper]
The Indyk-Motwani Locality-Sensitive Hashing (LSH) framework (STOC 1998) is a general technique for constructing a data structure to answer approximate near neighbor queries by using a distribution (\mathcal{H}) over locality-sensitive hash functions that partition space. For a collection of (n) points, after preprocessing, the query time is dominated by (O(n^{\rho} log n)) evaluations of hash functions from (\mathcal{H}) and (O(n^{\rho})) hash table lookups and distance computations where (\rho \in (0,1)) is determined by the locality-sensitivity properties of (\mathcal{H}). It follows from a recent result by Dahlgaard et al. (FOCS 2017) that the number of locality-sensitive hash functions can be reduced to (O(log^2 n)), leaving the query time to be dominated by (O(n^{\rho})) distance computations and (O(n^{\rho} log n)) additional word-RAM operations. We state this result as a general framework and provide a simpler analysis showing that the number of lookups and distance computations closely match the Indyk-Motwani framework, making it a viable replacement in practice. Using ideas from another locality-sensitive hashing framework by Andoni and Indyk (SODA 2006) we are able to reduce the number of additional word-RAM operations to (O(n^\rho)).