Record Linkage

The computational process of identifying, linking, and merging disparate records that refer to the same real-world entity across different data sources. Unlike basic record linkage, entity resolution encompasses the full pipeline of deduplication, canonicalization, and identity clustering to create a single golden record. Key techniques include:

• Pairwise similarity scoring on attributes like name, address, and date of birth
• Transitive closure to resolve chains of matches (A matches B, B matches C, therefore A matches C)
• Graph-based community detection to partition records into distinct identity clusters

The foundational probabilistic framework for record linkage, formalized by Ivan Fellegi and Alan Sunter in 1969. The model classifies record pairs into matches, non-matches, or potential matches by computing likelihood ratios based on agreement patterns across multiple fields. Core components include:

• M-probability: The probability that a field agrees given the pair is a true match
• U-probability: The probability that a field agrees by random chance
• Composite weight: Sum of agreement and disagreement weights across all fields, used to rank pairs for clerical review or automatic decision thresholds

A performance optimization technique that partitions large datasets into mutually exclusive blocks using a common attribute, drastically reducing the number of record pair comparisons from O(n²) to O(n). Without blocking, linking two datasets of 1 million records each would require 1 trillion comparisons. Common blocking strategies include:

• Phonetic blocking: Using Soundex or Metaphone codes on surnames
• N-gram indexing: Creating inverted indices on character trigrams for fuzzy matching
• Sorted neighborhood: Sorting records by a blocking key and sliding a fixed-size window to compare only nearby records

A string comparison technique that calculates the probability of two text strings being a match, tolerating typographical errors, abbreviations, transpositions, and formatting inconsistencies. Essential for linking records where names like 'Jon Smith' and 'John Smyth' refer to the same individual. Core algorithms include:

• Levenshtein Distance: Minimum single-character edits (insertions, deletions, substitutions) required to transform one string into another
• Jaro-Winkler Similarity: Optimized for short strings like personal names, giving higher scores when strings match from the beginning
• Cosine Similarity with TF-IDF: Converts strings into weighted token vectors for semantic comparison beyond character-level edits

A cryptographic protocol that enables the matching of records across disparate databases without revealing the plaintext personally identifiable information (PII) to any party. Critical for inter-bank fraud consortia and healthcare research where data sharing is legally restricted. Key techniques include:

• Bloom Filter Encoding: Converts identity attributes into irreversible bit arrays using multiple hash functions, enabling secure fuzzy matching via Dice coefficient or Jaccard similarity on the encoded values
• Homomorphic Encryption: Allows computation directly on encrypted data, producing encrypted match results that only the data owner can decrypt
• Secure Multi-Party Computation: Distributes computation across parties so no single entity sees the complete input data

An approach that models records as nodes and their pairwise similarity scores as weighted edges in a graph, then applies community detection or clustering algorithms to resolve entities. This method excels at detecting synthetic identity fraud rings where multiple fabricated identities share subtle, non-obvious connections. Key graph algorithms include:

• Connected Components: Identifies transitive clusters where any path between nodes indicates the same entity
• Louvain Community Detection: Partitions the graph into densely connected communities representing distinct real-world identities
• Link Prediction: Estimates the probability of missing edges between nodes, used to infer hidden synthetic identity relationships that fraudsters attempt to conceal