Gen AI

Locality-Sensitive Hashing (LSH)

LSH uses special hash functions that intentionally cause collisions for similar items, allowing you to find nearest neighbors without checking every pair.

Standard hashing avoids collisions entirely, but LSH uses random hyperplanes to ensure similar vectors collide into the same bucket.

Why Does This Exist?

In traditional computer science, a good hashing algorithm (like SHA-256 or MD5) is designed to avoid collisions. If you change a single byte in a file, the resulting hash changes completely. This avalanche effect is crucial for cryptography and data integrity, but it makes traditional hashing useless for finding similar items.

When you have millions of high-dimensional vectors (or documents, or images) and want to find ones that are close to each other, you cannot use an exact dictionary lookup, and comparing every item to every other item takes $O(N^2)$ time.

Locality-Sensitive Hashing (LSH) flips the goal of hashing upside down. It uses specialized hash functions that intentionally maximize collisions for similar inputs. If two vectors are close together in high-dimensional space, an LSH algorithm guarantees they will likely produce the exact same hash signature. This allows you to group similar items into the same "buckets," reducing nearest-neighbor search from an exhaustive scan to a simple hash-table lookup.

Think of It Like This

Sorting people by height and hair color

Imagine you are trying to find people who look similar in a crowd of 100,000 people. Comparing everyone to everyone else would take forever.

Instead, you use a set of coarse filters (your "hash functions"):

Filter 1: "Are they taller than 5'9?" (Yes/No)
Filter 2: "Do they have dark hair?" (Yes/No)
Filter 3: "Are they wearing glasses?" (Yes/No)

You assign every person a 3-bit code based on their answers, like 1-0-1. Then, you send everyone with the code 1-0-1 to Room A, and everyone with 0-1-0 to Room B.

When you need to find someone who looks like a specific suspect, you answer the three questions for the suspect (yielding 1-0-1) and walk straight to Room A. You only compare the suspect to the people in Room A, completely ignoring the rest of the crowd. Because similar people were assigned the same "hash," you found your matches in a fraction of the time.

How It Actually Works

Random Projection (Hyperplanes)

One of the most common LSH families used for cosine similarity (angular distance) is Random Projection. Imagine a 2D plane with various data points scattered across it. If you draw a random line (a hyperplane) through the origin, it splits the space in two. Every point on one side of the line gets a 1, and every point on the other side gets a 0.

If two points are very close together, it is highly unlikely that a random line will pass exactly between them. Therefore, they will probably both receive a 1 or both receive a 0. If two points are on opposite sides of the plane, they will almost certainly be separated by the random line.

To build an LSH index:

Generate k random hyperplanes in your high-dimensional space.
For each vector in your dataset, determine which side of each hyperplane it falls on by taking the dot product. If the dot product is positive, append a 1; if negative, append a 0.
This creates a k-bit binary hash signature for every vector.
Place vectors with identical signatures into the same hash bucket.

Multi-Probe and Multiple Tables

A single hash table with a long signature (e.g., $k=10$ ) creates very specific buckets. This means high precision, but terrible recall—if a point is right on the boundary of a hyperplane, it might end up in a different bucket than its nearest neighbor just because of bad luck.

To solve this, LSH systems use two strategies:

Multiple Hash Tables (L): Generate completely different sets of random hyperplanes to create $L$ independent hash tables. If two similar points miss each other in Table 1, they will likely collide in Table 2 or Table 3.
Multi-Probe LSH: Instead of just checking the exact matching bucket, flip one or two bits of the query's hash signature and check those adjacent buckets as well, catching points that were near the hyperplane boundaries.

Other LSH Families

Random projection is for cosine similarity. If you are comparing sets (like bags-of-words or n-grams for document deduplication), you use a different LSH algorithm called MinHash. For Euclidean distance (L2), you use E2LSH (Exact Euclidean LSH). The underlying principle is always the same: map the high-dimensional data to a lower-dimensional hash where similarity is preserved as collision probability.

Show Me the Code

This is a simplified, purely Python implementation of Random Projection LSH to demonstrate how hyperplanes generate bit signatures.

1import numpy as np2
3# Generate random vectors4dim = 1285num_vectors = 10006data = np.random.randn(num_vectors, dim)7query = np.random.randn(dim)8
9# LSH Parameters10num_bits = 8  # This means 8 random hyperplanes11
12# Generate random hyperplanes (a matrix of shape [dim, num_bits])13# Each column is a normal vector defining a hyperplane14np.random.seed(42)15hyperplanes = np.random.randn(dim, num_bits)16
17def generate_hash(vector):18    # The dot product determines which side of the hyperplane the vector is on19    dot_products = np.dot(vector, hyperplanes)20    # Convert positive values to 1 and negative to 021    bits = (dot_products >= 0).astype(int)22    # Convert the binary array to a single integer hash23    # e.g., [1, 0, 1] -> 524    return sum([bit * (2 ** i) for i, bit in enumerate(bits)])25
26# Build the hash table27hash_table = {}28for i, vector in enumerate(data):29    h = generate_hash(vector)30    if h not in hash_table:31        hash_table[h] = []32    hash_table[h].append(i)33
34# Search35query_hash = generate_hash(query)36candidates = hash_table.get(query_hash, [])37
38print(f"Query mapped to bucket {query_hash}.")39print(f"Found {len(candidates)} candidates instead of searching all {num_vectors}.")40# -> Query mapped to bucket 153.41# -> Found 7 candidates instead of searching all 1000.

Watch Out For

The curse of hyperparameter tuning

LSH requires carefully tuning $k$ (number of bits per hash) and $L$ (number of hash tables). If $k$ is too small, your buckets are too large, and you end up doing an expensive brute-force search inside the bucket. If $k$ is too large, your buckets are empty, and your recall drops to zero. If you compensate by increasing $L$ , your memory consumption skyrockets. Tuning these requires empirical testing on your specific data distribution.

The Quick Version

Standard hashes (like SHA-256) avoid collisions; LSH intentionally forces collisions for similar inputs.
By assigning similar vectors to the same hash bucket, LSH turns nearest-neighbor search into an $O(1)$ hash-table lookup.
For dense vectors, LSH uses random hyperplanes to slice the space, generating a binary signature based on which side of the lines a vector falls.
To maintain high recall, real systems use multiple hash tables or multi-probe techniques to catch neighbors separated by bad boundary cuts.