Locality-sensitive hashing

In computer science, locality-sensitive hashing (LSH) is an algorithmic technique that hashes similar input items into the same "buckets" with high probability.[1] (The number of buckets are 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]


An LSH family[1][4][5]  is defined for a metric space  , a threshold   and an approximation factor  . This family   is a family of functions   which map elements from the metric space to buckets  . The LSH family satisfies the following conditions for any two points  , using a function   which is chosen uniformly at random:

  • if  , then   (i.e., p and q collide) with probability at least  ,
  • if  , then   with probability at most  .

A family is interesting when  . Such a family   is called  -sensitive.

Alternatively[6] it is defined with respect to a universe of items U that have a similarity function  . An LSH scheme is a family of hash functions H coupled with a probability distribution D over the functions such that a function   chosen according to D satisfies the property that   for any  .

Locality-preserving hashingEdit

A locality-preserving hashing is a hash function f that maps a point or points in a multidimensional coordinate space to a scalar value, such that if we have three points A, B and C such that


In other words, these are hash functions where the relative distance between the input values is preserved in the relative distance between the output hash values; input values that are closer to each other will produce output hash values that are closer to each other.

This is in contrast to cryptographic hash functions and checksums, which are designed to have random output difference between adjacent inputs.

Locality preserving hashes are related to space-filling curves.[how?]


Given a  -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   from  . We then say that for a hash function  ,   if and only if all   for  . Since the members of   are independently chosen for any  ,   is a  -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   from  . We then say that for a hash function  ,   if and only if   for one or more values of i. Since the members of   are independently chosen for any  ,   is a  -sensitive family.


LSH has been applied to several problem domains, including:

  • Computer security[15]


Bit sampling for Hamming distanceEdit

One of the easiest ways to construct an LSH family is by bit sampling.[5] This approach works for the Hamming distance over d-dimensional vectors  . Here, the family   of hash functions is simply the family of all the projections of points on one of the   coordinates, i.e.,  , where   is the  th coordinate of  . A random function   from   simply selects a random bit from the input point. This family has the following parameters:  ,  .[clarification needed]

Min-wise independent permutationsEdit

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   let  . 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   the event that   corresponds exactly to the event that the minimizer of π over   lies inside  . As h was chosen uniformly at random,   and   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  ,[16] and that this bound is tight.[17]

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

Open source methodsEdit

Nilsimsa HashEdit

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


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

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.

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

Random projectionEdit

For small angles (not too close to orthogonal),   is a pretty good approximation to  .

The random projection method of LSH due to Moses Charikar[6] called SimHash (also sometimes called arccos[23]) 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.

Given an input vector v and a hyperplane defined by r, we let  . That is,   depending on which side of the hyperplane v lies.

Each possible choice of r defines a single function. Let H be the set of all such functions and let D be the uniform distribution once again. It is not difficult to prove that, for two vectors  ,  , where   is the angle between u and v.   is closely related to  .

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 distributionsEdit

The hash function [24]   maps a d dimensional vector   onto the set of integers. Each hash function in the family is indexed by a choice of random   and   where   is a d dimensional vector with entries chosen independently from a stable distribution and   is a real number chosen uniformly from the range [0,r]. For a fixed   the hash function   is given by  .

Other construction methods for hash functions have been proposed to better fit the data. [25] 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 searchEdit

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   from  , i.e.,  . 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 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   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   from q is found.

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

  • preprocessing time:  , where t is the time to evaluate a function   on an input point p;
  • space:  , plus the space for storing data points;
  • query time:  ;
  • the algorithm succeeds in finding a point within distance   from q (if there exists a point within distance R) 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:  ;

