Locality-Sensitive Hashing

Locality-sensitive hashing (LSH) is a class of probabilistic data structures for approximate nearest neighbor search in high-dimensional spaces, introduced by Indyk and Motwani in 1998. The core idea is to design hash families whose collision probability is a monotone function of the similarity between inputs: nearby points land in the same bucket with high probability, distant points rarely do. Formally a hash family is (r1, r2, p1, p2)-sensitive when points within distance r1 collide with probability at least p1 and points beyond r2 collide with probability at most p2, with p1 > p2. Different distance metrics use different families: MinHash for Jaccard similarity over sets, SimHash and random hyperplane projections for cosine similarity, and p-stable distributions for Euclidean distance. A query hashes through several functions, retrieves all points sharing at least one bucket, and re-ranks them exactly. By tuning the number of hash functions per table (band) and the number of tables, an implementer trades recall against query time and memory. LSH gives provable sublinear query bounds and is data-independent, but in practice graph-based indexes like HNSW and learned partitioners often beat plain LSH on the recall–latency frontier. LSH remains popular for near-duplicate detection, clustering, and streaming settings where its strong theoretical guarantees and simple incremental updates are valued.