Locality-sensitive hashing

Short description: Algorithmic technique using 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.[1] The number of buckets is much smaller than the universe of possible input items.[1] 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).[2][3]

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.[4][5]

## Contents

* 1 Definitions
* 1.1 LSH with respect to a similarity measure
* 1.2 Amplification
* 2 Applications
* 3 Methods
* 3.1 Bit sampling for Hamming distance
* 3.2 Min-wise independent permutations
* 3.3 Open source methods
* 3.3.1 Nilsimsa Hash
* 3.3.2 TLSH
* 3.4 Random projection
* 3.5 Stable distributions
* 3.6 Semantic hashing
* 4 Algorithm for nearest neighbor search
* 4.1 Finding nearest neighbor without fixed dimensionality
* 4.2 Improvements
* 5 See also
* 6 References
* 7 Further reading
* 8 External links

## Definitions

A finite family ℱ of functions h:M->S is defined to be an LSH family[1][6][7] for

* a metric space ℳ=(M,d),
* a threshold r>0,
* an approximation factor c>1,
* and probabilities p1>p2

if it satisfies the following condition. For any two points a,b∈M and a hash function h chosen uniformly at random from ℱ:

* If d(a,b)≤r, then h(a)=h(b) (i.e., a and b collide) with probability at least p1,
* If d(a,b)≥cr, then h(a)=h(b) with probability at most p2.

Such a family ℱ is called (r,cr,p1,p2)-sensitive.

### LSH with respect to a similarity measure

Alternatively[8] it is possible to define an LSH family on a universe of items U endowed with a similarity function ϕ:U×U->[0,1]. In this setting, a LSH scheme is a family of hash functions H coupled with a probability distribution D over H such that a function h∈H chosen according to D satisfies Pr[h(a)=h(b)]=ϕ(a,b) for each a,b∈U.

### Amplification

Given a (d1,d2,p1,p2)-sensitive family ℱ, we can construct new families 𝒢 by either the AND-construction or OR-construction of ℱ.[1]

To create an AND-construction, we define a new family 𝒢 of hash functions g, where each function g is constructed from k random functions h1,…,hk from ℱ. We then say that for a hash function g∈𝒢, g(x)=g(y) if and only if all hi(x)=hi(y) for i=1,2,…,k. Since the members of ℱ are independently chosen for any g∈𝒢, 𝒢 is a (d1,d2,p1k,p2k)-sensitive family.

To create an OR-construction, we define a new family 𝒢 of hash functions g, where each function g is constructed from k random functions h1,…,hk from ℱ. We then say that for a hash function g∈𝒢, g(x)=g(y) if and only if hi(x)=hi(y) for one or more values of i. Since the members of ℱ are independently chosen for any g∈𝒢, 𝒢 is a (d1,d2,1−(1−p1)k,1−(1−p2)k)-sensitive family.

## Applications

LSH has been applied to several problem domains, including:

* Near-duplicate detection[9]
* Hierarchical clustering[10][11]
* Genome-wide association study[12]
* Image similarity identification
* VisualRank
* Audio similarity identification
* Nearest neighbor search
* Audio fingerprint[13]
* Digital video fingerprinting[14]
* Shared memory organization in parallel computing[4][5]
* Physical data organization in database management systems[15]
* Training fully connected neural networks[16][17]
* Computer security[18]
* Machine learning[19]

## Methods

### Bit sampling for Hamming distance

One of the easiest ways to construct an LSH family is by bit sampling.[7] This approach works for the Hamming distance over d-dimensional vectors {0,1}d. Here, the family ℱ of hash functions is simply the family of all the projections of points on one of the d coordinates, i.e., ℱ={h:{0,1}d->{0,1}∣h(x)=xi for some i∈{1,…,d}}, where xi is the ith coordinate of x. A random function h from ℱ simply selects a random bit from the input point. This family has the following parameters: P1=1−R/d, P2=1−cR/d. That is, any two vectors x,y with Hamming distance at most R collide under a random h with probability at least P1. Any x,y with Hamming distance at least cR collide with probability at most P2.

### Min-wise independent permutations

Main article: MinHash

Suppose U is composed of subsets of some ground set of enumerable items S and the similarity function of interest is the Jaccard index J. If π is a permutation on the indices of S, for A⊆S let h(A)=mina∈A{π(a)}. Each possible choice of π defines a single hash function h mapping input sets to elements of S.

Define the function family H to be the set of all such functions and let D be the uniform distribution. Given two sets A,B⊆S the event that h(A)=h(B) corresponds exactly to the event that the minimizer of π over A∪B lies inside A∩B. As h was chosen uniformly at random, Pr[h(A)=h(B)]=J(A,B) and (H,D) define an LSH scheme for the Jaccard index.

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 π. It has been established that a min-wise independent family of permutations is at least of size lcm⁡{1,2,…,n}≥en−o(n),[20] and that this bound is tight.[21]

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.[22] Approximate min-wise independence differs from the property by at most a fixed ε.[23]

