↑ arvau

Wikipedia / Locality-sensitive hashing

In computer science, locality-sensitive hashing (LSH) is a fuzzy hashing technique that hashes similar input items into the same "buckets" with high probability. The number of buckets is much smaller than the universe of possible input items. Since similar items end up in the same buckets, this technique can be used for data clustering and nearest neighbor search. It differs from conventional hashing techniques in that hash collisions are maximized, not minimized. Alternatively, the technique can be seen as a way to reduce the dimensionality of high-dimensional data; high-dimensional input items can be reduced to low-dimensional versions while preserving relative distances between items.

Hashing-based approximate nearest-neighbor search algorithms generally use one of two main categories of hashing methods: either data-independent methods, such as locality-sensitive hashing (LSH); or data-dependent methods, such as locality-preserving hashing (LPH).

Locality-preserving hashing was initially devised as a way to facilitate data pipelining in implementations of massively parallel algorithms that use randomized routing and universal hashing to reduce memory contention and network congestion.

Definitions

is defined to be an LSH family for

:

  • (i.e., and ,

  • .

-sensitive.

LSH with respect to a similarity measure

Alternatively it is possible to define an LSH family on a universe of items . In this setting, a LSH scheme is a family of hash functions coupled with a probability distribution over chosen according to .

Amplification

.

of hash functions , where each function is constructed from -sensitive family.

of hash functions , where each function is constructed from for one or more values of -sensitive family.

Applications

LSH has been applied to several problem domains, including:

Image similarity identification

Methods

Bit sampling for Hamming distance

One of the easiest ways to construct an LSH family is by bit sampling. This approach works for the Hamming distance over .

Min-wise independent permutations

Suppose is composed of subsets of some ground set of enumerable items and the similarity function of interest is the Jaccard index . If is a permutation on the indices of . Each possible choice of defines a single hash function mapping input sets to elements of .

Define the function family to be the set of all such functions and let be the uniform distribution corresponds exactly to the event that the minimizer of . As define an LSH scheme for the Jaccard index.

Because the symmetric group on elements has size !, choosing a truly random permutation from the full symmetric group is infeasible for even moderately sized . 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 , 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 . Approximate min-wise independence differs from the property by at most a fixed .

Open source methods

Nilsimsa Hash

Nilsimsa is a locality-sensitive hashing algorithm used in anti-spam efforts. 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. The paper suggests that the Nilsimsa satisfies three requirements:

  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.

Testing performed in the paper on a range of file types identified the Nilsimsa hash as having a significantly higher false positive rate when compared to other similarity digest schemes such as TLSH, Ssdeep and Sdhash.

TLSH

TLSH is locality-sensitive hashing algorithm designed for a range of security and digital forensic applications. The goal of TLSH is to generate hash digests for messages such that low distances between digests indicate that their corresponding messages are likely to be similar.

An implementation of TLSH is available as open-source software.

Random projection

The random projection method of LSH due to Moses Charikar called SimHash (also sometimes called arccos) uses an approximation of the cosine distance between vectors. The technique was used to approximate the NP-complete max-cut problem.

The basic idea of this technique is to choose a random hyperplane (defined by a normal unit vector ) at the outset and use the hyperplane to hash input vectors.

Given an input vector and a hyperplane defined by depending on which side of the hyperplane lies. This way, each possible choice of a random hyperplane .

For two vectors between them, it can be shown that

, the probability of two vectors being on different sides of the random hyperplane is approximately proportional to the cosine distance between them.

Stable distributions

The hash function maps a is a -dimensional vector with entries chosen independently from a stable distribution.

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.

Semantic hashing

Semantic hashing is a technique that attempts to map input items to addresses such that closer inputs have higher semantic similarity. The hashcodes are found via training of an artificial neural network or graphical model.

One of the main applications of LSH is to provide a method for efficient approximate nearest neighbor search. The algorithm has two main parameters: the width parameter and the number of hash tables .

of hash functions , where each function is obtained by concatenating . In other words, a random hash function is obtained by concatenating . The algorithm then constructs hash tables, each corresponding to a different randomly chosen hash function .

In the preprocessing step we hash all -dimensional points from the data set into each of the hash tables. Given that the resulting hash tables have only 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:

  • , where on an input point ;

  • , plus the space for storing data points;

  • ;

  • the algorithm succeeds in finding a point within distance from (if there exists a point within distance ;

. Then one obtains the following performance guarantees:

  • ;

  • , plus the space for storing data points;

  • ;

Finding nearest neighbor without fixed dimensionality

To generalize the above algorithm without radius being fixed, we can take the algorithm and do a sort of binary search over . It has been shown that there is a data structure for the approximate nearest neighbor with the following performance guarantees:

  • ;

  • ;

  • ;

Improvements

When . This was shown by and which gave

  • ;

  • ;

can be very large. This happens for example with Jaccard similarity data, where even the most similar neighbor often has a quite low Jaccard similarity with the query. In (not including hashing costs) and similarly the space usage.

See also

References

Further reading

  • Samet, H. (2006) Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann.