Introduction

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.

Hash Collisions in Action

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">Two vectors <b>A</b> (blue) and <b>B</b> (orange) are hashed by random
projections. Similar vectors collide (same bucket); dissimilar ones scatter.
Drag the angle sliders or click <b>New random hashes</b> to see the effect.</p>
<canvas id="canvas" width="320" height="180"></canvas>
<div class="controls">
  <label>Angle of A: <span id="aVal">30°</span>
    <input type="range" id="angleA" min="0" max="359" value="30"></label>
  <label>Angle of 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">New random hashes</button>
  <button id="align" type="button" class="ghost">Make A ≈ B</button>
  <button id="spread" type="button" class="ghost">Spread A and B</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// LSH demo: random hyperplane projection hashing.
// A hash function h picks a random unit vector r and computes h(v) = sign(r·v).
// Collision probability = 1 - angle(A,B)/180 = cosine similarity (for unit vectors).
// We use NUM_HASHES independent hash functions and display each bucket outcome.

const NUM_HASHES = 8;
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

// Random projections (unit vectors): each is an angle in degrees.
let projAngles = [];

function randAngle() { return Math.random() * 360; }

function initHashes() {
  projAngles = Array.from({ length: NUM_HASHES }, randAngle);
}

// Convert polar angle (degrees) to unit vector
function toVec(deg) {
  const r = deg * Math.PI / 180;
  return [Math.cos(r), Math.sin(r)];
}

// dot product
function dot(a, b) { return a[0] * b[0] + a[1] * b[1]; }

// LSH bucket for a vector and a projection: sign of dot product
function bucket(vecDeg, projDeg) {
  return dot(toVec(vecDeg), toVec(projDeg)) >= 0 ? 1 : 0;
}

function getAngles() {
  return {
    a: parseInt(document.getElementById('angleA').value),
    b: parseInt(document.getElementById('angleB').value)
  };
}

function draw() {
  const { a, b } = getAngles();
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  const cx = W / 2, cy = H / 2;
  const R = Math.min(W, H) * 0.38;

  // Draw projection lines (faint)
  projAngles.forEach(pa => {
    const [px, py] = toVec(pa);
    ctx.save();
    ctx.strokeStyle = 'rgba(0,0,0,0.10)';
    ctx.lineWidth = 1;
    ctx.setLineDash([3, 3]);
    ctx.beginPath();
    ctx.moveTo(cx - px * R, cy - py * R);
    ctx.lineTo(cx + px * R, cy + py * R);
    ctx.stroke();
    ctx.restore();
  });

  // Draw axes
  ctx.strokeStyle = '#c5cdd6';
  ctx.lineWidth = 0.8;
  ctx.setLineDash([]);
  ctx.beginPath(); ctx.moveTo(cx - R, cy); ctx.lineTo(cx + R, cy); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(cx, cy - R); ctx.lineTo(cx, cy + R); ctx.stroke();

  // Draw vector B (orange)
  const [bx, by] = toVec(b);
  ctx.strokeStyle = '#e07b39';
  ctx.lineWidth = 2.5;
  ctx.setLineDash([]);
  ctx.beginPath(); ctx.moveTo(cx, cy); ctx.lineTo(cx + bx * R, cy - by * R); ctx.stroke();
  // arrowhead B
  drawArrow(ctx, cx + bx * R, cy - by * R, b, '#e07b39');

  // Draw vector A (blue)
  const [ax, ay] = toVec(a);
  ctx.strokeStyle = '#1d6fa5';
  ctx.lineWidth = 2.5;
  ctx.beginPath(); ctx.moveTo(cx, cy); ctx.lineTo(cx + ax * R, cy - ay * R); ctx.stroke();
  drawArrow(ctx, cx + ax * R, cy - ay * R, a, '#1d6fa5');

  // Labels
  ctx.font = 'bold 13px system-ui';
  ctx.fillStyle = '#1d6fa5';
  ctx.fillText('A', cx + ax * (R + 10) - 4, cy - ay * (R + 10) + 5);
  ctx.fillStyle = '#e07b39';
  ctx.fillText('B', cx + bx * (R + 10) - 4, cy - by * (R + 10) + 5);

  // Compute collisions
  const collisions = projAngles.filter(pa => bucket(a, pa) === bucket(b, pa)).length;
  const pct = Math.round(collisions / NUM_HASHES * 100);

  // Draw hash results as colored squares
  const sqSize = 18, sqGap = 4;
  const totalW = NUM_HASHES * (sqSize + sqGap) - sqGap;
  let sx = cx - totalW / 2;
  const sy = H - sqSize - 6;
  projAngles.forEach((pa, i) => {
    const same = bucket(a, pa) === bucket(b, pa);
    ctx.fillStyle = same ? '#2dc653' : '#e63946';
    roundRect(ctx, sx + i * (sqSize + sqGap), sy, sqSize, sqSize, 3);
    ctx.fill();
  });

  // Legend for squares
  ctx.font = '10px system-ui';
  ctx.fillStyle = '#555';
  ctx.fillText('each square = 1 hash function  ■ collide  ■ scatter', cx - totalW / 2, sy - 4);

  // Stats text
  const cosAngle = Math.round(Math.abs(((a - b + 360) % 360)));
  const angleDiff = cosAngle > 180 ? 360 - cosAngle : cosAngle;
  const expected = Math.round((1 - angleDiff / 180) * 100);
  document.getElementById('stats').textContent =
    fmt('Collisions: %collisions%/%NUM_HASHES% (%pct%%) — angle between A and B: %angleDiff%° — expected collision rate: %expected%%', { collisions: collisions, NUM_HASHES: NUM_HASHES, pct: pct, angleDiff: angleDiff, expected: expected });
}