### Open source methods

#### Nilsimsa Hash

Nilsimsa is a locality-sensitive hashing algorithm used in anti-spam efforts.[24] 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.[25]

#### TLSH

TLSH is locality-sensitive hashing algorithm designed for a range of security and digital forensic applications.[18] 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.[26]

### Random projection

Main article: Random projection

θ(u,v)π is approximately proportional to 1−cos⁡(θ(u,v)) on the interval [0, π

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

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.

Given an input vector v and a hyperplane defined by r, we let h(v)=sgn⁡(v⋅r). That is, h(v)=±1 depending on which side of the hyperplane v lies. This way, each possible choice of a random hyperplane r can be interpreted as a hash function h(v).

For two vectors u,v with angle θ(u,v) between them, it can be shown that

Pr[h(u)=h(v)]=1−θ(u,v)π.

Since the ratio between θ(u,v)π and 1−cos⁡(θ(u,v)) is at least 0.439 when θ(u,v)∈[0,π],[8][28] 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 [29] h𝐚,b(υ):ℛd->𝒩 maps a d-dimensional vector υ onto the set of integers. Each hash function in the family is indexed by a choice of random 𝐚 and b where 𝐚 is a d-dimensional vector with entries chosen independently from a stable distribution and b is a real number chosen uniformly from the range [0,r]. For a fixed 𝐚,b the hash function h𝐚,b is given by h𝐚,b(υ)=⌊𝐚⋅υ+br⌋.

Other construction methods for hash functions have been proposed to better fit the data. [30] 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.[31] The hashcodes are found via training of an artificial neural network or graphical model.

## 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 ℱ. The algorithm has two main parameters: the width parameter k and the number of hash tables L.

In the first step, we define a new family 𝒢 of hash functions g, where each function g is obtained by concatenating k functions h1,…,hk from ℱ, i.e., g(p)=[h1(p),…,hk(p)]. In other words, a random hash function g is obtained by concatenating k randomly chosen hash functions from ℱ. The algorithm then constructs L hash tables, each corresponding to a different randomly chosen hash function g.

In the preprocessing step we hash all n d-dimensional 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.

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

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

* preprocessing time: O(nLkt), where t is the time to evaluate a function h∈ℱ on an input point p;
* space: O(nL), plus the space for storing data points;
* query time: O(L(kt+dnP2k));
* the algorithm succeeds in finding a point within distance cR from q (if there exists a point within distance R) with probability at least 1−(1−P1k)L;

For a fixed approximation ratio c=1+ϵ and probabilities P1 and P2, one can set k=⌈log⁡nlog⁡1/P2⌉ and L=⌈P1−k⌉=O(nρP1−1), where ρ=log⁡P1log⁡P2. Then one obtains the following performance guarantees:

* preprocessing time: O(n1+ρP1−1kt);
* space: O(n1+ρP1−1), plus the space for storing data points;
* query time: O(nρP1−1(kt+d));

### Finding nearest neighbor without fixed dimensionality

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

* space: O(n1+ρP1−1dlog2n);
* query time: O(nρP1−1(kt+d)log⁡n);
* the algorithm succeeds in finding the nearest neighbor with probability at least 1−((1−P1k)Llog⁡n);

### Improvements

When t is large, it is possible to reduce the hashing time from O(nρ). This was shown by[33] and[34] which gave

* query time: O(tlog2(1/P2)/P1+nρ(d+1/P1));
* space: O(n1+ρ/P1+log2(1/P2)/P1);

It is also sometimes the case that the factor 1/P1 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[35] it was shown how to reduce the query time to O(nρ/P11−ρ) (not including hashing costs) and similarly the space usage.

## See also

* Bloom filter - Data structure for approximate set membership
* Curse of dimensionality - Difficulties arising when analyzing data with many aspects ("dimensions")
* Feature hashing - Vectorizing features using a hash function
* Fourier-related transforms
* Geohash
* Multilinear subspace learning - Approach to dimensionality reduction
* Principal component analysis - Method of data analysis
* Random indexing[36]
* Rolling hash - Type of hash function
* Singular value decomposition - Matrix decomposition
* Sparse distributed memory - Mathematical model of memory
* Wavelet compression
* Locality of reference - Tendency of a processor to access nearby memory locations in space or time

## References

1. ↑ 1.0 1.1 1.2 1.3 Rajaraman, A.; Ullman, J. (2010). "Mining of Massive Datasets, Ch. 3.". http://infolab.stanford.edu/~ullman/mmds.html.
2. ↑ Zhao, Kang; Lu, Hongtao; Mei, Jincheng (2014). "Locality Preserving Hashing". AAAI Conference on Artificial Intelligence. 28. pp. 2874–2880. https://ojs.aaai.org/index.php/AAAI/article/view/9133/8992.
3. ↑ Tsai, Yi-Hsuan; Yang, Ming-Hsuan (October 2014). "Locality preserving hashing". 2014 IEEE International Conference on Image Processing (ICIP). pp. 2988–2992. doi:10.1109/ICIP.2014.7025604. ISBN 978-1-4799-5751-4.
4. ↑ 4.0 4.1 Chin, Andrew (1991). Complexity Issues in General Purpose Parallel Computing (DPhil). University of Oxford. pp. 87–95.
5. ↑ 5.0 5.1 Chin, Andrew (1994). "Locality-Preserving Hash Functions for General Purpose Parallel Computation". Algorithmica 12 (2–3): 170–181. doi:10.1007/BF01185209. http://unclaw.com/chin/scholarship/hashfunctions.pdf.
6. ↑ Gionis, A. (1999). "Similarity Search in High Dimensions via Hashing". Proceedings of the 25th Very Large Database (VLDB) Conference. https://people.csail.mit.edu/indyk/vldb99.ps.
7. ↑ 7.0 7.1 Indyk, Piotr.; Motwani, Rajeev. (1998). "Proceedings of 30th Symposium on Theory of Computing".
8. ↑ 8.0 8.1 8.2 8.3 "Proceedings of the 34th Annual ACM Symposium on Theory of Computing". 2002. pp. 380–388. doi:10.1145/509907.509965. ISBN 1-58113-495-9.
9. ↑ Das, Abhinandan S. (2007), "Google news personalization: scalable online collaborative filtering", Proceedings of the 16th international conference on World Wide Web, pp. 271–280, doi:10.1145/1242572.1242610, ISBN 9781595936547 .
10. ↑ Koga, Hisashi; Tetsuo Ishibashi; Toshinori Watanabe (2007), "Fast agglomerative hierarchical clustering algorithm using Locality-Sensitive Hashing", Knowledge and Information Systems 12 (1): 25–53, doi:10.1007/s10115-006-0027-5 .
11. ↑ Cochez, Michael; Mou, Hao (2015), "Twister Tries", Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 505–517, doi:10.1145/2723372.2751521, ISBN 9781450327589, https://jyx.jyu.fi/bitstream/123456789/46537/1/cochezmousigmod15finalcameraready.pdf .
12. ↑ Brinza, Dumitru (2010), "RAPID detection of gene–gene interactions in genome-wide association studies", Bioinformatics 26 (22): 2856–2862, doi:10.1093/bioinformatics/btq529, PMID 20871107
13. ↑ dejavu - Audio fingerprinting and recognition in Python, 2018-12-19, https://github.com/worldveil/dejavu
14. ↑ A Simple Introduction to Locality Sensitive Hashing (LSH), 2025-03-27, https://www.iunera.com/kraken/fabric/locality-sensitive-hashing-lsh/#7-applications-of-lsh
15. ↑ Aluç, Güneş; Özsu, M. Tamer; Daudjee, Khuzaima (2018), "Building self-clustering RDF databases using Tunable-LSH", The VLDB Journal 28 (2): 173–195, doi:10.1007/s00778-018-0530-9
16. ↑ Chen, Beidi; Medini, Tharun; Farwell, James; Gobriel, Sameh; Tai, Charlie; Shrivastava, Anshumali (2020-02-29). "SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems". arXiv:1903.03129 [cs.DC].
17. ↑ Chen, Beidi; Liu, Zichang; Peng, Binghui; Xu, Zhaozhuo; Li, Jonathan Lingjie; Dao, Tri; Song, Zhao; Shrivastava, Anshumali et al. (2021), "MONGOOSE: A Learnable LSH Framework for Efficient Neural Network Training", International Conference on Learning Representation, https://openreview.net/forum?id=wWK7yXkULyh
18. ↑ 18.0 18.1 Oliver, Jonathan; Cheng, Chun; Chen, Yanggui (2013). "2013 Fourth Cybercrime and Trustworthy Computing Workshop". pp. 7–13. doi:10.1109/CTC.2013.9. ISBN 978-1-4799-3076-0. https://www.academia.edu/7833902.
19. ↑ Fanaee-T, Hadi (2024), Natural Learning
20. ↑ "Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing". 1998. pp. 327–336. doi:10.1145/276698.276781.
21. ↑ Takei, Y.; Itoh, T.; Shinozaki, T.. "An optimal construction of exactly min-wise independent permutations". Technical Report COMP98-62, IEICE, 1998.
22. ↑ Matoušek, J.; Stojakovic, M. (2002). "On Restricted Min-Wise Independence of Permutations". Preprint. http://citeseer.ist.psu.edu/689217.html. Retrieved 2007-11-14.
23. ↑ "Low discrepancy sets yield approximate min-wise independent permutation families". Information Processing Letters 73 (1–2): 29–32. 2000. doi:10.1016/S0020-0190(99)00163-5. http://citeseer.ist.psu.edu/saks99low.html. Retrieved 2007-11-14.
24. ↑ Damiani (2004). "An Open Digest-based Technique for Spam Detection". https://spdp.di.unimi.it/papers/pdcs04.pdf.
25. ↑ Oliver (2013). "TLSH - A Locality Sensitive Hash". 4th Cybercrime and Trustworthy Computing Workshop. https://www.academia.edu/7833902. Retrieved 2015-06-04.
26. ↑ "TLSH". https://github.com/trendmicro/tlsh.
27. ↑ Alexandr Andoni; Indyk, P. (2008). "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions". Communications of the ACM 51 (1): 117–122. doi:10.1145/1327452.1327494.
28. ↑ Goemans, Michel X.; Williamson, David P. (1995). "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming". Journal of the ACM (Association for Computing Machinery (ACM)) 42 (6): 1115–1145. doi:10.1145/227683.227684. ISSN 0004-5411.
29. ↑ Datar, M. (2004). "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions". Proceedings of the Symposium on Computational Geometry. http://theory.csail.mit.edu/~mirrokni/pstable.ps.
30. ↑ Pauleve, L.; Jegou, H.; Amsaleg, L. (2010). "Locality sensitive hashing: A comparison of hash function types and querying mechanisms". Pattern Recognition Letters 31 (11): 1348–1358. doi:10.1016/j.patrec.2010.04.004. Bibcode: 2010PaReL..31.1348P. https://hal.inria.fr/inria-00567191/en/.
31. ↑ Salakhutdinov, Ruslan; Hinton, Geoffrey (2008). "Semantic hashing" (in en). International Journal of Approximate Reasoning 50 (7): 969–978. doi:10.1016/j.ijar.2008.11.006.
32. ↑ Har-Peled, Sariel; Indyk, Piotr; Motwani, Rajeev (2012). "Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality". Theory of Computing 8 (Special Issue in Honor of Rajeev Motwani): 321–350. doi:10.4086/toc.2012.v008a014. https://theoryofcomputing.org/articles/v008a014/v008a014.pdf. Retrieved 23 May 2025.
33. ↑ Dahlgaard, Søren, Mathias Bæk Tejs Knudsen, and Mikkel Thorup. "Fast similarity sketching." 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2017.
34. ↑ Christiani, Tobias. "Fast locality-sensitive hashing frameworks for approximate near neighbor search." International Conference on Similarity Search and Applications. Springer, Cham, 2019.
35. ↑ Ahle, Thomas Dybdahl. "On the Problem of p1−1 in Locality-Sensitive Hashing." International Conference on Similarity Search and Applications. Springer, Cham, 2020.
36. ↑ Gorman, James, and James R. Curran. "Scaling distributional similarity to large corpora." Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. Association for Computational Linguistics, 2006.

## Further reading

* Samet, H. (2006) Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. ISBN 0-12-369446-9
* Indyk, Piotr; Motwani, Rajeev; Raghavan, Prabhakar; Vempala, Santosh (1997). "Locality-preserving hashing in multidimensional spaces". STOC '97. pp. 618–625. doi:10.1145/258533.258656. ISBN 978-0-89791-888-6.
* Chin, Andrew (1994). "Locality-preserving hash functions for general purpose parallel computation". Algorithmica 12 (2–3): 170–181. doi:10.1007/BF01185209. http://www.unclaw.com/chin/scholarship/hashfunctions.pdf.

## External links

* Alex Andoni's LSH homepage
* LSHKIT: A C++ Locality Sensitive Hashing Library
* A Python Locality Sensitive Hashing library that optionally supports persistence via redis
* Caltech Large Scale Image Search Toolbox: a Matlab toolbox implementing several LSH hash functions, in addition to Kd-Trees, Hierarchical K-Means, and Inverted File search algorithms.
* Slash: A C++ LSH library, implementing Spherical LSH by Terasawa, K., Tanaka, Y
* LSHBOX: An Open Source C++ Toolbox of Locality-Sensitive Hashing for Large Scale Image Retrieval, Also Support Python and MATLAB.
* SRS: A C++ Implementation of An In-memory, Space-efficient Approximate Nearest Neighbor Query Processing Algorithm based on p-stable Random Projection
* TLSH open source on Github
* JavaScript port of TLSH (Trend Micro Locality Sensitive Hashing) bundled as node.js module
* Java port of TLSH (Trend Micro Locality Sensitive Hashing) bundled as maven package

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Locality-sensitive hashing. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Locality-sensitive_hashing&oldid=3988661"