Locality-sensitive hashing

Locality-sensitive hashing (LSH) is a family of algorithmic techniques for hashing high-dimensional data points so that similar points map to the same hash bucket with high probability. Unlike conventional hash functions, which spread inputs uniformly to minimize collisions, LSH functions are designed to "amplify" collisions for nearby points while preserving separation for distant ones. This makes LSH the foundational primitive for sublinear-time approximate nearest-neighbor search, near-duplicate detection, and large-scale similarity search in information retrieval and machine learning.

The mathematical insight behind LSH was formalized by Indyk and Motwani in 1998: for a given distance metric, a family of hash functions is locality-sensitive if the probability of collision is a decreasing function of the distance between points. Concrete constructions exist for many metrics — random projection for cosine similarity, MinHash for Jaccard similarity, p-stable distributions for Lp norms — each tailored to the geometry of the target space.

LSH is not a single algorithm but a design paradigm. The choice of hash family, the number of hash tables, and the concatenation of hash functions all determine the trade-off between false positives (distant points hashed together) and false negatives (nearby points hashed apart). In practice, modern systems often combine LSH with graph-based or quantization methods to achieve the recall-latency balances required by production vector databases.

LSH is a gamble with geometry: it trades the certainty of exhaustive search for the probability of collision. But this gamble is not merely computational — it is epistemological. By accepting that similarity is a stochastic property, LSH acknowledges that in high-dimensional spaces, the very notion of a "nearest neighbor" dissolves into a cloud of likely candidates. The hash bucket is not a category; it is a probability distribution in disguise.