Locality-Sensitive Hashing (LSH), in depth: MinHash banding, random hyperplanes, p-stable projections and when to choose it over HNSW

The definition

A family H of hash functions is called (r, cr, p1, p2)-sensitive for a distance d if, for a function h drawn at random from H, any two points within distance r collide with probability at least p1, and any two points farther than cr apart collide with probability at most p2, with p1 greater than p2. Ordinary hash functions try to make every pair collide with the same tiny probability; LSH families make the probability depend on distance.

A single function is a weak filter: if p1 is 0.8 and p2 is 0.5, it separates near from far only slightly. The quality of a family is summarised by rho = ln(1/p1) / ln(1/p2). The classical result is that a family with exponent rho answers approximate near-neighbour queries in roughly n to the rho time with n to the 1 + rho space. For Hamming distance with bit sampling, rho is 1/c, so asking for neighbours within a factor of two gives square-root query time. That is sublinear, but not logarithmic, and the constants are large, which is why tuning matters so much in practice.

Amplification: bands and rows

Amplification turns a weak family into a strong one using two operations. AND: concatenate r functions into one key; two items collide only if all r agree, so the probability becomes p to the r, which pushes far pairs towards zero, and near pairs down too. OR: build b independent tables; an item is a candidate if it collides in any of them, giving 1 - (1 - p^r)^b, which lifts near pairs back up. Together they produce an S-curve with a steep rise near the threshold t, approximately (1/b) to the power 1/r.

Both configurations use 128 hash values per item, but they place the threshold very differently: about 0.71 for 16 bands of 8 rows and about 0.42 for 32 bands of 4 rows. More rows per band raise the threshold and sharpen the cut; more bands lower it and improve recall at the cost of more tables and more candidates to verify. Choosing b and r is therefore choosing the similarity you care about and the relative cost of a false negative against a false positive.

MinHash for Jaccard similarity

For sets, the natural similarity is Jaccard: the size of the intersection divided by the size of the union. Broder's MinHash, developed at AltaVista in 1997 to detect near-duplicate web pages, is an LSH family for it. Apply a random permutation to the universe of elements and take the smallest permuted value in the set. For two sets A and B, the smallest element of their union under the permutation is equally likely to be any element of the union, and the two minimums agree exactly when that element is in the intersection. So the probability that the MinHash values match equals the Jaccard similarity, which makes the fraction of matching values across k independent hashes an unbiased estimate with standard error about sqrt(s(1 - s)/k).

True random permutations are too expensive, so implementations use universal hash functions of the form (a*x + b) mod p over a hashed element, which behave closely enough for practical purposes.

import numpy as np, zlib

P = (1 << 61) - 1          # Mersenne prime; Python ints avoid overflow
rng = np.random.default_rng(42)

def shingles(text, k=5):
    w = text.lower().split()
    return {" ".join(w[i:i+k]) for i in range(max(1, len(w) - k + 1))}

def make_hashes(num_perm=128):
    return [(int(a), int(b)) for a, b in zip(rng.integers(1, P, num_perm), rng.integers(0, P, num_perm))]

def minhash(items, hashes):
    xs = [zlib.crc32(s.encode()) for s in items]
    return [min((a * x + b) % P for x in xs) for a, b in hashes]

def est_jaccard(sig1, sig2):
    return sum(x == y for x, y in zip(sig1, sig2)) / len(sig1)

This pure-Python version is clear but slow; production code vectorises the hash computation, and the datasketch library provides MinHash(num_perm=128) and MinHashLSH(threshold=0.8, num_perm=128) with insert and query methods that choose b and r for a target threshold.

The banded index

The index stores, for each band, a hash table from the band's r values to the item ids that share them. A query computes its signature, looks up each band and unions the results. Candidates are only candidates: verify each by computing the exact or estimated similarity, because the S-curve admits some pairs below the threshold and the verification step is what keeps precision high.

from collections import defaultdict

class MinHashLSH:
    def __init__(self, bands, rows):
        self.b, self.r = bands, rows
        self.tables = [defaultdict(list) for _ in range(bands)]
        self.sigs = {}

    def _keys(self, sig):
        return [hash(tuple(sig[i*self.r:(i+1)*self.r])) for i in range(self.b)]

    def insert(self, key, sig):
        self.sigs[key] = sig
        for t, k in zip(self.tables, self._keys(sig)):
            t[k].append(key)

    def query(self, sig, min_sim):
        cands = {x for t, k in zip(self.tables, self._keys(sig)) for x in t.get(k, ())}
        return [x for x in cands if est_jaccard(sig, self.sigs[x]) >= min_sim]

Worked example: deduplicating a training corpus

Suppose you are cleaning a crawl of 50 million web pages before training a language model, and you want to remove pages whose 5-word shingle sets have Jaccard similarity of about 0.8 or more: boilerplate-heavy templates, syndicated articles, mirrors. Exact pairwise comparison is about 1.25e15 pairs. MinHash LSH reduces it to a linear pass plus verification.

