Locality-sensitive hashing (LSH) is a family of randomized algorithms for finding similar objects in large datasets. It uses specially designed hash functions whose collision probability is higher for nearby or similar objects than for distant or dissimilar ones. By placing objects with matching hash values into shared buckets, an LSH index can generate a relatively small set of candidates for a similarity query, avoiding an exhaustive comparison with every stored object. Its principal application is approximate nearest-neighbor search, especially in high-dimensional spaces.
Purpose and basic principle
An exact nearest-neighbor query asks for the stored object closest to a query under a specified distance measure. This task underlies information retrieval, pattern matching, and the k-nearest neighbors algorithm. For large datasets, comparing a query with every object can be expensive. Geometric indexes such as a k-d tree can accelerate searches in low-dimensional spaces, but their pruning effectiveness often deteriorates as dimensionality increases.
LSH replaces exact search with a probabilistic candidate-generation process:
- Choose a hash family suited to the intended distance or similarity measure.
- Hash stored objects into buckets, usually in several independent tables.
- Hash a query using the same functions and inspect the corresponding buckets.
- Compare the retrieved candidates using the original distance or similarity measure.
The approximation lies mainly in candidate generation: a true neighbor may fail to appear in the inspected buckets. Computing exact distances for the candidates improves their ranking but does not recover omitted neighbors.
This purpose differs from ordinary hash-table lookup. A conventional hash table supports exact key matching and generally seeks to distribute distinct keys evenly. LSH deliberately encourages collisions between similar but nonidentical objects. It also differs from a cryptographic hash function, which is designed to make meaningful input relationships difficult to infer from outputs.
Formal definition
Let be a space with distance function , and let be a probability distribution over functions , where is a set of hash values.
For a distance threshold , approximation factor , and probabilities , the family is called -sensitive if, for every pair ,
and
Thus, near points collide with relatively high probability, while sufficiently far points collide with relatively low probability. The definition places no corresponding constraint on points in the intermediate region .
The probability is taken over the random choice of hash function. Once selected, a hash function is applied consistently to both stored data and queries.
The associated approximate near-neighbor problem asks for a data structure that, whenever a stored point lies within distance of a query, returns a point within distance with a prescribed success probability. This threshold formulation is central to LSH theory. Practical systems commonly adapt it to return a ranked list of approximate nearest neighbors.
Amplifying the collision gap
A single hash function often admits too many distant objects or misses too many nearby ones. Standard LSH indexing combines functions through two forms of amplification.
Concatenation within a table
Choose independent functions and define a composite key
Two objects share a bucket only if all component hashes match. If their collision probability under one function is , their composite collision probability is .
Concatenation therefore suppresses collisions, particularly unwanted ones, but also reduces the chance of retaining a true neighbor.
Repetition across tables
Build independent tables, each with its own composite function. A point becomes a candidate if it matches the query in at least one table. Its candidate probability is
Increasing raises the probability of retrieving nearby points, at the cost of more storage, bucket probes, and candidate comparisons.
For example, if a near pair has single-hash collision probability , while a far pair has probability , choosing and gives candidate probabilities of approximately and , respectively. These probabilities concern individual pairs; even a small far-pair probability can produce many candidates when the dataset is very large.
The LSH exponent
A central measure of a hash family's efficiency is
assuming .
In the classical construction, choosing approximately
for stored objects yields constant success probability for the approximate near-neighbor problem. Standard bounds have query cost roughly , apart from hash-evaluation costs, dimensional factors, and logarithmic terms, with storage roughly , plus storage for the original data.
These are theoretical bounds for a particular search formulation and construction, not universal performance guarantees for every LSH implementation. A query that must enumerate all qualifying neighbors must also pay for its output size. The distinction matters when comparing time complexity and space complexity across systems.
Major hash families
LSH is not a single hash function. Different similarity measures require different constructions.
MinHash for set similarity
MinHash applies to finite, nonempty sets. Their Jaccard similarity is
This is the same intersection-over-union principle used in intersection over union.
Choose a uniformly random ordering of the universe, and define a set's hash as its first element in that ordering. Then
The equality follows because the first element of belongs to both sets with probability .
Multiple MinHash values form a compact signature. A common indexing scheme divides the signature into bands of rows each, making two sets candidates when any complete band matches. Under independent components, the candidate probability for similarity is
This produces a soft similarity threshold rather than a strict cutoff. Practical implementations usually approximate random orderings with hash functions; their properties depend on the construction used.
Random hyperplanes for angular similarity
For nonzero vectors and , choose a random hyperplane through the origin, represented by an isotropically distributed normal vector , and define
If is the angle between the vectors, then
Vectors pointing in similar directions therefore tend to receive matching bits. Concatenated bits form signatures whose Hamming distance estimates angular separation.
This construction is closely associated with SimHash. It is useful for directional comparisons of document features and vectors such as word embeddings. Angular similarity ignores vector magnitude, so it is not interchangeable with unnormalized Euclidean distance or maximum inner product.
Stable-distribution hashing for vector distances
For distances with , LSH families can be constructed from -stable distributions. A standard form is
where the coordinates of are independently drawn from an appropriate -stable distribution, is uniform on , and is a bucket width.
For Euclidean distance, , Gaussian projections provide the relevant stable distribution. For Manhattan distance, , Cauchy projections are used. For , the corresponding distance expression is not a metric, although stable-distribution hashing still applies to that setting.
The method projects points onto a line and quantizes their positions into intervals. Nearby points are more likely to land in the same interval than distant points. The width controls a trade-off: wider buckets increase collisions, while narrower buckets reduce both unwanted collisions and useful matches.
Coordinate sampling for binary data
For fixed-length binary strings, selecting a coordinate uniformly at random gives
where is the string length and is Hamming distance. Concatenating sampled coordinates produces a basic LSH scheme for binary descriptors.
These examples illustrate why the intended notion of similarity must be specified before selecting a hash family.
Index design and variants
Multi-probe LSH
Multi-probe LSH searches several likely buckets within each table instead of using only the exact query bucket. With projection-based hashes, nearby quantization intervals may contain useful candidates.
By ordering bucket probes according to their expected usefulness, a system can trade additional work per table for fewer tables and lower storage. Poor probe ordering can instead increase work without recovering many additional neighbors.
Data-independent and data-dependent hashing
Classical LSH families are usually data-independent: their defining distribution is selected for a distance measure without being fitted to the particular dataset.
Data-dependent approaches adapt partitions or hashing structures to the stored points. They can improve theoretical or empirical trade-offs under suitable assumptions, but their guarantees and construction costs differ from those of classical LSH.
Learned binary representations are also sometimes described as locality-sensitive hashing in a broader sense. A learned code does not automatically satisfy the formal collision-probability definition; that property must be established separately.
Candidate verification and storage
A practical LSH index usually stores object identifiers in buckets and keeps the original vectors or features separately. Query processing combines bucket lookup, candidate deduplication, distance evaluation, and ranking.
Memory consumption is driven not only by compact signatures but also by repeated identifiers across tables and bucket-management overhead. Index updates are often straightforward in principle, though deletion policies, concurrency, and bucket imbalance can complicate implementations.
Applications
LSH is used where approximate similarity is acceptable and exhaustive comparison is expensive:
- Near-duplicate detection: Finding documents or web pages with overlapping token shingles, commonly through MinHash.
- Multimedia retrieval: Generating candidates from image, audio, or video descriptors in computer vision and related systems.
- Vector retrieval: Searching representations produced by machine learning, provided the hash family matches the retrieval metric.
- Similarity joins: Identifying potentially matching record pairs in a database without comparing every possible pair.
- Recommendation and exploration: Retrieving similar users, items, or feature vectors for a recommender system.
These uses depend on the representation as much as on the index. LSH can preserve a chosen similarity relationship probabilistically; it cannot make an unsuitable feature representation capture semantic similarity.
Limitations and practical trade-offs
Missed neighbors. LSH generally permits false negatives. Additional tables or probes can improve recall but increase storage or query cost.
Metric dependence. A family suited to set overlap is not automatically suitable for angular, Euclidean, or edit distance. Transforming data to fit a supported metric can change the meaning of similarity.
Large candidate sets. Weak collision separation, dense clusters, or poorly chosen parameters can produce large buckets. Candidate verification may then approach the cost of exhaustive search.
Memory overhead. Classical multi-table LSH can require substantial storage. Theoretical sublinear query time may be purchased through superlinear index space.
Parameter sensitivity. The number of concatenated hashes, number of tables, bucket width, and probe budget jointly affect speed and retrieval quality. Suitable settings depend on dataset size, distance distributions, and desired recall.
Competition with other indexes. Graph-based methods, including hierarchical navigable small-world graphs, and compression-based approaches such as product quantization can offer better practical trade-offs for some vector-search workloads. LSH remains distinctive for its explicit collision-based framework and theoretical guarantees for specific distance measures.
Historical development
Andrei Broder's work on document resemblance in 1997 established MinHash as an important technique for estimating set similarity. Piotr Indyk and Rajeev Motwani introduced the locality-sensitive hashing framework for approximate nearest-neighbor search in 1998.
Subsequent developments broadened the supported similarity measures and improved efficiency. Moses Charikar's 2002 work connected similarity estimation with random-hyperplane hashing. Work by Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab Mirrokni in 2004 developed LSH based on stable distributions for vector distances.
Later research investigated multi-probe search, improved collision exponents, data-dependent partitions, and tighter space–query-time trade-offs. These developments made LSH both a practical indexing technique and a central framework in the theoretical study of high-dimensional similarity search.