Everything about Locality-sensitive hashing
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. 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. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Locality-sensitive hashingA 5-minute orientation
- Skim a recent paper: Learnable Locality-Sensitive Hashing for Video Anomaly DetectionInfluential work since 2022
- Pick up a classic book: Language Processing and Intelligent Information SystemsThe most-reprinted book on the subject
- Read the landmark paper: Locality-Sensitive Hashing for Finding Nearest Neighbors [Lecture Notes]Cited 287 times
- Go sideways: MinHashA closely related topic
- Go sideways: Nearest neighbor searchA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Locality-Sensitive Hashing for Finding Nearest Neighbors [Lecture Notes]
Kernelized Locality-Sensitive Hashing
Ranking-Based Locality Sensitive Hashing-Enabled Cancelable Biometrics: Index-of-Max Hashing
Efficient large-scale sequence comparison by locality-sensitive hashing
Bayesian locality sensitive hashing for fast similarity search
Video anomaly detection based on locality sensitive hashing filters
Fast agglomerative hierarchical clustering algorithm using Locality-Sensitive Hashing
Locality-Sensitive Hashing for Chi2 Distance
🆕 Influential since 2022
Learnable Locality-Sensitive Hashing for Video Anomaly Detection
DB-LSH 2.0: Locality-Sensitive Hashing With Query-Based Dynamic Bucketing
Double locality sensitive hashing Bloom filter for high-dimensional streaming anomaly detection
Automatically detecting groups using locality-sensitive hashing in group recommendations
Genomic sketching with multiplicities and locality-sensitive hashing using Dashing 2
📚 Books worth reading
Language Processing and Intelligent Information SystemsMieczysław A. Kłopotek · 2013
The Semantic Web – ISWC 2012Philippe Cudré-Mauroux · 2012
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- MinHash In computer science and data mining, MinHash (or the min-wise independent permutations locality-sensitive hashing scheme) is a technique for quickly estimating…
- Nearest neighbor search Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most…
- Jaccard index The Jaccard index is a statistic used for gauging the similarity and diversity of sample sets. It is defined in general taking the ratio of two sizes (areas…
- Similarity learning Similarity learning is an area of supervised machine learning in artificial intelligence. It is closely related to regression and classification, but the…
- Dimensionality reduction Dimensionality reduction, or dimension reduction, is the transformation of data from a high-dimensional space into a low-dimensional space so that the…
- Count–min sketch In computing, the count–min sketch (CM sketch) is a probabilistic data structure that serves as a frequency table of events in a stream of data. It uses…
- Homomorphic signatures for network coding Network coding has been shown to optimally use bandwidth in a network, maximizing information flow but the scheme is very inherently vulnerable to pollution…
- Universal hashing In mathematics and computing, universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family…