See alsoEdit


  1. ^ a b c d Rajaraman, A.; Ullman, J. (2010). "Mining of Massive Datasets, Ch. 3".
  2. ^ Zhao, Kang; Lu, Hongtao; Mei, Jincheng (2014). "Locality Preserving Hashing". pp. 2874–2880. Unknown parameter |conference= ignored (help)
  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. ISSN 1522-4880. S2CID 8024458.
  4. ^ Gionis, A.; Indyk, P.; Motwani, R. (1999). "Similarity Search in High Dimensions via Hashing". Proceedings of the 25th Very Large Database (VLDB) Conference.
  5. ^ a b Indyk, Piotr.; Motwani, Rajeev. (1998). "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.". Proceedings of 30th Symposium on Theory of Computing.
  6. ^ a b Charikar, Moses S. (2002). "Similarity Estimation Techniques from Rounding Algorithms". Proceedings of the 34th Annual ACM Symposium on Theory of Computing. pp. 380–388. CiteSeerX doi:10.1145/509907.509965.
  7. ^ Das, Abhinandan S.; et al. (2007), "Google news personalization: scalable online collaborative filtering", Proceedings of the 16th International Conference on World Wide Web: 271, doi:10.1145/1242572.1242610, ISBN 9781595936547, S2CID 207163129.
  8. ^ 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, S2CID 4613827.
  9. ^ Cochez, Michael; Mou, Hao (2015), "Twister Tries: Approximate Hierarchical Agglomerative Clustering for Average Distance in Linear Time", Proceeding SIGMOD '15 Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data: 505–517, doi:10.1145/2723372.2751521, ISBN 9781450327589, S2CID 14414777.
  10. ^ Brinza, Dumitru; et al. (2010), "RAPID detection of gene–gene interactions in genome-wide association studies", Bioinformatics, 26 (22): 2856–2862, doi:10.1093/bioinformatics/btq529, PMC 3493125, PMID 20871107
  11. ^ dejavu - Audio fingerprinting and recognition in Python, 2018-12-19
  12. ^ 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, S2CID 53695535
  13. ^ 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].
  14. ^ Chen, Beidi; Liu, Zichang; Peng, Binghui; Xu, Zhaozhuo; Li, Jonathan Lingjie; Dao, Tri; Song, Zhao; Shrivastava, Anshumali; Re, Christopher (2021), "MONGOOSE: A Learnable LSH Framework for Efficient Neural Network Training", International Conference on Learning Representation
  15. ^ Oliver, Jonathan; Cheng, Chun; Chen, Yanggui (2013), "TLSH - a locality sensitive hash", 4th Cybercrime and Trustworthy Computing Workshop, doi:10.1109/CTC.2013.9, ISBN 978-1-4799-3076-0
  16. ^ Broder, A.Z.; Charikar, M.; Frieze, A.M.; Mitzenmacher, M. (1998). "Min-wise independent permutations". Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. pp. 327–336. CiteSeerX doi:10.1145/276698.276781. Retrieved 2007-11-14.
  17. ^ Takei, Y.; Itoh, T.; Shinozaki, T. "An optimal construction of exactly min-wise independent permutations". Technical Report COMP98-62, IEICE, 1998.
  18. ^ Matoušek, J.; Stojakovic, M. (2002). "On Restricted Min-Wise Independence of Permutations". Preprint. Retrieved 2007-11-14.
  19. ^ Saks, M.; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000). "Low discrepancy sets yield approximate min-wise independent permutation families". Information Processing Letters. 73 (1–2): 29–32. CiteSeerX doi:10.1016/S0020-0190(99)00163-5. Retrieved 2007-11-14.
  20. ^ Damiani; et al. (2004). "An Open Digest-based Technique for Spam Detection" (PDF). Retrieved 2013-09-01.
  21. ^ Oliver; et al. (2013). "TLSH - A Locality Sensitive Hash". 4th Cybercrime and Trustworthy Computing Workshop. Retrieved 2015-04-06.
  22. ^ "TLSH". Retrieved 2014-04-10.
  23. ^ Alexandr Andoni; Indyk, P. (2008). "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions". Communications of the ACM. 51 (1): 117–122. CiteSeerX doi:10.1145/1327452.1327494. S2CID 6468963.
  24. ^ Datar, M.; Immorlica, N.; Indyk, P.; Mirrokni, V.S. (2004). "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions". Proceedings of the Symposium on Computational Geometry.
  25. ^ 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.
  26. ^ 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 readingEdit

  • Samet, H. (2006) Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. ISBN 0-12-369446-9

External linksEdit