# Locality-sensitive hashing

Locality-sensitive hashing (LSH) is a method of performing probabilistic dimension reduction of high-dimensional data. The basic idea is to hash the input items so that similar items are mapped to the same buckets with high probability (the number of buckets being much smaller than the universe of possible input items). The hashing used in LSH is different from conventional hash functions, such as those used in cryptography, as in the LSH case the goal is to maximize probability of "collision" of similar items rather than avoid collisions.  Note how locality-sensitive hashing, in many ways, mirrors data clustering and nearest neighbor search.

## Applications

LSH has been applied to several problem domains including{{ safesubst:#invoke:Unsubst||date=__DATE__ |\$B= {{#invoke:Category handler|main}}{{#invoke:Category handler|main}}[citation needed] }}

{{#invoke:Category handler|main}}{{#invoke:Category handler|main}}[citation needed] }}

## Methods

### Min-wise independent permutations

{{#invoke:main|main}}

Because the symmetric group on n elements has size n!, choosing a truly random permutation from the full symmetric group is infeasible for even moderately sized n. Because of this fact, there has been significant work on finding a family of permutations that is "min-wise independent" - a permutation family for which each element of the domain has equal probability of being the minimum under a randomly chosen $\pi$ . It has been established that a min-wise independent family of permutations is at least of size $lcm(1,2,...,n)\geq e^{n-o(n)}$ . and that this bound is tight

Because min-wise independent families are too big for practical applications, two variant notions of min-wise independence are introduced: restricted min-wise independent permutations families, and approximate min-wise independent families. Restricted min-wise independence is the min-wise independence property restricted to certain sets of cardinality at most k. Approximate min-wise independence differs from the property by at most a fixed $\epsilon$ .

### Nilsimsa Hash

{{#invoke:main|main}}

Nilsimsa is an anti-spam focused locality-sensitive hashing algorithm. The goal of Nilsimsa is to generate a hash digest of an email message such that the digests of two similar messages are similar to each other. Nilsimsa satisfies three requirements outlined by the paper's authors:

1. The digest identifying each message should not vary significantly for changes that can be produced automatically.
2. The encoding must be robust against intentional attacks.
3. The encoding should support an extremely low risk of false positives.

### Random projection

The random projection method of LSH (termed arccos by Andoni and Indyk ) is designed to approximate the cosine distance between vectors. The basic idea of this technique is to choose a random hyperplane (defined by a normal unit vector $r$ ) at the outset and use the hyperplane to hash input vectors.

In this instance hashing produces only a single bit. Two vectors' bits match with probability proportional to the cosine of the angle between them.

### Stable distributions

Other construction methods for hash functions have been proposed to better fit the data.  In particular k-means hash functions are better in practice than projection-based hash functions, but without any theoretical guarantee.

## LSH algorithm for nearest neighbor search

One of the main applications of LSH is to provide a method for efficient approximate nearest neighbor search algorithms. Consider an LSH family ${\mathcal {F}}$ . The algorithm has two main parameters: the width parameter $k$ and the number of hash tables $L$ .

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