Locality-Sensitive Hashing

Imagine you have one billion images and you want to find the ten most similar to a new one. Comparing every pair would take years. Yet Google Images, Spotify, and TikTok do something like this in milliseconds. The trick is Locality-Sensitive Hashing (LSH).

Normal hash functions are designed to make similar inputs produce wildly different outputs — a single changed character flips half the bits. LSH deliberately inverts this: it uses hash functions where similar inputs are likely to land in the same bucket, while dissimilar inputs are likely to land in different ones.

The idea sounds modest, but its consequences are enormous. Instead of comparing your query to all one billion items, you hash the query, look up its bucket, and compare only the small number of items that collided there. With the right LSH family the probability of collision is mathematically tied to similarity — nearby things collide often, far-away things almost never.

The technique was formalized by Piotr Indyk and Rajeev Motwani in 1998 in their landmark paper on approximate nearest-neighbor search in high-dimensional spaces. Today every major recommendation engine, duplicate-detection system, and semantic search index uses some descendant of their idea.

The demo below shows two 2-D vectors, A (blue) and B (orange). Each random hash function projects both onto a line and checks whether they land in the same interval (bucket). Click New random hashes to try a fresh set of projections, or drag the sliders to change how similar the vectors are.

<p class="hint">{{hint}}</p>
<canvas id="canvas" width="320" height="180"></canvas>
<div class="controls">
  <label>{{label_a}} <span id="aVal">30°</span>
    <input type="range" id="angleA" min="0" max="359" value="30"></label>
  <label>{{label_b}} <span id="bVal">50°</span>
    <input type="range" id="angleB" min="0" max="359" value="50"></label>
</div>
<div class="stats" id="stats"></div>
<div class="btns">
  <button id="rehash" type="button">{{btn_rehash}}</button>
  <button id="align" type="button" class="ghost">{{btn_align}}</button>
  <button id="spread" type="button" class="ghost">{{btn_spread}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; display: block;
         background: #f5f8fb; width: 100%; max-width: 320px; height: auto; }
.controls { margin: .6rem 0; display: flex; flex-direction: column; gap: .3rem; }
label { font-size: .85rem; display: flex; align-items: center; gap: .5rem; }
input[type=range] { flex: 1; }
.stats { font-size: .9rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the pattern: when A and B point in nearly the same direction they collide in most hash functions; as they diverge, collisions become rare. The collision probability is not magic — it equals the cosine similarity of the two vectors. With enough independent hash functions you can estimate how similar any two items are without ever computing a direct distance.

How hard is nearest-neighbor search, and what does LSH actually buy you?

• Exact nearest neighbor in high dimensions is brutal. The best known exact algorithms require time that grows at least linearly in the number of points n for high-dimensional data. Worse, in hundreds or thousands of dimensions every point is nearly the same distance from every other — the so-called curse of dimensionality.
• Approximate nearest neighbor (ANN) is tractable. LSH finds a point within a factor c of the true nearest neighbor in time O(n^ρ) where ρ < 1 — genuinely sub-linear. The approximation ratio c and the exponent ρ are tunable: tighter approximation costs more time.
• The hash family does the work. An LSH family for a similarity measure sim(x, y) is a distribution over hash functions h such that Pr[h(x) = h(y)] = sim(x, y). For cosine similarity this is the random hyperplane family (SimHash, used in Google's code-plagiarism detector). For set-similarity it is MinHash (used to identify near-duplicate web pages). For Euclidean distance it is p-stable projections.
• Amplification by banding. To control false positives and negatives, LSH applies k functions at once and repeats L times (the AND-OR construction). Changing k and L slides the collision probability curve — a steep S-curve that sharply separates "similar" from "dissimilar".
• It is a solved engineering problem, not an open research question. The complexity bounds are well understood; what matters in practice is choosing the right LSH family for your similarity measure and tuning k and L for your recall target.

LSH does not fit neatly into the NP-complete / undecidable narrative of other articles here — it is a probabilistic algorithmic technique that provably solves a hard search problem cheaply, at the cost of small, controllable error. Compare this to dimensionality reduction, which attacks the same curse of dimensionality from a different angle.

LSH is behind more of the internet than most people realize:

• Near-duplicate web page detection: Google and Bing use SimHash to identify pages that are nearly identical — crucial for de-duplicating search indices that crawl trillions of documents.
• Recommendation systems: Spotify's "Discover Weekly" and YouTube's video recommendations use ANN search over high-dimensional embedding vectors. LSH (or its learned successors) makes these queries fast enough to run per-user in real time.
• Plagiarism and copyright detection: MinHash compares document shingles to detect copied text, even across paraphrase. Academics and publishers run it over millions of papers.
• Image and audio fingerprinting: Perceptual hash functions (a close cousin of LSH) let content-ID systems like YouTube's flag re-uploaded videos, and Shazam match a 10-second clip against 70 million songs in under a second.
• Genomics: Comparing a new DNA read against billions of reference sequences is the daily workload of bioinformatics pipelines. Tools like MASH use MinHash to make genome-scale comparisons tractable.
• Vector databases for AI: Every modern vector database (Pinecone, Weaviate, Qdrant) uses ANN indexes — HNSW, IVF, or LSH — to search over the embedding spaces produced by large language models and image encoders. Without sub-linear ANN, retrieval-augmented generation would be too slow to be useful.

Locality-Sensitive Hashing is one of those rare ideas that seems obvious in hindsight but unlocked an entire industry. By carefully choosing hash functions where collision probability equals similarity, LSH transforms a needle-in-a-billion-haystacks problem into a quick bucket lookup — with provable, tunable approximation guarantees.

It is not magic: LSH accepts a small probability of missing the true nearest neighbor. But that tradeoff is exactly right for most real-world applications, where a very good answer retrieved in milliseconds beats a perfect answer that takes hours.

The next time a recommendation surprises you with something you actually love, or a search engine surfaces a page you thought was buried — there is a good chance a hash collision is partly responsible. Similar things fell into the same bucket, and the machine noticed.