locality-sensitive hashing
In plain wordsA trick for finding look-alikes in a huge collection without comparing every pair: items get short codes designed so that similar items tend to share a code, and only items sharing one are compared.
A family of hashing schemes in which the chance that two items receive the same hash value rises with their similarity, so that near neighbors can be found by comparing only items that collide; ordinary and cryptographic hashes aim at the opposite, scattering even nearly identical inputs. Each LSH family matches a similarity measure: MinHashMinHash, n.: A shortcut for spotting near-copies among millions of documents: each document is boiled down to a short fingerprint, and similar documents end up with similar fingerprints. for Jaccard similarityJaccard similarity, n.: A simple score for how much two collections overlap: the number of items they share divided by the number of distinct items in either. Identical sets score 1; sets with nothing in common score 0. between sets, random-hyperplane hashing (SimHash) for angles between vectors (cosine similaritycosine similarity, n.: A score from −1 to 1 for how closely two lists of numbers point the same way, ignoring their size. It is the standard test of whether two texts mean similar things.), and projections onto random lines for Euclidean distanceEuclidean distance, n.: How far apart two points are in a straight line, as a ruler would measure it, extended from two or three dimensions to lists of numbers of any length.. Because a single hash is noisy, schemes are amplified: signatures are split into b bands of r values each, and two items become candidates if any band matches exactly, which turns similarity into a sharp, tunable threshold. LSH powers near-duplicate detection in web crawls and training corpora and was an early method for approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster., though graph-based indexes such as HNSWHNSW, abbr.: A popular way to organize millions of embeddings for fast similarity search: a layered web of links where the search starts with long jumps on sparse top layers, then takes ever shorter steps. now dominate vector retrieval.
With 20 bands of 5 rows, pairs above about 0.55 Jaccard similarity become candidates.
Origin
Introduced by Piotr Indyk and Rajeev Motwani at STOC 1998 to escape the 'curse of dimensionality' in nearest-neighbor search, building on Broder's MinHash. Aristides Gionis, Indyk and Motwani applied it to similarity search in databases (1999), and Moses Charikar's 2002 random-hyperplane scheme became known as SimHash.
Related
- MinHashMinHash, n.: A shortcut for spotting near-copies among millions of documents: each document is boiled down to a short fingerprint, and similar documents end up with similar fingerprints.
- deduplicationdeduplication, n.: Removing repeated copies of the same or nearly the same content from a dataset, so a model does not over-learn whatever happens to be copied many times online.
- Jaccard similarityJaccard similarity, n.: A simple score for how much two collections overlap: the number of items they share divided by the number of distinct items in either. Identical sets score 1; sets with nothing in common score 0.
- approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster.
- cosine similaritycosine similarity, n.: A score from −1 to 1 for how closely two lists of numbers point the same way, ignoring their size. It is the standard test of whether two texts mean similar things.
- vector searchvector search, n.: Searching by closeness instead of exact match: the query and all stored items are lists of numbers, and the search returns the items whose numbers are most similar to the query's.
Sources
- Indyk, P. & Motwani, R. (1998). Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. Proceedings of STOC 1998.
- Charikar, M. S. (2002). Similarity Estimation Techniques from Rounding Algorithms. Proceedings of STOC 2002.
Mentioned in
approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster., deduplicationdeduplication, n.: Removing repeated copies of the same or nearly the same content from a dataset, so a model does not over-learn whatever happens to be copied many times online., Jaccard similarityJaccard similarity, n.: A simple score for how much two collections overlap: the number of items they share divided by the number of distinct items in either. Identical sets score 1; sets with nothing in common score 0., MinHashMinHash, n.: A shortcut for spotting near-copies among millions of documents: each document is boiled down to a short fingerprint, and similar documents end up with similar fingerprints.