Locality-sensitive hashing (LSH) is a randomized method for grouping objects so that nearby objects, under a specified distance or similarity measure, collide more often than distant ones. It can narrow a large archive of financial-document vectors to a candidate set before expensive comparisons. A collision means “worth checking”; it does not establish that two documents are identical or that one is the nearest match.
LSH addresses retrieval cost. A method such as k-nearest neighbors instead specifies how to predict from selected neighbors. Approximate retrieval can supply those neighbors, but missed records can change the prediction.
The promise belongs to a family
Choose a distance , near and far thresholds , and probabilities . A hash family is locality-sensitive when, for a function sampled from that family,
The probability is over the choice of hash function, with the two objects held fixed. The definition leaves a transition region between the thresholds; it does not require every near pair to collide or every far pair to separate. This probabilistic separation is the central idea in Indyk and Motwani’s original construction, §4.2.
An ordinary hash table uses equality checks to find an exact key despite collisions. LSH deliberately makes collisions informative about proximity. A cryptographic hash has security objectives and is unsuitable as a substitute for this geometric property. Feature hashing, which maps feature identifiers into a fixed number of coordinates, is another distinct use of hashing.
A random hyperplane gives one angular bit
For a nonzero vector , draw a normal vector with independent standard-normal coordinates and use the dot product to define
The hyperplane through the origin, with normal , divides the space into two sides. Nonzero vectors and separated by angle satisfy
This is the random-hyperplane family described by Charikar (2002), §3. For a pair at , the same-bit probability is . Geometrically, rotate the normal around the circle in the pair’s plane: the two disagreement intervals span altogether, leaving of agreement out of . Boundary orientations have probability zero under the continuous draw; the rule above assigns a zero projection to bit 1.
Now take a separate, fixed direction and three synthetic vectors:
| Vector | Projection | Bit |
|---|---|---|
| 1 | 1 | |
| 2 | 1 | |
| −1 | 0 |
A and B collide under this particular hash. This table is one realized partition, not an estimate of the collision probability; these vectors are not the separate pair.
A fixed split assigns actual buckets; rotating the normal explains a probability over the angular hash family. The two panels use separate synthetic examples.
More selective buckets, more chances to find them
One bit puts everything into just two buckets. A common construction concatenates independently sampled hashes into a table key: all components must match. For a fixed pair with base collision probability , a table collision then has probability .
Build independent tables and retrieve a point if any table matches. Its candidate-inclusion probability becomes
Increasing reduces unwanted candidates but also loses more genuine neighbors. Increasing restores retrieval chances while increasing storage, hash computations and candidate work. These expressions assume independent hash draws within and across tables. They describe a fixed pair, not the probability that every desired neighbor will be found. The Andoni–Indyk–Razenshteyn survey explains concatenation, multiple tables and subsequent distance checks.
Match the geometry to the question
Random-hyperplane bits preserve angular proximity, not raw Euclidean distance. Multiplying a vector by a positive scalar leaves every bit unchanged, however large its Euclidean norm becomes. Two vectors in the same bucket can therefore be far apart in magnitude. For unit-normalized vectors, squared Euclidean distance is , so angular and Euclidean rankings agree; normalization deliberately discards magnitude. Other LSH families target other measures, including Euclidean distance without that normalization. Datar and coauthors (2004) construct a family that works directly with Euclidean-space points.
In a research workflow, define the representation and distance first, retrieve candidates, then recompute the intended similarity or distance on those candidates. Compare retrieval quality and runtime with an exact search on a manageable evaluation set. Exact reranking cannot recover a neighbor that never entered the candidate set, and LSH alone provides no unconditional exact-nearest-neighbor guarantee.
For the prediction step after neighbor retrieval, k-Nearest Neighbours and the Curse of Dimensionality develops averaging, voting and the effect of extra features. Its public page is a preview; the full lesson requires membership.