Locality-Sensitive Hashing (LSH)

The core principle of LSH is that it maximizes collision probability for similar items while minimizing it for dissimilar ones. Unlike cryptographic hashing where a single bit change produces an avalanche effect, LSH functions are designed so that the hash collision probability equals a similarity function (e.g., Jaccard or cosine). This allows the algorithm to reduce a high-dimensional similarity search to a simple hash lookup.

LSH achieves sublinear query performance, typically O(n^ρ) where ρ < 1, compared to the O(n) cost of brute-force linear scan. This is accomplished by partitioning the vector space into buckets and only comparing the query against items that fall into the same bucket. For large-scale knowledge graph construction, this enables entity resolution across millions of nodes without exhaustive pairwise comparison.

LSH is an approximate algorithm with formal probabilistic bounds. By tuning two parameters—the number of hash tables (L) and the number of hash functions per table (k)—you can control the trade-off between precision and recall. Increasing L improves recall by creating more chances for true neighbors to collide, while increasing k improves precision by filtering out false positives more aggressively.

Different LSH families are designed for different distance metrics:

• MinHash: Jaccard similarity for sets and documents
• SimHash: Cosine similarity for text and embeddings
• p-stable LSH: Euclidean distance for vector spaces
• Bit sampling: Hamming distance for binary codes This flexibility allows LSH to be applied across diverse data types in knowledge graph pipelines, from textual entity mentions to graph embeddings.

LSH constructs a banding structure to amplify the gap between high-similarity and low-similarity pairs. Multiple hash functions are concatenated with an AND operation to form a single band, increasing precision. Multiple bands are then combined with an OR operation to boost recall. This AND-OR composition creates a sharp sigmoid probability curve, making the algorithm highly discriminative around a tunable similarity threshold.

LSH is inherently embarrassingly parallel. Each hash table operates independently, allowing straightforward distribution across compute clusters. The algorithm also supports streaming ingestion—new items can be hashed and inserted into existing tables without recomputing the entire index. This property is critical for real-time knowledge graph construction where new entities and relationships arrive continuously.

A distance metric frequently used in LSH for binary hash codes. It counts the number of positions where two equal-length binary strings differ. Why it matters for LSH:

• Extremely fast to compute via XOR and popcount operations
• Naturally suited for random projection and bit-sampling hash families
• Enables efficient bucket lookup using bitwise operations
• Common in image perceptual hashing and document fingerprinting

A core dimensionality reduction technique underlying many LSH families. It projects high-dimensional vectors onto random hyperplanes, preserving pairwise distances with high probability according to the Johnson-Lindenstrauss lemma. The sign of each projection determines a hash bit. This method is particularly effective for cosine similarity and angular distance measures in dense embedding spaces.

An LSH family specifically designed for Jaccard similarity between sets. It estimates set similarity by comparing the minimum hash values across multiple hash functions. Primary applications:

• Near-duplicate document detection at web scale
• Plagiarism detection and content deduplication
• Collaborative filtering for recommendation engines
• Originally popularized by the AltaVista search engine for finding duplicate web pages

A competing ANN technique that partitions the vector space into clusters represented by centroids. Unlike LSH's hash-based bucketing, vector quantization uses codebook learning to minimize reconstruction error. Product Quantization (PQ) decomposes vectors into sub-vectors for efficient storage and asymmetric distance computation, often achieving better recall than LSH at the cost of higher memory requirements.

A graph-based ANN algorithm that constructs a multi-layer proximity graph. It often outperforms LSH in recall-speed tradeoffs for in-memory indexes. Key differences from LSH:

• Greedy traversal through graph edges rather than hash bucket lookup
• No theoretical collision probability guarantees
• Higher memory footprint due to graph structure storage
• Dominant algorithm in modern vector databases like Weaviate and Qdrant