Fuzzy Matching

The foundational algorithms that quantify string dissimilarity by counting the minimum number of single-character operations required to transform one string into another.

• Levenshtein Distance: Counts insertions, deletions, and substitutions. Ideal for general typographical errors.
• Damerau-Levenshtein Distance: Extends Levenshtein by adding transposition of two adjacent characters, catching common human spelling mistakes like 'teh' for 'the'.
• Jaro-Winkler Similarity: A variant that gives a higher score to strings that match from the beginning, optimized for short strings like personal names and addresses.

Algorithms that index words by their pronunciation rather than their spelling, enabling the matching of homophones that are often confused during data entry.

• Soundex: The original phonetic algorithm that maps names to a letter followed by three digits, grouping similar-sounding consonants.
• Metaphone & Double Metaphone: More sophisticated successors that account for English spelling rules and non-English origins, producing more accurate phonetic keys.
• NYSIIS: The New York State Identification and Intelligence System, which maps phonemes to a standardized code, preserving relative vowel placement more accurately than Soundex.

Methods that decompose strings into sets of tokens (words or n-grams) and compare the overlap between sets, making them robust to word reordering and partial matches.

• Jaccard Similarity: Calculates the ratio of the intersection to the union of two token sets. Effective for comparing multi-word fields like company names.
• Cosine Similarity with TF-IDF: Converts strings into weighted vectors where rare tokens receive higher importance, then measures the cosine of the angle between vectors to determine semantic similarity.
• Q-Gram (N-Gram) Matching: Breaks strings into overlapping substrings of length q, then compares the sets. Highly resilient to character-level noise and transpositions.

A statistical framework that moves beyond deterministic thresholds by calculating the likelihood that a record pair is a true match based on observed agreement patterns.

• Fellegi-Sunter Model: The formal foundation that assigns a match weight to each field comparison. Agreement on a rare value (e.g., Social Security Number) contributes a high positive weight, while agreement on a common value (e.g., 'John') contributes less.
• Composite Score Calculation: Individual field weights are summed to produce a total composite match score. This score is then compared against two thresholds: an upper threshold for automatic linking and a lower threshold for automatic rejection.
• Clerical Review Zone: Record pairs with scores falling between the two thresholds are flagged for manual human review, ensuring high precision on edge cases.

A critical performance optimization that avoids the computationally prohibitive task of comparing every record against every other record (an O(n²) problem).

• Blocking Keys: The dataset is partitioned into mutually exclusive blocks using a deterministic key, such as the first three characters of a last name or a phonetic code. Comparisons are only performed within each block.
• Sorted Neighborhood Method: Records are sorted by a blocking key, and a sliding window of fixed size moves through the sorted list, comparing only records within the current window.
• Canopy Clustering: A cheap, approximate distance metric is used to create overlapping clusters (canopies). Expensive, precise distance calculations are then restricted to record pairs that fall within the same canopy.

The ability to assign different importance levels to specific data fields, reflecting the real-world diagnostic power of each attribute for identity resolution.

• High-Weight Fields: Unique identifiers like Social Security Number or Passport Number receive the highest agreement weights, as a match is a strong indicator of a true identity link.
• Medium-Weight Fields: Semi-stable attributes like Date of Birth and Phone Number receive moderate weights, as they are strong signals but can change or be shared.
• Low-Weight Fields: Generic attributes like Gender or City receive low weights, as agreement is common across many distinct individuals and provides minimal discriminatory power.
• Mismatch Penalties: The system also applies negative weights (penalties) for disagreements on high-confidence fields, rapidly decreasing the composite score for conflicting core identifiers.

The foundational edit distance metric that quantifies the minimum number of single-character operations—insertions, deletions, or substitutions—required to transform one string into another.

• Mechanism: Dynamic programming matrix computes the cost of alignment.
• Example: Transforming 'kitten' to 'sitting' requires 3 edits (substitute 'k' for 's', substitute 'e' for 'i', insert 'g').
• Application: Detecting typographical errors in names and addresses during identity resolution.

A string edit distance algorithm optimized for short strings like personal names. It gives higher scores to strings that match from the beginning (prefix scale), making it ideal for detecting transposed characters and minor misspellings.

• Range: Normalized score between 0 (no match) and 1 (exact match).
• Winkler Modification: Boosts scores for strings sharing a common prefix up to 4 characters.
• Example: 'Johnathan' vs 'Jonathan' receives a high similarity score due to matching characters and transposition tolerance.

A phonetic algorithm that indexes names by their English pronunciation, converting homophones to identical alphanumeric codes. It enables fuzzy matching despite drastic spelling variations.

• Encoding Rule: Retains the first letter, then maps subsequent consonants to digits (e.g., B/F/P/V → 1), ignoring vowels.
• Example: 'Smith' and 'Smythe' both encode to S530.
• Limitation: Designed for Anglo-Saxon surnames; variants like Metaphone and Double Metaphone improve cross-linguistic accuracy.

A numerical statistic that converts unstructured text into a vector space model by weighting terms based on their frequency in a document and their rarity across the corpus.

• Term Frequency (TF): How often a term appears in a specific record.
• Inverse Document Frequency (IDF): Diminishes the weight of common terms (e.g., 'Inc.', 'LLC') that appear across many records.
• Application: Transforms business names and addresses into weighted vectors for cosine similarity calculations, enabling fuzzy matching at scale.

A metric measuring the cosine of the angle between two non-zero vectors in a multi-dimensional space. It quantifies semantic similarity independent of vector magnitude.

• Range: -1 (opposite) to 1 (identical), with 0 indicating orthogonality.
• Formula: Dot product divided by the product of vector magnitudes.
• Example: The TF-IDF vectors for '123 Main St' and '123 Main Street' will have a cosine similarity approaching 1.0, indicating near-identity despite formatting differences.

A statistical framework formalized by the Fellegi-Sunter model that uses likelihood ratios to calculate match probabilities between record pairs without deterministic keys.

• Agreement Weights: Assigns positive weight to matching fields (e.g., same date of birth) and negative weight to disagreeing fields.
• Decision Rule: Classifies pairs as matches, non-matches, or clerical review based on composite score thresholds.
• Advantage: Handles missing data and partial agreement gracefully, making it superior to deterministic rules for noisy real-world identity data.