Locality-sensitive Hashing - LSH Algorithm For Nearest Neighbor Search

LSH Algorithm For Nearest Neighbor Search

One of the main application of LSH is to provide efficient nearest neighbor search algorithms. Consider any LSH family . The algorithm has two main parameters: the width parameter and the number of hash tables .

In the first step, we define a new family of hash functions, where each function is obtained by concatenating functions from, i.e., . In other words, a random hash function is obtained by concatenating randomly chosen hash functions from . The algorithm then constructs hash tables, each corresponding to a different randomly chosen hash function .

In the preprocessing step we hash all points from the data set into each of the hash tables. Given that the resulting hash tables have only non-zero entries, one can reduce the amount of memory used per each hash table to using standard hash functions.

Given a query point, the algorithm iterates over the hash functions . For each considered, it retrieves the data points that are hashed into the same bucket as . The process is stopped as soon as a point within distance from is found.

Given the parameters and, the algorithm has the following performance guarantees:

• preprocessing time:, where is the time to evaluate a function on an input point ;
• space:, plus the space for storing data points;
• query time: ;
• the algorithm succeeds in finding a point within distance from (if it exists) with probability at least ;

For a fixed approximation ratio and probabilities and, one can set and, where . Then one obtains the following performance guarantees:

• preprocessing time: ;
• space:, plus the space for storing data points;
• query time: ;