function drawArrow(ctx, x, y, angleDeg, color) {
  const r = (angleDeg + 180) * Math.PI / 180;
  const len = 9;
  const spread = 0.4;
  ctx.fillStyle = color;
  ctx.beginPath();
  ctx.moveTo(x, y);
  ctx.lineTo(x + Math.cos(r - spread) * len, y - Math.sin(r - spread) * len);
  ctx.lineTo(x + Math.cos(r + spread) * len, y - Math.sin(r + spread) * len);
  ctx.closePath();
  ctx.fill();
}

function roundRect(ctx, x, y, w, h, r) {
  ctx.beginPath();
  ctx.moveTo(x + r, y);
  ctx.arcTo(x + w, y, x + w, y + h, r);
  ctx.arcTo(x + w, y + h, x, y + h, r);
  ctx.arcTo(x, y + h, x, y, r);
  ctx.arcTo(x, y, x + w, y, r);
  ctx.closePath();
}

function updateLabels() {
  const a = document.getElementById('angleA').value;
  const b = document.getElementById('angleB').value;
  document.getElementById('aVal').textContent = a + '°';
  document.getElementById('bVal').textContent = b + '°';
}

document.getElementById('angleA').addEventListener('input', () => { updateLabels(); draw(); });
document.getElementById('angleB').addEventListener('input', () => { updateLabels(); draw(); });
document.getElementById('rehash').addEventListener('click', () => { initHashes(); draw(); });
document.getElementById('align').addEventListener('click', () => {
  const a = parseInt(document.getElementById('angleA').value);
  document.getElementById('angleB').value = (a + 10) % 360;
  updateLabels(); draw();
});
document.getElementById('spread').addEventListener('click', () => {
  document.getElementById('angleA').value = 30;
  document.getElementById('angleB').value = 150;
  updateLabels(); draw();
});

initHashes();
draw();

// Verify in console: collision probability ≈ 1 - angleDiff/180
(function verify() {
  // For two vectors 60° apart, expected collision rate per hash = 1 - 60/180 ≈ 0.667
  let hits = 0;
  const trials = 10000;
  for (let i = 0; i < trials; i++) {
    const pa = Math.random() * 360;
    if (bucket(0, pa) === bucket(60, pa)) hits++;
  }
  const rate = hits / trials;
  const expected = 1 - 60 / 180;
  const ok = Math.abs(rate - expected) < 0.05;
  console.log('LSH verify: 60° apart, collision rate =', rate.toFixed(3),
    'expected', expected.toFixed(3), ok ? '✓ PASS' : '✗ FAIL');
})();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/locality-sensitive-hashing/Content licensed under CC BY-NC 4.0.