Similarity & High-Dimensional Search

Locality-Sensitive Hashing

Bucket items so that similar ones collide and dissimilar ones don't — turning nearest-neighbor search into a near-linear scan.

x-axis: the true similarity s of a pair. y-axis: the chance they become candidates. Green is the theoretical S-curve; blue dots are the measured rate; the dashed line is the threshold s*.

What you're seeing

Comparing every pair in a big collection is O(n²) — hopeless at scale. LSH avoids it by hashing items into buckets such that similar items are likely to land together, so you only ever compare pairs that share a bucket. The plot shows the heart of the scheme: for a pair with true similarity s (x-axis), what's the chance they're flagged as candidates (y-axis)? The answer is the green S-curve, and the blue dots — measured by simulating many pairs at each similarity — fall right on it.

The rule

signature: m MinHash rows, split into b bands of r rows (m = b·r)
for each band:  hash its r rows → a bucket
candidate pair = two items that share a bucket in ANY band
then verify candidates exactly

Two items agree on a whole band only if all r of its rows match; they become candidates if that happens in at least one of the b bands.

The invariant

Because each MinHash row matches with probability s (the Jaccard similarity — see MinHash), a specific band's r rows all match with probability s^r, and the pair becomes a candidate unless every band fails: P(candidate) = 1 − (1 − s^r)^b. That function is an S-curve with an inflection — a soft "threshold" — near s* ≈ (1/b)^(1/r). Below s* the probability is crushed toward 0; above it, lifted toward 1. So banding turns the gentle linear relationship "match probability = similarity" into a sharp decision: similar pairs almost always collide, dissimilar pairs almost never do. The blue dots tracking the green curve is that guarantee, measured — exactly what this entry's test verifies across many seeded trials.

The cost

All-pairsLSH ComparisonsO(n²)≈ O(n + #candidates) Index / item—O(b)

Tuning b and r slides and sharpens the threshold to match your similarity cutoff. More bands (with r fixed) lowers s* — more pairs collide, raising recall at the cost of more false candidates to verify; more rows per band raises s* — fewer, higher-quality candidates but more misses. It's a recall/precision dial. The win is replacing the quadratic blowup with a scan over only the pairs that share a bucket.

In the wild

LSH is the workhorse of large-scale similarity search: near-duplicate detection in web crawls and document stores (MinHash-LSH), audio fingerprinting (Shazam-style), recommendation and entity resolution, and approximate nearest neighbor over embeddings. Different distance measures get their own LSH families — MinHash for Jaccard, SimHash / random hyperplanes for cosine, p-stable projections for Euclidean (Datar–Indyk–Immorlica–Mirrokni, 2004). For dense vectors, modern graph indexes like HNSW often win in practice, but LSH remains the theoretically clean, tunable, and streaming-friendly baseline — and the one with provable guarantees.

Try this

Crank Rows per band up and watch the S-curve slam to the right and steepen — only very similar pairs survive. Then add Bands and watch the threshold slide back left as more chances to collide accumulate. You're literally tuning the precision/recall trade-off by reshaping the curve.

References

  1. Indyk, P. & Motwani, R. "Approximate nearest neighbors: towards removing the curse of dimensionality." STOC, 1998. The original LSH.
  2. Leskovec, Rajaraman & Ullman. Mining of Massive Datasets, 2nd ed., §3.4 (LSH, the banding technique and S-curve). mmds.org.
  3. Datar, Indyk, Immorlica & Mirrokni. "Locality-sensitive hashing scheme based on p-stable distributions." SoCG, 2004 — Euclidean LSH.
  4. Andoni, A. Advanced Algorithms (Columbia COMS 4995-8, 2021), Lectures 9–10 (LSH). course materials.