Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search

Abstract

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 o

Stats

• citations10
• S2 citations—
• github stars0
• HF likes0
• heat score7.81
• arxiv keychristiani2017fast

Related papers

• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• Optimal Las Vegas Locality Sensitive Data Structures (2017)6.77
• A Framework For Similarity Search With Space-time Tradeoffs Using Locality-sensitive Filtering (2016)8.35
• Locality Sensitive Hashing For Set-queries, Motivated By Group Recommendations (2020)0.00
• DET-LSH: A Locality-sensitive Hashing Scheme With Dynamic Encoding Tree For Approximate Nearest Neighbor Search (2024)9.92
• Distance-sensitive Hashing (2017)8.82
• Multi-level Spherical Locality Sensitive Hashing For Approximate Near Neighbors (2017)0.00