Locality-Sensitive Hashing

Ordinary hash functions are built to spread similar inputs apart, so that a hash table never has two different keys landing in the same bucket by coincidence. Locality-sensitive hashing (LSH) does the opposite on purpose: it uses hash functions engineered so that inputs which are close together in the original space are likely to hash to the same bucket, while distant inputs are unlikely to.

Why this is useful

Once similar points are grouped into buckets, finding approximate neighbors of a new point is just: hash it, look at whoever else is in that bucket, and compare against only those candidates. Using several independent hash tables in parallel and taking the union of their buckets raises the odds of catching a true neighbor without sacrificing much speed, since each individual hash function only needs to be "good enough," not perfect.

This is the technique behind near-duplicate detection at web scale — search engines finding pages that are copies of each other, or music-recognition apps matching a hummed tune against a library of millions of songs — where comparing every pair of items directly would be computationally impossible.

Worked example

Searching for near-duplicates among 100 million documents by brute force means roughly 5 quadrillion pairwise comparisons. With LSH tuned so that documents sharing 80% of their content collide in the same bucket with high probability, each document typically lands with only a few dozen candidates worth comparing directly — cutting the work by many orders of magnitude, at the cost of occasionally missing a genuine near-duplicate that happened to hash differently.