LSH: Locality Sensitive Hashing

A normal hash spreads inputs uniformly — one bit flips and the hash is unrecognizable. A locality-sensitive hash does the opposite on purpose: it sends similar inputs to the same bucket with high probability. That single property turns nearest-neighbor search into a hash-table lookup, and it comes with a guarantee no other ANN method has.

Interactive LSH Visualization

The explorer is real: it hashes genuine GloVe vectors with random hyperplanes and plots the measured collision rate against cosine similarity — overlaid with the theory line and the amplification curve you tune. Below it, a live index shows which words actually share a bucket.

The LSH property

For the cosine version, SimHash, a hash function is a single random hyperplane: the bit is which side of it the vector falls on. Two vectors get the same bit exactly when the hyperplane does not separate them — which happens with probability proportional to the angle between them:

So collision probability is a (monotone) function of similarity — the property the whole method rests on. In the explorer, every dot is a real word pair, and they sit right on this line.

def simhash(X, planes):              # planes: (b, d) random Gaussian rows
    return (X @ planes.T >= 0)       # each row → a b-bit signature

Other families hash other similarities the same way — MinHash for Jaccard overlap, p-stable projections for Euclidean distance:

Amplification: AND + OR

A single bit is a weak signal — even dissimilar vectors collide ~half the time. Amplification sharpens it. Require all b bits of a band to match (logical AND) and the collision rate becomes P^b — steep, but it now misses some true neighbors. Repeat with L independent tables and accept a match in any (logical OR):

This is the S-curve in the explorer. Tuning b and L slides the threshold — the steep part — to whatever similarity you want to call "a match", with near-zero collisions below it.

def build(X, b, L):
    tables = []
    for _ in range(L):                       # L hash tables (the OR)
        planes = np.random.randn(b, X.shape[1])   # b hyperplanes (the AND)
        idx = defaultdict(list)
        for i, sig in enumerate(simhash(X, planes)):
            idx[sig.tobytes()].append(i)      # bucket by full b-bit code
        tables.append((planes, idx))
    return tables

def query(q, tables):
    cand = set()
    for planes, idx in tables:               # union of matching buckets
        cand |= set(idx.get(simhash(q[None], planes)[0].tobytes(), []))
    return cand                              # then re-rank exactly

When to reach for LSH

The honest summary: on a static in-memory corpus a graph index recalls more for less work — you can see it in the ANN comparison. LSH earns its place where its guarantee matters: constantly changing data, adversarial inputs, or near-duplicate detection at web scale, where MinHash over shingles is still the standard.

References

• Charikar "Similarity Estimation Techniques from Rounding Algorithms" (SimHash)
• Indyk & Motwani "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality"
• Broder "On the Resemblance and Containment of Documents" (MinHash)

Related concepts