1. Shingle each page and compute 128 MinHash values, stored as 64-bit integers: about 1 KB per page, 50 GB for the corpus, which shards cleanly by page.
2. Use 16 bands of 8 rows. The threshold is about 0.71; a pair at 0.8 becomes a candidate with probability 0.947, a pair at 0.5 with probability 0.061.
3. For each band, emit (band index, hash of band values, page id) and group by the first two fields, which is a single shuffle in Spark or a sort on disk. Buckets with more than one page yield candidate pairs.
4. Verify each candidate pair by estimated Jaccard from the full signatures, then build a graph of confirmed duplicates and keep one page per connected component, preferring the longest or earliest.

Two practical problems appear at this scale. Giant buckets, produced by pages that are almost entirely navigation boilerplate, generate quadratic numbers of pairs; cap bucket size and treat oversized buckets as duplicate clusters directly. And connected components can chain: A resembles B and B resembles C, yet A and C are different. Use a stricter verification threshold or cluster with a centre rather than taking components blindly. Rolling hashes, as in Rabin-Karp, make shingle hashing fast, and a HyperLogLog sketch estimates how many distinct shingles a shard contains before you size its tables.

Cosine and Euclidean families

For vectors compared by angle, Charikar's random-hyperplane hashing, the basis of SimHash, is the standard family. Draw a random vector w with Gaussian entries and set h(x) to 1 if w.x is non-negative, else 0. Two vectors at angle theta fall on different sides of a random hyperplane with probability theta/pi, so they collide with probability 1 - theta/pi. Concatenating k such bits gives a k-bit sketch whose Hamming distance estimates the angle, which is also a compact binary code: 256 bits stand in for a 768-float embedding at 1/96 of the memory.

import numpy as np

def hyperplane_codes(X, n_bits, seed=0):
    W = np.random.default_rng(seed).standard_normal((X.shape[1], n_bits))
    return (X @ W >= 0)                       # boolean codes, shape (n, n_bits)

def angle_estimate(code_a, code_b):
    return np.pi * np.mean(code_a != code_b)  # radians

For Euclidean distance, the p-stable scheme of Datar, Immorlica, Indyk and Mirrokni projects onto a random Gaussian direction and quantises: h(x) = floor((a.x + b) / w), with b uniform in [0, w). Nearby points tend to land in the same interval. The bucket width w trades collision probability for near points against far points and must be tuned to the data's distance scale, which is the most common reason Euclidean LSH under-performs out of the box.

Multi-probe LSH and the memory problem

The weakness of classic LSH is memory. High recall needs many tables, and every table stores every item id, so an index with 100 tables is 100 times the id storage before you store any vectors. Multi-probe LSH, from Lv and colleagues in 2007, reduces the table count by probing several buckets per table: not just the query's own bucket but the neighbouring buckets most likely to hold near points, ordered by how close the query's projection was to a boundary. With E2LSH-style hashes, those are the buckets one quantisation step away on the coordinates where the query sat nearest the edge. The published experiments reported similar recall with an order of magnitude fewer tables, trading memory for query-time probes.

LSH versus graph indexes

For dense vector search, graph indexes such as HNSW and disk-resident designs like DiskANN usually beat LSH on recall per unit of query time, which is why vector databases default to them. LSH keeps a clear place for specific jobs.

Failure modes

How LSH deployments go wrong:

• Threshold set by default. Libraries pick b and r for a threshold you supply; supplying 0.5 because it looks neutral silently decides what counts as a duplicate.
• No verification step. Treating every bucket mate as a match lets the lower tail of the S-curve through.
• Shingle size wrong. Character 3-grams make every English page look similar; 20-word shingles make near-copies with small edits look different. Five-word shingles are a common starting point for prose; check on labelled pairs.
• Skewed buckets. A few huge buckets dominate run time and memory. Cap them and handle them separately.
• Seeds not fixed. Signatures computed with different hash seeds are incomparable, so an index built last month cannot answer queries hashed today. Store the seeds with the index.
• Recall never measured. Sample pairs, compute exact similarity, and count how many true near pairs the index found.

Operating an LSH index

Operate an LSH index like any approximate structure: measure it. Keep a labelled sample of pairs across the similarity range, compute the empirical candidate rate per similarity bin, and compare it with the theoretical S-curve; a mismatch usually means a hashing bug or non-independent hash functions. Track candidate count per query and bucket-size percentiles, since both drive cost. When the data distribution shifts, for example a new language enters a corpus, re-check recall rather than assuming the threshold still means what it did. For embedding search, compare against a graph index on your own data before committing; the navigable small-world article explains the alternative.

What to do next

1. Implement MinHash and the banded index above, then check that the estimated Jaccard of random pairs matches the exact value within the expected error.
2. Plot the empirical candidate probability against similarity for your chosen b and r and confirm it follows 1 - (1 - s^r)^b.
3. Pick the similarity that defines a duplicate in your data by labelling 200 pairs, then choose b and r so the threshold sits just below it.
4. Run deduplication on a sample, measure recall against exact comparison and inspect the largest buckets.
5. For embedding search, benchmark random-hyperplane LSH against HNSW at equal memory and pick on measured recall and latency.
6. Store hash seeds, b, r and shingle settings alongside every index you build.