fbpx
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.[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]

Definitions edit

A family   of functions   is defined to be an LSH family[1][6][7] for

  • a metric space  ,
  • a threshold  ,
  • an approximation factor  ,
  • and probabilities  

if it satisfies the following condition. For any two points   and a hash function   chosen uniformly at random from  :

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

Such a family   is called  -sensitive.

LSH with respect to a similarity measure edit

Alternatively[8] it is possible to define an LSH family on a universe of items U endowed with a similarity function  . 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   chosen according to D satisfies   for each  .

Amplification edit

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.

Applications edit

LSH has been applied to several problem domains, including:

Methods edit

Bit sampling for Hamming distance edit

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  . 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:  ,  . That is, any two vectors   with Hamming distance at most   collide under a random   with probability at least  . Any   with Hamming distance at least   collide with probability at most  .

Min-wise independent permutations edit

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  ,[19] and that this bound is tight.[20]

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

Open source methods edit

Nilsimsa Hash edit

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

TLSH edit

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

Random projection edit

 
  is proportional to   on the interval [0,  ]

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

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

 

Since the ratio between   and   is at least 0.87856 when  ,[8][27] the probability of two vectors being on the same side of the random hyperplane is approximately proportional to the cosine distance between them.

Stable distributions edit

The hash function [28]   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. [29] In particular k-means hash functions are better in practice than projection-based hash functions, but without any theoretical guarantee.

Semantic hashing edit

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

Algorithm for nearest neighbor search edit

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 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   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:  , 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 cR 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:  ;

Improvements edit

When t is large, it is possible to reduce the hashing time from  . This was shown by[31] and[32] which gave

  • query time:  ;
  • space:  ;

It is also sometimes the case that the factor   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[33] it was shown how to reduce the query time to   (not including hashing costs) and similarly the space usage.

See also edit

References edit

  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. AAAI Conference on Artificial Intelligence. Vol. 28. pp. 2874–2880.
  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. ^ a b Chin, Andrew (1991). Complexity Issues in General Purpose Parallel Computing (DPhil). University of Oxford. pp. 87–95.
  5. ^ a b Chin, Andrew (1994). "Locality-Preserving Hash Functions for General Purpose Parallel Computation" (PDF). Algorithmica. 12 (2–3): 170–181. doi:10.1007/BF01185209. S2CID 18108051.
  6. ^ Gionis, A.; Indyk, P.; Motwani, R. (1999). "Similarity Search in High Dimensions via Hashing". Proceedings of the 25th Very Large Database (VLDB) Conference.
  7. ^ a b Indyk, Piotr.; Motwani, Rajeev. (1998). "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.". Proceedings of 30th Symposium on Theory of Computing.
  8. ^ a b c d 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 10.1.1.147.4064. doi:10.1145/509907.509965. ISBN 1-58113-495-9.
  9. ^ Das, Abhinandan S.; et al. (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, S2CID 207163129.
  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, S2CID 4613827.
  11. ^ Cochez, Michael; Mou, Hao (2015), "Twister Tries", Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (PDF), pp. 505–517, doi:10.1145/2723372.2751521, ISBN 9781450327589, S2CID 14414777.
  12. ^ 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
  13. ^ dejavu - Audio fingerprinting and recognition in Python, 2018-12-19
  14. ^ 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
  15. ^ 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].
  16. ^ 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
  17. ^ a b Oliver, Jonathan; Cheng, Chun; Chen, Yanggui (2013). TLSH - a locality sensitive hash. 4th Cybercrime and Trustworthy Computing Workshop. pp. 7–13. doi:10.1109/CTC.2013.9. ISBN 978-1-4799-3076-0.
  18. ^ Fanaee-T, Hadi (2024). Natural Learning. arXiv. pp. 1–10.
  19. ^ 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 10.1.1.409.9220. doi:10.1145/276698.276781. Retrieved 2007-11-14.
  20. ^ Takei, Y.; Itoh, T.; Shinozaki, T. "An optimal construction of exactly min-wise independent permutations". Technical Report COMP98-62, IEICE, 1998.
  21. ^ Matoušek, J.; Stojakovic, M. (2002). "On Restricted Min-Wise Independence of Permutations". Preprint. Retrieved 2007-11-14.
  22. ^ 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 10.1.1.20.8264. doi:10.1016/S0020-0190(99)00163-5. Retrieved 2007-11-14.
  23. ^ Damiani; et al. (2004). "An Open Digest-based Technique for Spam Detection" (PDF). Retrieved 2013-09-01.
  24. ^ Oliver; et al. (2013). "TLSH - A Locality Sensitive Hash". 4th Cybercrime and Trustworthy Computing Workshop. Retrieved 2015-06-04.
  25. ^ "TLSH". GitHub. Retrieved 2014-04-10.
  26. ^ 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 10.1.1.226.6905. doi:10.1145/1327452.1327494. S2CID 6468963.
  27. ^ Goemans, Michel X.; Williamson, David P. (1995). "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming". Journal of the ACM. 42 (6). Association for Computing Machinery (ACM): 1115–1145. doi:10.1145/227683.227684. ISSN 0004-5411. S2CID 15794408.
  28. ^ 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.
  29. ^ 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. Bibcode:2010PaReL..31.1348P. doi:10.1016/j.patrec.2010.04.004. S2CID 2666044.
  30. ^ Salakhutdinov, Ruslan; Hinton, Geoffrey (2008). "Semantic hashing". International Journal of Approximate Reasoning. 50 (7): 969–978. doi:10.1016/j.ijar.2008.11.006.
  31. ^ 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.
  32. ^ Christiani, Tobias. "Fast locality-sensitive hashing frameworks for approximate near neighbor search." International Conference on Similarity Search and Applications. Springer, Cham, 2019.
  33. ^ Ahle, Thomas Dybdahl. "On the Problem of   in Locality-Sensitive Hashing." International Conference on Similarity Search and Applications. Springer, Cham, 2020.
  34. ^ 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 edit

  • 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". Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. STOC '97. pp. 618–625. CiteSeerX 10.1.1.50.4927. doi:10.1145/258533.258656. ISBN 978-0-89791-888-6. S2CID 15693787.
  • Chin, Andrew (1994). "Locality-preserving hash functions for general purpose parallel computation" (PDF). Algorithmica. 12 (2–3): 170–181. doi:10.1007/BF01185209. S2CID 18108051.

