Locality-Sensitive Hashing (LSH)

LSH operates on a simple geometric principle: hash similar items into the same bucket with high probability, while dissimilar items land in different buckets. Unlike cryptographic hashing where a single bit change avalanches the output, LSH functions are designed to be distance-preserving. For a given distance metric d and threshold R, an LSH family guarantees that points within distance R collide with probability p1, and points beyond distance cR collide with probability p2, where p1 > p2. This probabilistic separation is what enables sub-linear search time.

The choice of hash function family is dictated by the underlying distance metric used in the vector space:

• Jaccard Similarity: MinHash estimates set overlap by hashing elements and keeping the minimum hash value.
• Cosine Similarity: SimHash (or Signed Random Projections) uses a random hyperplane to partition space; the sign of the dot product determines the hash bit.
• Euclidean Distance: Projects points onto random lines and divides the line into segments of fixed width w; the bucket ID is the segment index.
• Hamming Distance: Bit sampling selects a subset of bit positions as the hash value.

A single LSH function is too weak to be useful—it either misses true neighbors or returns too many false positives. Amplification combines multiple functions to tune precision and recall:

• AND-construction (Band): Concatenates k independent hash functions. A match requires all k hashes to collide, drastically reducing false positives but increasing false negatives.
• OR-construction (Table): Uses L independent hash tables. A match requires collision in at least one table, boosting recall at the cost of more false positives. The standard LSH index uses L tables, each with k hashes, to achieve a sharp probability curve around the distance threshold R.

The primary advantage of LSH over brute-force search is its sub-linear query time. For a dataset of size N, a brute-force k-NN search requires O(N) distance computations. A properly tuned LSH index reduces this to approximately O(N^ρ), where ρ < 1 is a function of the approximation factor c. For example, with cosine similarity and an approximation factor of c=2, ρ ≈ 0.5, meaning the query examines roughly the square root of the dataset size. This makes billion-scale similarity search computationally feasible.

While graph-based indices like HNSW often achieve higher recall-per-latency in main memory, LSH remains critical in specific deployment scenarios:

• Encrypted Vector Databases: LSH families based on random projections can be adapted to work with homomorphic encryption or secure multi-party computation, enabling private similarity search where graph traversal would leak access patterns.
• Streaming and Distributed Systems: LSH's stateless hashing allows embarrassingly parallel indexing across clusters without shared global state.
• Disk-Resident Indexes: LSH tables map naturally to key-value stores, enabling efficient secondary-storage lookups without the pointer-chasing overhead of graph traversal.

Tuning an LSH index is a direct three-way trade-off between recall, query speed, and memory footprint:

• Increasing the number of hash tables L improves recall but linearly increases memory and query time.
• Increasing the hash length k reduces false positives but may miss true neighbors, lowering recall.
• The segment width w (for Euclidean LSH) controls granularity: too small fragments true clusters; too large collapses distinct groups. Optimal parameters are typically found through grid search against a ground-truth benchmark, balancing the acceptable recall drop (often 95-99%) against the desired speedup (often 10-100x).

The dense, low-dimensional numerical representation of unstructured data that LSH indexes. Embeddings map semantically similar items—text, images, audio—to nearby points in a continuous vector space.

• Dimensionality: Modern embeddings range from 384 (MiniLM) to 4096+ dimensions.
• Distance Metrics: LSH functions are designed for specific metrics like cosine similarity (random hyperplane LSH) or Euclidean distance (p-stable LSH).
• Semantic Proximity: The quality of LSH bucketing depends entirely on the embedding model's ability to place similar concepts close together.

A specialized data management system that indexes and queries high-dimensional embeddings while maintaining the stored data in an encrypted state. LSH is particularly valuable here because its hash functions can be adapted to operate over encrypted data.

• Searchable Encryption: LSH-based Secure Nearest Neighbor schemes allow a server to find similar encrypted vectors without decryption.
• Threat Model: Protects against a honest-but-curious cloud provider that correctly executes queries but attempts to learn the content of stored embeddings.
• Performance Gap: Encrypted LSH queries are 10-100x slower than plaintext but remain the only practical method for private similarity search at scale.