Locality-Sensitive Hashing (LSH)

Unlike cryptographic hashing, LSH provides a probabilistic guarantee of collision. The core property is defined by a distance metric (d), a similarity threshold (R), and probabilities (p1) and (p2), where (p1 > p2). A hash family (H) is ((R, cR, p1, p2))-sensitive if:

• If (d(x, y) \leq R), then (Pr[h(x) = h(y)] \geq p1) (similar items collide with high probability).
• If (d(x, y) \geq cR), then (Pr[h(x) = h(y)] \leq p2) (dissimilar items collide with low probability). This formalizes the approximate nature of the search, trading perfect recall for massive speedups.

Single hash functions provide weak separation. LSH amplifies the gap between (p1) and (p2) using AND and OR constructions.

• AND Construction (Concatenation): Combine (r) hash functions; a collision requires all (r) to match. This reduces (p1) and (p2), making the hash more selective and shrinking bucket sizes.
• OR Construction (Multiple Hash Tables): Create (L) independent hash tables, each with its own AND-concatenated hash function. An item is a candidate if it collides in any table. This increases the overall (p1), boosting recall. Tuning (r) and (L) controls the recall vs. precision trade-off and query time.

LSH requires hash functions tailored to the target distance metric. Key families include:

• Cosine Similarity (Random Projections): For vectors on a unit sphere, hash bit (h_i(x) = \text{sign}(w_i \cdot x)), where (w_i) is a random Gaussian vector. This implements SimHash.
• Euclidean Distance (L2) - p-stable distributions: Uses E3F2LSH or p-stable LSH. Hashes are computed as (h_{a,b}(v) = \left\lfloor \frac{a \cdot v + b}{w} \right\rfloor), where (a) is drawn from a p-stable distribution (e.g., Gaussian for L2) and (w) is a bucket width.
• Jaccard Similarity (MinHash): For sets, the hash function is the minimum element after a random permutation. The probability of hash equality equals the Jaccard index.

The primary performance benefit of LSH is achieving sub-linear query time relative to dataset size (N). An exhaustive (linear) scan is (O(Nd)) for (d)-dimensional vectors. LSH reduces this to roughly (O(L \cdot (r + \text{bucket size}))). The expected bucket size is controlled by the AND construction ((r)). In practice, for large (N), query time can be orders of magnitude faster than a linear scan, enabling real-time similarity search on billion-scale datasets, albeit with an approximate result.

LSH does not have a single "correct" result. Performance is controlled by hyperparameters that create a tunable recall-precision curve:

• Number of hash functions per table ((r)): Increasing (r) makes buckets sparser, raising precision but lowering recall.
• Number of hash tables ((L)): Increasing (L) provides more chances for collision, raising recall but increasing memory and query time.
• Bucket width ((w)) for Euclidean LSH: A larger (w) puts more points in each bucket, increasing recall but reducing precision. Engineers tune these parameters based on application SLOs for recall@K and query latency.

The efficiency of LSH comes with structural overhead:

• Memory for Hash Tables: Maintaining (L) hash tables requires storing (L \times N) hash keys and pointers, leading to significant memory consumption. This is the cost of the OR construction.
• Indexing Time: Precomputing hash values for all dataset points during index build is typically (O(NLrd)). While often acceptable as a one-time cost, it is non-trivial for streaming data.
• Comparison to Graph Indexes: Unlike HNSW, LSH does not store a graph structure. Its memory overhead is more predictable (scales with (L) and (N)) but can be higher for the same recall level, especially in high dimensions.

Approximate Nearest Neighbor (ANN) Search is a class of algorithms designed to find vectors in a database that are most similar to a query vector, trading off perfect accuracy for significantly faster query times compared to an exhaustive linear scan. LSH is a foundational ANN technique.

• Core Trade-off: Enables sub-linear or logarithmic query time by accepting that some true nearest neighbors may be missed.
• Use Case: Essential for real-time semantic search, recommendation systems, and retrieval-augmented generation (RAG) where querying billions of vectors is required.
• Algorithm Families: Includes hashing-based methods (LSH), graph-based methods (HNSW), and tree-based methods.

Hierarchical Navigable Small World (HNSW) is a graph-based algorithm for approximate nearest neighbor search that constructs a multi-layered graph. It is a contemporary, highly performant alternative to LSH for many high-recall use cases.

• Mechanism: Creates a hierarchy of graphs where long-range connections on higher layers enable fast, logarithmic-time search via greedy traversal.
• Comparison to LSH: Typically offers higher recall and lower latency for a given memory footprint but can have higher index construction time and is less naturally suited for certain filtering scenarios.
• Key Parameters: Controlled by M (maximum connections per node) and efConstruction / efSearch for quality/speed trade-offs.

Recall and Precision are the fundamental evaluation metrics for any approximate search algorithm like LSH, quantifying the trade-off between completeness and accuracy.

• Recall: The fraction of true nearest neighbors (from an exhaustive search) that are successfully retrieved by the ANN system. High recall means missing fewer relevant results.
• Precision: The fraction of retrieved items that are true nearest neighbors. High precision means the returned list contains less irrelevant noise.
• LSH Tuning: Increasing the number of hash tables or hash functions generally improves recall at the cost of higher memory usage and query latency. Recall@K is the standard operational metric.

Product Quantization (PQ) is a lossy compression technique for high-dimensional vectors often used in conjunction with coarse quantizers like IVF. It reduces memory footprint, enabling billion-scale indexes in RAM, a common complement to LSH's retrieval role.

• Mechanism: Splits a vector into subvectors, quantizes each subspace independently using a learned codebook, and represents the vector by a short code of sub-quantizer indices.
• Distance Calculation: Uses Asymmetric Distance Computation (ADC) for accurate distance approximations between a raw query vector and compressed database vectors.
• System Design: In a multi-stage pipeline, LSH can perform fast candidate generation, after which a more precise but expensive PQ-based distance calculation re-ranks the final results.

A Distance Metric is a mathematical function that defines similarity between vectors. The choice of metric dictates the geometry of the search space and the design of the LSH family.

• LSH Family Dependency: An LSH scheme is defined for a specific distance metric (e.g., Euclidean LSH, Cosine LSH).
• Common Metrics:
  • Cosine Similarity: Measures angular similarity; ideal for text embeddings. Corresponding LSH uses random hyperplanes.
  • Euclidean Distance (L2): Measures straight-line distance. Corresponding LSH often uses stable distributions (p-stable LSH).
  • Inner Product: Used for similarity of normalized vectors. Requires specialized LSH constructions.
• Index Selection: The vector database must use an index (like LSH) compatible with the application's chosen distance metric.

Filtered Search is a hybrid query that combines vector similarity search with conditional metadata filters. Integrating LSH with filtering requires careful engineering to maintain performance.

• Challenge: Applying a metadata filter (e.g., date > 2024) before or after the LSH lookup can drastically impact recall.
• Strategies:
  • Pre-Filtering: Apply metadata filters first, then run LSH on the filtered subset. Risk: can eliminate all true nearest neighbors.
  • Post-Filtering: Run LSH first, then filter the results. Risk: may return fewer than K results if the filter is selective.
• Advanced Solutions: Modern vector databases implement single-stage filtered search where the index structure (or query planner) integrates filters during traversal, a complex but critical optimization.