External links edit

  • Alex Andoni's LSH homepage
  • LSHKIT: A C++ Locality Sensitive Hashing Library
  • A Python Locality Sensitive Hashing library that optionally supports persistence via redis
  • : 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

locality, sensitive, hashing, computer, science, locality, sensitive, hashing, fuzzy, hashing, technique, that, hashes, similar, input, items, into, same, buckets, with, high, probability, number, buckets, much, smaller, than, universe, possible, input, items,. 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 Improvements 5 See also 6 References 7 Further reading 8 External linksDefinitions editA family F displaystyle mathcal F nbsp of functions h M S displaystyle h colon M to S nbsp is defined to be an LSH family 1 6 7 for a metric space M M d displaystyle mathcal M M d nbsp a threshold r gt 0 displaystyle r gt 0 nbsp an approximation factor c gt 1 displaystyle c gt 1 nbsp and probabilities p 1 gt p 2 displaystyle p 1 gt p 2 nbsp if it satisfies the following condition For any two points a b M displaystyle a b in M nbsp and a hash function h displaystyle h nbsp chosen uniformly at random from F displaystyle mathcal F nbsp If d a b r displaystyle d a b leq r nbsp then h a h b displaystyle h a h b nbsp i e p and q collide with probability at least p 1 displaystyle p 1 nbsp If d a b c r displaystyle d a b geq cr nbsp then h a h b displaystyle h a h b nbsp with probability at most p 2 displaystyle p 2 nbsp Such a family F displaystyle mathcal F nbsp is called r c r p 1 p 2 displaystyle r cr p 1 p 2 nbsp sensitive LSH with respect to a similarity measure edit 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 displaystyle phi colon U times U to 0 1 nbsp 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 displaystyle h in H nbsp chosen according to D satisfies P r h a h b ϕ a b displaystyle Pr h a h b phi a b nbsp for each a b U displaystyle a b in U nbsp Amplification edit Given a d 1 d 2 p 1 p 2 displaystyle d 1 d 2 p 1 p 2 nbsp sensitive family F displaystyle mathcal F nbsp we can construct new families G displaystyle mathcal G nbsp by either the AND construction or OR construction of F displaystyle mathcal F nbsp 1 To create an AND construction we define a new family G displaystyle mathcal G nbsp of hash functions g where each function g is constructed from k random functions h 1 h k displaystyle h 1 ldots h k nbsp from F displaystyle mathcal F nbsp We then say that for a hash function g G displaystyle g in mathcal G nbsp g x g y displaystyle g x g y nbsp if and only if all h i x h i y displaystyle h i x h i y nbsp for i 1 2 k displaystyle i 1 2 ldots k nbsp Since the members of F displaystyle mathcal F nbsp are independently chosen for any g G displaystyle g in mathcal G nbsp G displaystyle mathcal G nbsp is a d 1 d 2 p 1 k p 2 k displaystyle d 1 d 2 p 1 k p 2 k nbsp sensitive family To create an OR construction we define a new family G displaystyle mathcal G nbsp of hash functions g where each function g is constructed from k random functions h 1 h k displaystyle h 1 ldots h k nbsp from F displaystyle mathcal F nbsp We then say that for a hash function g G displaystyle g in mathcal G nbsp g x g y displaystyle g x g y nbsp if and only if h i x h i y displaystyle h i x h i y nbsp for one or more values of i Since the members of F displaystyle mathcal F nbsp are independently chosen for any g G displaystyle g in mathcal G nbsp G displaystyle mathcal G nbsp is a d 1 d 2 1 1 p 1 k 1 1 p 2 k displaystyle d 1 d 2 1 1 p 1 k 1 1 p 2 k nbsp sensitive family Applications editLSH 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 Gene expression similarity identification citation needed Audio similarity identification Nearest neighbor search Audio fingerprint 13 Digital video fingerprinting Shared memory organization in parallel computing 4 5 Physical data organization in database management systems 14 Training fully connected neural networks 15 16 Computer security 17 Machine Learning 18 Methods editBit sampling for Hamming distance edit 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 displaystyle 0 1 d nbsp Here the family F displaystyle mathcal F nbsp of hash functions is simply the family of all the projections of points on one of the d displaystyle d nbsp coordinates i e F h 0 1 d 0 1 h x x i for some i 1 d displaystyle mathcal F h colon 0 1 d to 0 1 mid h x x i text for some i in 1 ldots d nbsp where x i displaystyle x i nbsp is the i displaystyle i nbsp th coordinate of x displaystyle x nbsp A random function h displaystyle h nbsp from F displaystyle mathcal F nbsp simply selects a random bit from the input point This family has the following parameters P 1 1 R d displaystyle P 1 1 R d nbsp P 2 1 c R d displaystyle P 2 1 cR d nbsp That is any two vectors x y displaystyle x y nbsp with Hamming distance at most R displaystyle R nbsp collide under a random h displaystyle h nbsp with probability at least P 1 displaystyle P 1 nbsp Any x y displaystyle x y nbsp with Hamming distance at least c R displaystyle cR nbsp collide with probability at most P 2 displaystyle P 2 nbsp Min wise independent permutations edit 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 p is a permutation on the indices of S for A S displaystyle A subseteq S nbsp let h A min a A p a displaystyle h A min a in A pi a nbsp Each possible choice of p 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 displaystyle A B subseteq S nbsp the event that h A h B displaystyle h A h B nbsp corresponds exactly to the event that the minimizer of p over A B displaystyle A cup B nbsp lies inside A B displaystyle A cap B nbsp As h was chosen uniformly at random P r h A h B J A B displaystyle Pr h A h B J A B nbsp and H D displaystyle H D nbsp 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 p It has been established that a min wise independent family of permutations is at least of size lcm 1 2 n e n o n displaystyle operatorname lcm 1 2 ldots n geq e n o n nbsp 19 and that this bound is tight 20 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 21 Approximate min wise independence differs from the property by at most a fixed e 22 Open source methods edit Nilsimsa Hash edit Main article Nilsimsa Hash Nilsimsa is a locality sensitive hashing algorithm used in anti spam efforts 23 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 The digest identifying each message should not vary significantly for changes that can be produced automatically The encoding must be robust against intentional attacks 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 24 TLSH edit TLSH is locality sensitive hashing algorithm designed for a range of security and digital forensic applications 17 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 25 Random projection edit Main article Random projection nbsp 8 u v p displaystyle frac theta u v pi nbsp is proportional to 1 cos 8 u v displaystyle 1 cos theta u v nbsp on the interval 0 p displaystyle pi nbsp The random projection method of LSH due to Moses Charikar 8 called SimHash also sometimes called arccos 26 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 displaystyle h v operatorname sgn v cdot r nbsp That is h v 1 displaystyle h v pm 1 nbsp 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 displaystyle h v nbsp For two vectors u v with angle 8 u v displaystyle theta u v nbsp between them it can be shown that P r h u h v 1 8 u v p displaystyle Pr h u h v 1 frac theta u v pi nbsp Since the ratio between 8 u v p displaystyle frac theta u v pi nbsp and 1 cos 8 u v displaystyle 1 cos theta u v nbsp is at least 0 87856 when 8 u v 0 p displaystyle theta u v in 0 pi nbsp 8 27 the probability of two vectors being on the same side of the random hyperplane is approximately proportional to the cosine distance between them Stable distributions edit The hash function 28 h a b y R d N displaystyle h mathbf a b boldsymbol upsilon mathcal R d to mathcal N nbsp maps a d dimensional vector y displaystyle boldsymbol upsilon nbsp onto the set of integers Each hash function in the family is indexed by a choice of random a displaystyle mathbf a nbsp and b displaystyle b nbsp where a displaystyle mathbf a nbsp is a d dimensional vector with entries chosen independently from a stable distribution and b displaystyle b nbsp is a real number chosen uniformly from the range 0 r For a fixed a b displaystyle mathbf a b nbsp the hash function h a b displaystyle h mathbf a b nbsp is given by h a b y a y b r displaystyle h mathbf a b boldsymbol upsilon left lfloor frac mathbf a cdot boldsymbol upsilon b r right rfloor nbsp Other construction methods for hash functions have been proposed to better fit the data 29 In particular k means hash functions are better in practice than projection based hash functions but without any theoretical guarantee Semantic hashing edit Semantic hashing is a technique that attempts to map input items to addresses such that closer inputs have higher semantic similarity 30 The hashcodes are found via training of an artificial neural network or graphical model citation needed Algorithm for nearest neighbor search editOne of the main applications of LSH is to provide a method for efficient approximate nearest neighbor search algorithms Consider an LSH family F displaystyle mathcal F nbsp 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 G displaystyle mathcal G nbsp of hash functions g where each function g is obtained by concatenating k functions h 1 h k displaystyle h 1 ldots h k nbsp from F displaystyle mathcal F nbsp i e g p h 1 p h k p displaystyle g p h 1 p ldots h k p nbsp In other words a random hash function g is obtained by concatenating k randomly chosen hash functions from F displaystyle mathcal F nbsp 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 displaystyle O n nbsp 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 n L k t displaystyle O nLkt nbsp where t is the time to evaluate a function h F displaystyle h in mathcal F nbsp on an input point p space O n L displaystyle O nL nbsp plus the space for storing data points query time O L k t d n P 2 k displaystyle O L kt dnP 2 k nbsp 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 P 1 k L displaystyle 1 1 P 1 k L nbsp For a fixed approximation ratio c 1 ϵ displaystyle c 1 epsilon nbsp and probabilities P 1 displaystyle P 1 nbsp and P 2 displaystyle P 2 nbsp one can set k log n log 1 P 2 displaystyle k left lceil tfrac log n log 1 P 2 right rceil nbsp and L P 1 k O n r P 1 1 displaystyle L lceil P 1 k rceil O n rho P 1 1 nbsp where r log P 1 log P 2 displaystyle rho tfrac log P 1 log P 2 nbsp Then one obtains the following performance guarantees preprocessing time O n 1 r P 1 1 k t displaystyle O n 1 rho P 1 1 kt nbsp space O n 1 r P 1 1 displaystyle O n 1 rho P 1 1 nbsp plus the space for storing data points query time O n r P 1 1 k t d displaystyle O n rho P 1 1 kt d nbsp Improvements edit When t is large it is possible to reduce the hashing time from O n r displaystyle O n rho nbsp This was shown by 31 and 32 which gave query time O t log 2 1 P 2 P 1 n r d 1 P 1 displaystyle O t log 2 1 P 2 P 1 n rho d 1 P 1 nbsp space O n 1 r P 1 log 2 1 P 2 P 1 displaystyle O n 1 rho P 1 log 2 1 P 2 P 1 nbsp It is also sometimes the case that the factor 1 P 1 displaystyle 1 P 1 nbsp 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 33 it was shown how to reduce the query time to O n r P 1 1 r displaystyle O n rho P 1 1 rho nbsp not including hashing costs and similarly the space usage See also editBloom 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 Public domain geocoding invented in 2008 Multilinear subspace learning Approach to dimensionality reduction Principal component analysis Method of data analysis Random indexing 34 Rolling hash hash function where the input is hashed in a window that moves through the inputPages displaying wikidata descriptions as a fallback Singular value decomposition Matrix decomposition Sparse distributed memory Mathematical model of memory Wavelet compression Mathematical technique used in data compression and analysisPages displaying short descriptions of redirect targetsReferences edit a b c d Rajaraman A Ullman J 2010 Mining of Massive Datasets Ch 3 Zhao Kang Lu Hongtao Mei Jincheng 2014 Locality Preserving Hashing AAAI Conference on Artificial Intelligence Vol 28 pp 2874 2880 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 a b Chin Andrew 1991 Complexity Issues in General Purpose Parallel Computing DPhil University of Oxford pp 87 95 a b Chin Andrew 1994 Locality Preserving Hash Functions for General Purpose Parallel Computation PDF Algorithmica 12 2 3 170 181 doi 10 1007 BF01185209 S2CID 18108051 Gionis A Indyk P Motwani R 1999 Similarity Search in High Dimensions via Hashing Proceedings of the 25th Very Large Database VLDB Conference a b Indyk Piotr Motwani Rajeev 1998 Approximate Nearest Neighbors Towards Removing the Curse of Dimensionality Proceedings of 30th Symposium on Theory of Computing a b c d 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 10 1 1 147 4064 doi 10 1145 509907 509965 ISBN 1 58113 495 9 Das Abhinandan S et al 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 S2CID 207163129 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 Cochez Michael Mou Hao 2015 Twister Tries Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data PDF pp 505 517 doi 10 1145 2723372 2751521 ISBN 9781450327589 S2CID 14414777 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 dejavu Audio fingerprinting and recognition in Python 2018 12 19 Aluc Gunes Ozsu 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 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 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 a b Oliver Jonathan Cheng Chun Chen Yanggui 2013 TLSH a locality sensitive hash 4th Cybercrime and Trustworthy Computing Workshop pp 7 13 doi 10 1109 CTC 2013 9 ISBN 978 1 4799 3076 0 Fanaee T Hadi 2024 Natural Learning arXiv pp 1 10 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 10 1 1 409 9220 doi 10 1145 276698 276781 Retrieved 2007 11 14 Takei Y Itoh T Shinozaki T An optimal construction of exactly min wise independent permutations Technical Report COMP98 62 IEICE 1998 Matousek J Stojakovic M 2002 On Restricted Min Wise Independence of Permutations Preprint Retrieved 2007 11 14 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 10 1 1 20 8264 doi 10 1016 S0020 0190 99 00163 5 Retrieved 2007 11 14 Damiani et al 2004 An Open Digest based Technique for Spam Detection PDF Retrieved 2013 09 01 Oliver et al 2013 TLSH A Locality Sensitive Hash 4th Cybercrime and Trustworthy Computing Workshop Retrieved 2015 06 04 TLSH GitHub Retrieved 2014 04 10 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 10 1 1 226 6905 doi 10 1145 1327452 1327494 S2CID 6468963 Goemans Michel X Williamson David P 1995 Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming Journal of the ACM 42 6 Association for Computing Machinery ACM 1115 1145 doi 10 1145 227683 227684 ISSN 0004 5411 S2CID 15794408 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 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 Bibcode 2010PaReL 31 1348P doi 10 1016 j patrec 2010 04 004 S2CID 2666044 Salakhutdinov Ruslan Hinton Geoffrey 2008 Semantic hashing International Journal of Approximate Reasoning 50 7 969 978 doi 10 1016 j ijar 2008 11 006 Dahlgaard Soren Mathias Baek Tejs Knudsen and Mikkel Thorup Fast similarity sketching 2017 IEEE 58th Annual Symposium on Foundations of Computer Science FOCS IEEE 2017 Christiani Tobias Fast locality sensitive hashing frameworks for approximate near neighbor search International Conference on Similarity Search and Applications Springer Cham 2019 Ahle Thomas Dybdahl On the Problem of p 1 1 displaystyle p 1 1 nbsp in Locality Sensitive Hashing International Conference on Similarity Search and Applications Springer Cham 2020 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 editSamet 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 Proceedings of the twenty ninth annual ACM symposium on Theory of computing STOC 97 pp 618 625 CiteSeerX 10 1 1 50 4927 doi 10 1145 258533 258656 ISBN 978 0 89791 888 6 S2CID 15693787 Chin Andrew 1994 Locality preserving hash functions for general purpose parallel computation PDF Algorithmica 12 2 3 170 181 doi 10 1007 BF01185209 S2CID 18108051 External links editAlex 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 Retrieved from https en wikipedia org w index php title Locality sensitive hashing amp oldid 1221167871, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.