Locality-Sensitive Hashing (LSH)

LSH is fundamentally an approximate algorithm. It trades perfect accuracy for immense speed, providing probabilistic guarantees rather than deterministic results. The core guarantee is that the probability of collision (hashing to the same bucket) is higher for similar items than for dissimilar ones.

• Formal Property: For a distance metric d and similarity threshold R, an LSH family H satisfies: if d(x, y) ≤ R then P[h(x) = h(y)] is high (e.g., p1); if d(x, y) ≥ cR then P[h(x) = h(y)] is low (e.g., p2), where p1 > p2 and c > 1.
• Engineering Implication: This means some truly similar pairs may be missed (false negatives), and some dissimilar pairs may collide (false positives). The parameters k (number of hash functions per band) and L (number of bands) allow tuning this speed/recall trade-off.

LSH's primary advantage is reducing the computational complexity of similarity search from O(N) (comparing a query to every item in a database) to a sub-linear or near-constant time operation on average.

• Mechanism: Instead of a linear scan, the query is hashed to one or more buckets. Only the items within those buckets are considered as candidates for detailed comparison.
• Impact on Blocking: In entity resolution, this transforms an intractable O(N²) pairwise matching problem across millions of records into a manageable process. Candidate pairs are generated only within hash-collision blocks, reducing comparisons by orders of magnitude (e.g., from billions to millions).

An LSH scheme is defined for a specific distance or similarity metric. Different metrics require mathematically distinct hash function families.

• Common LSH Families:
  • Hamming Distance: Uses bit sampling functions.
  • Jaccard Similarity: Uses MinHash (Min-wise independent permutations).
  • Cosine Similarity: Uses SimHash (random hyperplane projections).
  • Euclidean Distance (L2): Uses p-stable distributions (e.g., E2LSH).
• Selection Criteria: The choice of LSH family is dictated by the similarity measure most appropriate for the data (e.g., MinHash for set-based token similarity, SimHash for text embedding cosine similarity).

The performance of a basic LSH function is amplified using a structured AND-OR concatenation of multiple hash functions to sharpen the probability curve.

• AND Construction (k hashes): Concatenate k independent hash functions. Two items hash to the same bucket only if all k functions agree. This reduces false positives (makes collisions stricter).
• OR Construction (L bands): Create L independent hash tables, each with its own AND-composed hash function. Two items are candidate pairs if they collide in any of the L tables. This increases recall (reduces false negatives).
• Tuning: Adjusting k and L moves the system along a precision-recall curve, defined by the S-curve probability function 1 - (1 - p^k)^L.

A key operational feature of LSH is the symmetry between indexing and querying. The same hash functions are applied identically to both database records and incoming queries.

• Indexing Phase: All database items are pre-processed and inserted into L hash tables using their computed hash signatures.
• Query Phase: The query item is hashed with the same L functions, and the corresponding buckets are probed to retrieve candidate neighbors.
• Benefit: This symmetry enables extremely fast online querying, as the computational overhead is primarily in the one-time index build. The query process is a simple hash computation and bucket lookup.

In entity resolution, LSH is predominantly used in the blocking or candidate generation stage to efficiently find record pairs that are potential matches.

• Workflow:
  1. Records are converted into a similarity-space representation (e.g., token sets, text embeddings).
  2. An appropriate LSH family (e.g., MinHash for tokens, SimHash for embeddings) hashes records into blocks.
  3. Only records within the same block are passed to the more expensive, precise matching stage (e.g., a classifier or detailed similarity scorer).
• Scalability: This is critical for deduplication and record linkage on datasets with millions or billions of records, where naive all-pairs comparison is computationally prohibitive.

Blocking is a pre-processing technique in entity resolution that partitions records into candidate groups, or 'blocks', to drastically reduce the number of pairwise comparisons required. Instead of comparing every record to every other record (an O(n²) operation), only records within the same block are compared. Common blocking keys include:

• The first three letters of a surname.
• A geographic area code.
• A hashed value of a normalized attribute. LSH is a sophisticated form of blocking where the 'blocks' are hash buckets, and similarity, not exact key equality, determines bucket placement.

Probabilistic Matching is a statistical approach to entity resolution that calculates the likelihood that two records refer to the same entity. It contrasts with deterministic (rule-based) matching. The core idea is to weigh the agreement or disagreement on each attribute (e.g., name, date of birth, address) based on its discriminative power. A common framework is the Fellegi-Sunter model, which estimates:

• m-probability: The probability that an attribute agrees given the records are a match.
• u-probability: The probability that an attribute agrees given the records are a non-match. These probabilities are combined into a composite match score, with a threshold determining the final link decision. LSH serves as a highly efficient candidate generation step for probabilistic matching systems.

Entity resolution relies on quantitative measures to compare records. LSH families are designed to preserve specific similarity metrics in the hashing process. Key measures include:

• Jaccard Similarity: For sets, it's the size of the intersection divided by the size of the union. MinHash is an LSH family for Jaccard similarity.
• Cosine Similarity: For vectors, it's the cosine of the angle between them. SimHash is a well-known LSH for cosine similarity.
• Hamming Distance: The number of positions at which corresponding symbols differ. Used for bit vectors.
• Levenshtein Distance: The minimum number of single-character edits (insert, delete, substitute) to change one string into another. The choice of similarity metric dictates the appropriate LSH algorithm and the definition of 'locality'.

Deduplication is the specific task of identifying and removing duplicate records that refer to the same entity within a single dataset. It is a core application of entity resolution focused on data hygiene and quality. The process typically involves:

1. Standardization (canonicalization) of data fields.
2. Blocking or LSH to create candidate duplicate pairs.
3. Pairwise comparison using similarity scores or machine learning models.
4. Clustering matched pairs into groups representing the same entity (e.g., finding connected components in a match graph).
5. Survivorship or Golden Record creation to merge the group into one authoritative record. LSH is critical for scaling deduplication to large datasets.

Approximate Nearest Neighbor search is the fundamental computational problem that LSH is designed to solve efficiently. Given a query point in a high-dimensional space (e.g., a text embedding or image feature vector) and a large database of points, ANN search finds points that are approximately the closest to the query, trading perfect accuracy for massive speed and memory gains. LSH achieves this by hashing similar points into the same buckets with high probability. This is directly analogous to entity resolution, where the 'database' is the set of all records, and the 'query' is a new record needing resolution. ANN is the engine behind scalable semantic search, recommendation systems, and clustering.

The performance of an LSH-based entity resolution pipeline is rigorously evaluated using precision and recall, derived from a confusion matrix of record pairs.

• Precision: The fraction of predicted matches that are correct. Precision = True Positives / (True Positives + False Positives). High precision means few false matches.
• Recall: The fraction of all true matches that were successfully retrieved. Recall = True Positives / (True Positives + False Negatives). High recall means few missed matches. LSH involves a trade-off: increasing the number of hash tables or bands generally improves recall (finds more true matches) but can reduce precision (lets in more false candidates). Tuning LSH parameters (k, L) is often an optimization exercise on this precision-recall curve.