Record Linkage, Similarity & Data Fusion

01 · Problem

Record linkage & entity resolution

Schema reconciliation lined up the structures. But the same real-world object — a person, a product — is still recorded with different values in different sources. Finding those matches is record linkage (a.k.a. entity resolution); reconciling what they disagree on is data fusion.

Whatever the data model, we must recognise when two records hold the same information — and, crucially, we can do this field by field rather than on the whole tuple as one blob. Compare Tanca | Letizia | DEIS | Lonardo with Tanca | Letizia | DEIB | Leonardo: split into fields, we can use the knowledge that Leonardo is a Politecnico campus to see that Lonardo is a typo of it and DEIS a typo of DEIB. Glue the tuple into one string and that structured knowledge is lost.

The mismatches record linkage must survive are everyday ones: typing errors (Givanni vs Giovanni), different conventions (Sept 20th vs 20/9), nicknames (Giuseppe vs Beppe), inversions (Giovanni Rossi vs Rossi, Giovanni), and abbreviations (Politecnico di Milano vs PoliMI).

02 · Method

String similarity measures

Given two sets of strings, find all pairs that refer to the same entity — each such pair is a match. The tool is a similarity measure $s(x,y) \in [0,1]$ with $s(x,y) = 1 \iff x = y$; the closer to 0, the less similar. We declare a match when

$s(x,y) \ge t, \qquad 0 \le t \le 1.$

(Using a distance instead changes nothing: lower similarity means higher distance.) The measures come in families — sequence-based (edit distance, Needleman-Wunsch, affine gap, Smith-Waterman, Jaro, Jaro-Winkler), set-based (overlap, Jaccard, TF/IDF), hybrid (generalized Jaccard, soft TF/IDF, Monge-Elkan), and phonetic (Soundex). Three matter most here.

The dynamic-programming table behind $d(a,b)$ is worth seeing once. It is seeded with a near-duplicate name of exactly the kind linkage has to score — one substitution and one insertion, so $d = 2$ — and the highlighted path is the alignment that achieves it. Divide by the longer length to get the similarity $s(a,b)$ above, then compare against your threshold:

03 · Method

Record matching & data fusion

A string measure compares fields; record matching decides whether two whole tuples are the same entity. Three approaches, plus one indispensable optimisation:

All three still end at the same place: a score, and a decision about where to cut it. That decision is harder than $s(x,y) \ge t$ makes it look — set the cut anywhere and some of these pairs come out wrong:

Data fusion

Once two records are known to be the same entity, their fields may still disagree — which salary is right? Inconsistency can arise because a source is simply wrong, or because each source holds a correct but partial view (two workplaces, where the true salary is the sum; an author list that is incomplete; a middle name given only as an initial). A resolution function produces the reconciled value — often a function of the originals such as $\text{value}_1 + \text{value}_2$ or $0.5\,\text{value}_1 + 0.5\,\text{value}_2$.