Probabilistic Record Linkage

The mathematical foundation of probabilistic record linkage, introduced by Ivan Fellegi and Alan Sunter in 1969. The model formalizes the linkage decision as a statistical classification problem with three possible outcomes:

• Match (M): The record pair represents the same entity
• Non-match (U): The record pair represents different entities
• Possible Match (Clerical Review): The pair falls into an indeterminate region requiring human adjudication

The model establishes optimal decision rules by minimizing the probability of false matches and false non-matches, using likelihood ratios derived from attribute agreement patterns. This framework remains the theoretical backbone of modern entity resolution systems.

Match weights quantify the evidential value of attribute agreement or disagreement between record pairs. The total match weight is the sum of individual attribute weights:

• Agreement weight: log2(m/u), where m is the probability that a matching pair agrees on the attribute, and u is the probability that a non-matching pair agrees by chance
• Disagreement weight: log2((1-m)/(1-u)), representing the penalty when attributes conflict

A positive weight increases the likelihood of a true match; a negative weight decreases it. The logarithmic scale (base 2) means each +1 weight doubles the odds of a match. This additive property allows combining evidence from multiple fields like name, date of birth, and address into a single composite score.

The accuracy of probabilistic linkage depends critically on estimating two conditional probabilities for each matching field:

• M-probability: The likelihood that a field agrees given the records are a true match. This accounts for data entry errors, typos, and legitimate variations. A typical m-probability for surname might be 0.95, reflecting a 5% error rate.
• U-probability: The likelihood that a field agrees by random chance given the records are not a match. For a surname field, this is approximately 1/frequency, making rare names more discriminating.

These parameters can be estimated using the Expectation-Maximization (EM) algorithm on unlabeled data, or derived from training data where true match status is known. Accurate estimation is essential—poor m and u values produce misleading match weights.

Comparing every record pair in large datasets is computationally infeasible—a million-record file would require ~500 billion comparisons. Blocking solves this by partitioning records into mutually exclusive groups using efficient heuristics:

• Traditional blocking: Exact matching on a blocking key like postal code or phonetic encoding (Soundex, Double Metaphone)
• Sorted neighborhood: Sliding a fixed-size window over sorted records to compare only nearby pairs
• Canopy clustering: Using cheap, approximate distance metrics to create overlapping clusters
• Locality-sensitive hashing (LSH): Hashing records so similar items map to the same buckets with high probability

Effective blocking dramatically reduces the comparison space while maintaining high recall, ensuring true matches are not missed due to overly aggressive filtering.

Probabilistic linkage rarely relies on exact field matching. Instead, string comparators quantify partial agreement to handle real-world data quality issues:

• Edit distance (Levenshtein): Minimum character insertions, deletions, or substitutions to transform one string into another
• Jaro-Winkler: Optimized for short strings like names, giving higher scores to strings matching from the beginning
• Jaccard similarity: Measures token overlap, robust to word reordering in addresses
• Phonetic encoding (Soundex, Metaphone): Converts strings to codes representing pronunciation, catching spelling variations
• Numeric comparators: Absolute or relative difference functions for ages, dates, and measurements

These comparators produce similarity scores between 0 and 1, which are then discretized into agreement/disagreement states for weight calculation.

The Fellegi-Sunter model defines two critical thresholds on the composite match weight:

• Upper threshold: Pairs scoring above this are automatically classified as matches
• Lower threshold: Pairs scoring below this are automatically classified as non-matches
• Clerical review zone: Pairs between the thresholds require manual review

Threshold selection involves a fundamental trade-off:

• Lowering thresholds increases sensitivity (recall) but raises the false positive rate, linking records that should remain separate
• Raising thresholds increases specificity (precision) but raises the false negative rate, missing true matches

Optimal thresholds are determined by the relative costs of false positives versus false negatives in the specific application domain. In healthcare, a missed match could mean fragmented patient records; in fraud detection, a false match could trigger an incorrect investigation.

Hospitals and health information exchanges use probabilistic linkage to create unified patient records across disparate EHR systems without a universal national ID. Match weights are calculated on attributes like name, date of birth, address, and phone number.

• Tolerates nicknames (e.g., 'Bill' vs. 'William') via string comparators
• Handles transposed digits in dates using edit distance
• Reduces duplicate medical records by up to 40% in multi-facility systems
• Critical for accurate allergy and medication reconciliation

National statistical agencies apply the Fellegi-Sunter model to link census records with administrative data (tax filings, social security) for population estimation. Blocking on postal code and gender reduces the comparison space before computing agreement weights on first name, surname, and age.

• Enables post-enumeration surveys to measure census coverage error
• Links historical census records for longitudinal demographic studies
• Handles name changes due to marriage or immigration

Financial institutions link customer records against global sanctions lists and politically exposed persons (PEP) databases. The probabilistic framework accounts for transliteration variations of Arabic, Cyrillic, and Mandarin names into Latin script, and partial matches on date of birth.

• Agreement weight on name boosted by phonetic encoding (Soundex, Double Metaphone)
• Disagreement on country of residence carries a high negative weight
• Reduces false positive alerts that overwhelm compliance teams
• Required by FATF Recommendation 10 for customer due diligence

Marketplaces and aggregators merge product listings from thousands of sellers where the same SKU appears with slight variations in title, description, and specifications. Probabilistic linkage uses token-based similarity (Jaccard, TF-IDF cosine) on product attributes.

• 'iPhone 13 Pro 128GB Graphite' vs. 'Apple iPhone 13 Pro (128 GB, Graphite)'
• Blocking on brand and category before pairwise comparison
• Enables unified product reviews and competitive price analysis
• Powers catalog normalization for Google Shopping and Amazon

Platforms like Ancestry.com and FamilySearch link historical records (birth certificates, marriage licenses, census forms) across centuries. The Fellegi-Sunter model handles handwriting OCR errors, name spelling evolution, and approximate dates where only a year is known.

• Agreement on rare surname carries higher weight than common surname
• Partial agreement on birth year within ±2 years receives a positive weight
• Links across record types to construct multi-generational family trees
• Handles millions of pairwise comparisons via blocking on geographic region

Law enforcement agencies link arrest records, court filings, and incarceration data across jurisdictions where no universal offender ID exists. Match weights incorporate fingerprint minutiae similarity, scars/marks/tattoos codes, and biographic attributes.

• High weight on agreement of FBI fingerprint classification
• Disagreement on race or eye color triggers manual review threshold
• Enables rap sheet compilation from fragmented county-level data
• Must satisfy strict audit trail requirements for due process