Locality-Sensitive Hashing (LSH)

Unlike traditional cryptographic hashing where collisions are avoided, LSH maximizes the probability of collision for vectors that are close in the input space. A family of hash functions H is called (R, cR, P1, P2)-sensitive if for any two points p and q:

• If distance(p, q) ≤ R, then Pr[h(p) = h(q)] ≥ P1
• If distance(p, q) ≥ cR, then Pr[h(p) = h(q)] ≤ P2 This creates a locality-preserving mapping where similar items fall into the same bucket with high probability, enabling sub-linear search by only examining colliding items.

A single LSH function has limited discriminative power. To achieve practical precision and recall, LSH uses amplification through two Boolean compositions:

• AND-construction (banding): Concatenate k independent hash functions into a single hash key. This sharpens the gap between P1 and P2, reducing false positives but also lowering collision probability.
• OR-construction (multiple tables): Build L independent hash tables. A candidate is any vector that collides in at least one table. This boosts recall by providing multiple collision opportunities. The AND-then-OR scheme (k hash functions per table, L tables) provides the classic tunable tradeoff between precision and recall.

LSH requires a hash family specifically designed for the target distance metric:

• Cosine Similarity / Angular Distance: Use random hyperplane LSH (SimHash). A random vector r defines a hyperplane; the hash bit is the sign of the dot product with r. The probability of collision is 1 - (θ/π), where θ is the angle between vectors.
• Euclidean Distance (L2): Use p-stable distributions (e.g., Gaussian). Project onto a random line and quantize into buckets of width w. Collision probability decreases with distance.
• Jaccard Similarity: Use MinHash. Apply a random permutation to the set elements; the minimum element under that permutation is the hash value. Collision probability equals the Jaccard index.
• Maximum Inner Product Search (MIPS): Requires asymmetric transformations like Simple-LSH or Range-LSH to convert inner product into a metric distance before hashing.

LSH querying follows a two-phase pipeline:

1. Bucket Retrieval: Hash the query vector using the same k × L functions. Retrieve all vectors from the matching buckets across all L hash tables. This candidate set is typically a tiny fraction of the total dataset.
2. Reranking: Compute the exact distance between the query and each candidate vector. Sort by true distance and return the top-K. The candidate set size is the critical runtime factor. Too few candidates (high k, low L) hurts recall; too many (low k, high L) approaches brute-force cost. Parameter tuning is data-dependent.

Strengths:

• Theoretically grounded: Provides probabilistic guarantees on recall given parameter choices.
• Data-agnostic: No training phase required; hash functions are randomly generated independent of data distribution.
• Incremental updates: Inserting new vectors requires only hashing and appending to buckets; no global index rebuild.
• Distributable: Hash tables naturally partition across machines by bucket ID.

Limitations:

• Memory overhead: Storing L complete hash tables multiplies storage requirements.
• Curse of dimensionality: As dimensionality grows, the gap between P1 and P2 shrinks, requiring exponentially more tables to maintain recall.
• Parameter sensitivity: Choosing k and L requires careful tuning; poor choices lead to either missed neighbors or excessive candidate sets.
• Outperformed by graph methods: On many real-world benchmarks, HNSW and similar graph-based indices achieve better recall-speed tradeoffs.

While pure LSH has been largely superseded by graph-based indices (HNSW) and clustering methods (IVF) in modern vector databases, its principles remain influential:

• FAISS includes IndexLSH for cosine similarity using random rotation and scalar quantization.
• Annoy (Spotify) uses random projections to build a forest of binary trees, conceptually similar to LSH's random hyperplane approach.
• Datasketch libraries use MinHash LSH for large-scale document deduplication and near-duplicate detection.
• Hybrid systems sometimes use LSH as a coarse filter before applying a more expensive graph search, combining the data-agnostic nature of LSH with the precision of graph traversal. LSH remains valuable for streaming data, decentralized settings, and applications where index build time must be near-zero.