Matching and Deduplication

8.0 What this chapter gives you#

1. You will be able to explain to somebody with no technical training why two records that clearly describe one person can fail an exact comparison, and why two that pass one can describe two people.
2. You will be able to write down the Fellegi-Sunter decision rule, name its three outcomes, and say what the m probability and the u probability of a field actually measure.
3. You will be able to compute a match weight in bits for a real pair of records, add a prior, convert the total into a probability, and defend the threshold you then apply.
4. You will be able to calculate how many comparisons an unblocked deduplication run needs on a register of any size, and design blocking rules that cut that number without quietly throwing away the matches you were looking for.
5. You will be able to choose between Levenshtein distance, Jaro-Winkler similarity and a phonetic key for a given field, say what each is blind to, encode a name in Soundex by hand, and show cases where Soundex fails on names that are not English.
6. You will be able to explain why a one-to-many biometric search is not a one-to-one check repeated, and compute how good a comparison must be before a search of a billion-record gallery is safe.
7. You will be able to state the difference between a false match rate and a false non-match rate, show how moving one threshold moves both, and say who in an organization should own that number.
8. You will be able to explain why merging two records is easy and unmerging them is close to impossible, and design a record structure that keeps the option open.
9. You will be able to read a matching system’s output and tell the difference between a decision, a score and an assertion.

Every identity system eventually asks the same question about two rows in a table: are these the same person? It sounds like a question with a yes or a no. It is not. It is a question with a probability, and the most expensive mistake in this field is answering it as though it were exact.

The mistake produces two kinds of ghost, and both are costly. The first is the duplicate: one human being, two records, two pension payments, two vaccination histories, two credit files, two chances to be treated as a stranger by an institution that already knows you. The second is the phantom: two human beings collapsed into one record, so that one person’s arrest appears in another person’s background check, one person’s allergy sits in another person’s chart, and one person’s death cancels another person’s benefits. Duplicates cost money. Phantoms cost people.

Neither ghost is a bug in the ordinary sense. Neither comes from a programmer forgetting a null check. They come from a category error: a system asked a statistical question and built to give a categorical answer. Demand certainty from evidence that does not contain certainty and the system will manufacture it, and the manufactured certainty is where the ghosts live.

We start with the plain version, that matching means weighing evidence rather than checking a key, then mark where that picture breaks, then do the real thing: the 1969 statistical model that still underlies almost every serious matcher in production in 2026, the blocking tricks that make it run at national scale, the string and phonetic comparisons that feed it, the biometric version of the same problem, the threshold that is a policy instrument in disguise, and the merge operation that almost nobody builds an inverse for.

Two neighbours to mark and leave alone. The moment an authority decides a new person exists, and the fraud that concentrates there, is chapter 7 on enrolment; here records already exist and we ask which refer to the same human. What makes a register an authority whose assertions others rely on is chapter 9; here we care only whether its rows are correctly grouped.

The plain version#

Two class lists on one desk#

Imagine a school that has just absorbed a smaller school down the road. On the head teacher’s desk are two lists of children. The first list has eight hundred names on it. The second has three hundred. Some of the children on the second list already appear on the first, because they moved across last year and were written down twice. Nobody knows how many. The head teacher’s job today is to produce one list.

The obvious plan is to look for names that appear on both lists and cross out the copies. Try it for five minutes and it falls apart.

On the first list there is a child written as Priya Subramanian, born on the fourteenth of March 1987, in postcode 600017. On the second list there is Priyaa Subramaniam, born on the fourteenth of March 1987, in postcode 600017. Two letters differ across the two names. Everything else is identical. Are they the same child?

Almost certainly yes. But notice what you just did. You did not check whether the two rows were equal. You looked at each piece of information in turn, asked how surprising the agreement was, and added the surprises up. The birth dates agreeing is surprising if these are two different children. The postcodes agreeing is surprising too. The names nearly agreeing proves nothing on its own, because plenty of children have similar names, but combined with the rest it pushes the answer over the line.

That is the whole idea of this chapter. Matching is not comparison. It is weighing evidence. Each field is a witness. Some witnesses are worth a great deal and some are worth almost nothing, and the skill is knowing which is which before you ask them anything.

Why some witnesses are worth more than others#

Here is the test that tells you what a witness is worth. Ask two questions about each field, in this order.

First: if these two records really are the same person, how often would this field agree? Call that the field’s truthfulness. A birth date is a truthful field, because people who write down their birth date twice usually write the same thing. A telephone number is much less truthful, because people change telephone numbers and only one of the two records gets updated.

Second: if these two records are two different people picked at random, how often would this field agree anyway? Call that the field’s coincidence rate. Sex recorded as female has a coincidence rate near one half, because half the population is recorded that way. A full birth date has a coincidence rate of roughly one in thirteen thousand. A mobile telephone number has a coincidence rate of roughly one in half a million.

The value of a witness is truthfulness divided by coincidence. A field that almost always agrees for the same person, and almost never agrees for different people, is worth a great deal. A field that agrees for everybody is worth nothing however truthful it is. This is why “sex agrees” tells you almost nothing and “mobile number agrees exactly” tells you almost everything, even though people are far more careless with telephone numbers than with sex.

The second question is the one people skip. It is not enough to know that a field is accurate; you have to know how often it agrees by accident. That is why matching on a surname alone is useless in a country where a fifth of the population shares a hundred surnames and quite powerful where surnames are rare, and why a matching system tuned in one country and shipped to another behaves like a different product.

Adding up the evidence in points#

Let us put numbers on it, in points, and keep the arithmetic on the kitchen table. Each point is a doubling of the odds. Evidence that makes it twice as likely that two records are the same person is worth one point; four times is two points; eight times is three; a thousand times is about ten, because doubling ten times gets you just over a thousand.

Points can be negative. If a field that usually agrees for the same person disagrees, that counts against the match. Points from different fields add together, which is the whole reason for using this scale rather than multiplying probabilities.

Now the crucial and unintuitive part. Before you look at any field at all, you must start from a heavy penalty, and the penalty gets heavier the bigger the register is. In a register of forty million people there are about eight hundred million million possible pairs of records. If the register holds, say, six hundred thousand genuine duplicate pairs, then a pair chosen blindly is a genuine duplicate about once in every one and a third thousand million million tries. Before any evidence arrives, the sensible starting position is that any two records you pick are different people. On our points scale that is worth about minus thirty points.

Minus thirty points is a shock the first time you see it. It means evidence worth twenty-five points is still not enough. It means two records agreeing on name and sex and town, which feels overwhelming to a human reading them, may not be enough. Big registers are suspicious places, and they should be.

Here is our pair of children, scored.

Plus five points means the odds are about thirty-four to one in favour of these being the same child, a probability of about 97 in a hundred. That sounds like a decision. It is not, and the next section explains why.

Three answers, not two#

The natural instinct is to pick a cut-off. Above it, same person. Below it, different people. That gives two answers and it is wrong.

Consider what a wrong answer costs in each direction. If the head teacher wrongly decides two rows are the same child, the school loses a child: no place assigned, no meals ordered, no letters home, and nobody notices until somebody physically looks for them. If she wrongly decides two rows are different children, the school orders one extra lunch and prints one extra name badge, and somebody notices at the door on the first morning.

Those two errors are not the same size, or even the same kind of thing. A system that treats them as symmetric, by picking one number and calling everything above it a match, has already made a policy decision without telling anybody.

So a good matcher gives three answers. The first is yes, join these, reserved for evidence so strong that the residual doubt is smaller than the harm of asking a human. The second is no, leave these apart, for evidence weak enough that pursuing it wastes everybody’s time. Between them sits the important one: a human should look at this. In the trade that middle band is called clerical review, and it is not an admission of failure. It is where the system tells the truth about its own uncertainty instead of hiding it.

Our pair of children, at plus five points and 97 in 100, sits in the middle band. A clerk looks at both rows, sees two spellings of one Tamil name and one address, and joins them in four seconds. Had somebody instead set a single cut-off at 90 in 100 and let the machine decide, the machine would have got this one right and eventually got a different one wrong, silently, with nobody watching.

What happens when a machine looks at faces instead#

Everything so far assumed the evidence was written down. Suppose instead you had a photograph of each child, and a machine that compares two photographs and returns a number between zero and one for how alike they are. It feels as though that should end the argument. It does not, for a reason worth understanding properly. Comparing two photographs is one comparison. Searching a photograph against a list of a million children is a million comparisons, and every one of them is a fresh chance to be wrong.

Suppose the machine wrongly says “same person” about two different children once in every million comparisons. That sounds superb. Now search one new photograph against a gallery of a million children. You have taken a million tickets in a lottery you lose. The chance that at least one of those comparisons comes back wrongly is not one in a million. It is about sixty-three in a hundred. On average, a search of that gallery surfaces a stranger who looks like a match more often than not.

This is the most misunderstood fact in biometrics and it is pure arithmetic. A comparison error rate that is excellent for checking one person against one record is catastrophic for searching one person against a nation. Scaling the search up by a factor of a thousand demands that the underlying comparison get a thousand times better just to stand still.

The operation nobody builds backwards#

The last plain idea causes the most lasting damage.

When the head teacher decides two rows are one child, she crosses one out. The next day the office writes new notes against the surviving row: dietary requirement, emergency contact, a sprained wrist. A week later somebody realizes the two rows were two different children after all, cousins with nearly the same name and the same birthday.

Now try to undo it. Which of the week’s notes belongs to which child? The crossing-out destroyed the information you would need. Worse, the merged row has gone out to the meals contractor, the bus company, the local clinic and the county register, and each has written its own notes against it.

Merging is a one-way door. Almost every system built in the last forty years has a button for it and no button for the reverse. The fix is simple to say and hard to make anybody pay for: never cross anything out. Keep both rows exactly as they were, and write a separate note saying “we believe these two rows are the same child, decided on this date, by this clerk, on this evidence.” That note can be withdrawn. A crossing-out cannot.

Where the plain version stops being true#

The witnesses are not independent, and pretending they are inflates every score#

The points-adding trick has a hidden assumption inside it. Adding points from separate fields is only valid if the fields are independent, which means that knowing what one field did tells you nothing about what the next one will do.

Real identity fields are nothing like independent. Postcode and city agree together or disagree together, because a postcode determines a city. Given name and sex are correlated, because most given names are strongly associated with one sex. Surname and postcode are correlated, because families live together and because communities cluster geographically.

Add points from correlated fields and you count the same evidence twice. The score comes out too high, and it does so in exactly the cases you care about, because correlated agreement is commonest among people who live near each other and are related. Cousins, siblings and parent-child pairs are the population that fools a naive matcher, and also the population where a wrong merge does the most harm.

The honest version: the additive score is a first-order approximation that assumes conditional independence given match status, and that assumption is known to be false for identity data. The professional responses are to model groups of correlated fields as a single composite field, to apply term-frequency adjustments so that agreement on a common value earns fewer points than agreement on a rare one, or to fit a model that allows dependence between the fields explicitly. Every serious matcher does at least one of these. A matcher that does none of them will over-merge families.

You cannot compare everything with everything#

The plain version quietly assumed the head teacher looks at every pair of rows. With eight hundred and three hundred rows that is fine. With a national register it is arithmetic that never finishes. The number of distinct pairs in a set of N records is N times N minus one, divided by two, which grows as the square of N.

Those times assume a single processing core doing a million pair comparisons every second, which is generous for anything computing a string similarity. The point survives any reasonable adjustment: you cannot compare everything with everything, and the fix is not a faster computer. The fix is called blocking, and the technical half covers it. Its cost is the part to keep in mind now: blocking works by refusing to compare most pairs, so any true match it refuses to compare is lost forever, silently, with no error message. Blocking is where recall goes to die, and almost nobody measures it.

The threshold is not a technical setting#

The plain version treated the cut-off as a knob an engineer turns. It is not. Move the threshold down and you catch more true duplicates and merge more strangers; move it up and you merge fewer strangers and leave more true duplicates in the register. No setting avoids both, because the score distributions of true and false pairs always overlap; if they did not, you would not need a threshold at all.

The honest version: choosing a threshold is choosing a ratio between two harms that fall on different people. The number belongs to whoever is accountable for both, and it should be written in a policy document with a date on it, not left in a configuration file.

Names are not the stable strings the analogy assumed#

The plain version treated a name as a string that is either right or slightly mistyped. The reality is that a name is a social object with regional, script, ordering and life-event variation baked into it, and the ways it varies are not the ways a keyboard slip varies. Chapter 5 handles that in full; the one line to carry here is that a matcher comparing name strings is comparing transcriptions of names, not names, and the transcription rules differ by clerk, by decade and by country.

Biometrics change the shape of the problem, not the nature of it#

The plain version presented photograph matching as a different kind of evidence. It is not. A biometric comparison produces a score, that score has one distribution for true pairs and another for false pairs, the two overlap, and a threshold cuts between them. That is precisely the structure of the name-and-birthday problem. Only the numbers change.

What biometrics genuinely change is the coincidence rate. A ten-finger comparison has a coincidence rate many orders of magnitude below any demographic field, which is why national registers use it. What they do not change is that the coincidence rate is multiplied by the size of the gallery, that some people cannot present a usable sample at all, and that error rates differ measurably between demographic groups. A biometric system is a statistical matcher with better numbers, not an oracle.

The pairwise answer does not settle the group answer#

The plain version asked about pairs. Registers are made of clusters.

Suppose the matcher says record A and record B are the same person, and B and C are the same person, but A and C score below threshold. Sameness in the real world is transitive: if A is B and B is C then A is C. Sameness according to a threshold is not, because a threshold applied to a continuous score has no reason to respect transitivity.

Resolve it by taking connected components, joining anything reachable through a chain of links, and you get a phenomenon every practitioner has seen: one weak link joins two large clusters, another joins a third, and eventually a single cluster holds fifty thousand people and is known as the monster. Resolve it instead by demanding that every pair inside a cluster clears the threshold, and you fragment genuine identities. Both answers are defensible and neither is right, which is a sign the question has been asked at the wrong level.

The honest version of the whole chapter#

The honest version: a matching system never decides who somebody is. It produces a numerical belief that two records refer to one person, and an organization then decides what action that belief justifies. Every failure of consequence in this field comes from losing the distinction between those two things: storing the action instead of the belief, copying the action to a downstream system that no longer sees the belief, and making the action irreversible.

The technical version#

Deterministic matching, and precisely what it breaks on#

Deterministic matching decides that two records refer to the same entity when a specified set of fields is equal after normalization. It is the industry’s default because it is cheap, explainable, and gives an auditor something to point at.

Normalization does more work here than people credit. A serious deterministic rule compares canonical forms, not raw strings: case folding, Unicode normalization to a canonical composed or decomposed form, stripping combining marks where the domain allows it, collapsing internal whitespace, removing punctuation, standardizing dates to one calendar and format, converting telephone numbers to a full international form, and standardizing addresses against a postal file. Two records that fail an exact comparison before normalization very often pass after it, and a large share of the “probabilistic matching” a team thinks it needs is really unfinished normalization.

Even done perfectly, deterministic matching fails in four distinct ways, worth separating because the remedies differ. It fails on transcription variation: SUBRAMANIAN against SUBRAMANIAM, one character apart, because two clerks heard one sound and wrote it differently. It fails on field absence: a record with no telephone number cannot match on telephone number, and a rule requiring agreement treats absence as disagreement. It fails on legitimate change: people move, marry, change numbers and correct their own birth dates, so one person’s records diverge over time by design. And it fails on collision, the direction people forget: the rule fires when it should not.

The scale of collision is the surprise. In the Bipartisan Policy Center’s study of patient matching, published in June 2012 as Looking for a Perfect Match: Challenges and Strategies for Matching Patients’ Scattered Health Data, the authors report that Harris County, Texas contained 2,488 real patients named Maria Garcia, that 231 of them shared a date of birth, and that the county held 69,807 pairs of patients agreeing on both name and date of birth. A deterministic rule of “same full name and same date of birth” would have merged 69,807 pairs of distinct human beings in one county. The figure was not a one-off: reporting by the Advisory Board in February 2019 quoted Harris Health System’s then chief information officer, Tim Tindle, giving updated counts of 2,833 records for the name Maria Garcia, 528 of them sharing a birth date.

The useful way to think about this: a deterministic rule is a probabilistic rule with the weights hard-wired to plus and minus infinity. It is the same technique with the uncertainty deleted, and deleting uncertainty does not remove it from the world.

A deterministic rule cascade is a legitimate design when the rules are ordered and each is separately measured: national identifier equal; else passport number and issuing country equal; else full name, date of birth and postcode equal; else no match. It becomes indefensible the moment somebody adds a tier without measuring it, which is how “same surname and same year of birth” reaches production.

Fellegi-Sunter: the model underneath almost everything#

The statistical treatment is older than most people assume. Howard Newcombe and colleagues published Automatic Linkage of Vital Records in Science, volume 130, issue 3381, pages 954 to 959, October 1959, setting out the idea of comparing records field by field and combining odds. Ivan Fellegi and Alan Sunter gave it a formal statistical basis in A Theory for Record Linkage, in the Journal of the American Statistical Association, volume 64, issue 328, pages 1183 to 1210, December 1969. That paper is still the model of record linkage in production use in 2026, implemented directly by modern tooling.

The set-up. Take two files, A and B. The set of all pairs divides into two disjoint subsets: the matched set M, of pairs referring to the same entity, and the unmatched set U. For each pair you compute a comparison vector, written gamma in the paper, whose components record the outcome of comparing each field: agree, disagree, or one of several graded levels in between. For each field and each outcome there are then two conditional probabilities.

The m probability is the probability of observing that outcome given the pair is in M. It measures data quality and stability; a field with high m is one people record consistently for themselves.

The u probability is the probability of observing that outcome given the pair is in U. It measures coincidence and cardinality; a field with low u is one where agreement between two random strangers is rare.

Fellegi and Sunter form the ratio of the two likelihoods, written R, being the probability of the observed comparison vector under M divided by its probability under U, and prove that ordering pairs by R and cutting at two thresholds is optimal. Optimal has a precise meaning: for any fixed pair of error levels, no other decision rule produces a smaller middle region. The two error levels are conventionally written mu, the probability of declaring a link when the pair is genuinely unmatched, and lambda, the probability of declaring a non-link when the pair is genuinely matched.

The rule has three outcomes, and the paper names them:

1. Positive link, written A1, when R is at or above the upper threshold.
2. Possible link, written A2, when R falls between the thresholds. This is the clerical review region, and Fellegi and Sunter treat it as a first-class output, not as a failure.
3. Positive non-link, written A3, when R is at or below the lower threshold.

Two thresholds, three outcomes. Any system offering two outcomes has thrown away the middle region, and the middle region is where the interesting pairs live.

In practice nobody works with R directly. Because outcomes across fields are assumed conditionally independent given match status, the log of the ratio is a sum, and sums are easier to reason about, explain to an auditor and display. Logarithms to base 2 give weights in bits, one bit being one doubling of the odds, and adding a prior gives a total that converts directly to a posterior probability.

from math import log2

def field_weight(m, u):
    if m is None or u is None:
        return 0.0
    return log2(m / u)

def match_weight(prior, pairs):
    w = log2(prior / (1.0 - prior))
    for m, u in pairs:
        w += field_weight(m, u)
    return w

def posterior(w):
    return 2.0 ** w / (1.0 + 2.0 ** w)

A trap worth naming. In the 1969 paper, lambda is one of the two error levels. In modern tooling that follows the same model, notably the Splink package maintained by the Ministry of Justice Analytical Services in the United Kingdom, lambda denotes the prior probability that a randomly chosen pair is a match. These are different quantities that share a letter. Read every paper’s notation before you copy a formula out of it.

Estimating m and u without a labelled answer key#

The model needs m and u for every field and every comparison level. You almost never have a labelled set of true matches to estimate them from, which is the practical heart of the difficulty.

The u probabilities are the easy half, because they describe random pairs and a large file is mostly random pairs. Sample pairs uniformly from a large register and the overwhelming majority are non-matches, so the observed agreement rate on a field estimates that field’s u. For a categorical field you can do better and compute u analytically from the value distribution: the probability that two random records agree is the sum over values of the square of each value’s frequency.

That calculation is what tells you a full date of birth is worth about thirteen and a half bits. If birth dates were spread evenly over 365.25 days and eighty birth years, the agreement probability for a random pair would be one in 29,220. Real populations are not evenly spread, and administrative data has a notorious pile-up on the first of January. An effective value near one in thirteen thousand, a u of about 0.000075, is a realistic working figure for a national register, and it is worth measuring rather than assuming.

The m probabilities are the hard half, because they describe true matches and you have no list of those. Three approaches are used. Expectation-maximization fits the two-component mixture directly: treat match status as a latent variable, start from a guess, compute the expected match status of each pair under the current parameters, re-estimate, and iterate; William Winkler at the United States Census Bureau developed this line of work through the 1980s and 1990s. Bootstrapping blocks on a field so discriminating that its pairs are essentially all true matches, such as an exact national identifier, then measures how often the other fields agree within that set, at the cost of a bias: people with a recorded national identifier are not a random sample. Hand-labelling a sample is expensive, is the only approach that gives an honest estimate of overall accuracy, and should be done anyway, because without it you cannot measure the system at all.

Here is a worked parameter table for a national health register of forty million records, carried through the rest of the chapter. The numbers are illustrative rather than measured from a public dataset, and are chosen to be realistic for that setting.

“Close” for a name means a Jaro-Winkler similarity of at least 0.92, which we compute properly further down. Converting each of these to bits gives the weights we will use.

Read the last three rows together, because they contain the lesson. Agreement on sex is worth about one bit, which is to say it doubles the odds and no more. Agreement on a mobile number is worth about seventeen and a half bits, which is to say it multiplies the odds by about two hundred thousand. Disagreement on a mobile number costs less than one bit, because people change numbers. A field can be enormously valuable when it agrees and nearly worthless when it does not, and any scoring scheme that uses one number per field rather than one number per outcome cannot express that.

Blocking: making the square root of the problem#

Comparing every pair is impossible past a few hundred thousand records. Blocking is the standard answer: partition or index the records so that only records sharing a blocking key are compared. The classic key for identity data is a coarse, robust function of several fields. A phonetic code of the family name paired with year of birth is a common choice, because the code survives spelling variation and the year survives day and month transposition.

-- candidate pairs are the union of these rules,
-- deduplicated; a pair need satisfy only one
l.family_phonetic = r.family_phonetic
  and l.birth_year = r.birth_year

l.birth_date = r.birth_date
  and substr(l.postcode, 1, 3) = substr(r.postcode, 1, 3)

l.mobile_e164 = r.mobile_e164

l.given_phonetic = r.given_phonetic
  and l.family_phonetic = r.family_phonetic

Two measures govern the design, and both must be reported. Reduction ratio is one minus the number of candidate pairs divided by the number of total pairs; it measures how much work you saved. Pairs completeness is the proportion of true matching pairs that appear among the candidates; it measures how much truth you destroyed. Teams fail to measure the second, because measuring it requires a labelled sample, and without it a blocking scheme that silently drops a fifth of the true matches looks identical to one that drops none.

Work the arithmetic for our forty-million-record register. Suppose the first rule yields roughly 160,000 populated blocks, a few thousand common phonetic codes crossed with about eighty birth years. Spread evenly, each block holds 250 records, giving 31,125 pairs per block and about 4.98 thousand million candidate pairs in total, against about 800 million million total pairs: a reduction ratio of 0.999994, a saving of roughly 160,000 times.

Records are not spread evenly, and that is the operational problem. Name distributions have very heavy heads. If two per cent of the register shares one phonetic code and one birth year, that single block holds 800,000 records and 3.2e11 pairs by itself, more work than the other 159,999 blocks combined. The standard fixes are to salt oversized blocks with another key component, to cap block size and fall back to a finer rule, or to use a technique that does not partition at all.

Three alternatives to strict partitioning are worth naming. Sorted neighbourhood sorts records by a key and compares only within a sliding window of fixed width, degrading gracefully instead of exploding. Canopy clustering uses a cheap similarity to form overlapping candidate groups before applying an expensive one. Locality-sensitive hashing, typically MinHash over character n-grams, hashes records so that similar ones collide with high probability. All three are conventions of practice, not standards.

The rule to remember: use several blocking rules and take the union of their candidate pairs, because a pair missed by one rule is often caught by another, and a single rule is a single point of silent failure.

   40,000,000 records
          |
          v
  [1] normalize  case, marks, dates, phones, postcodes
          |
          v
  [2] block      union of 4 rules, salted
          |
          v      about 5.0e9 candidate pairs
  [3] compare    per-field comparison levels
          |
          v
  [4] score      prior + sum of log2(m/u), in bits
          |
   +------+---------------+----------------+
   |                      |                |
   v                      v                v
 at or above          between          at or below
 upper threshold      thresholds       lower threshold
   |                      |                |
 A1 LINK            A2 REVIEW          A3 NON-LINK
   |                      |                |
   v                      v                v
 write link         queue for clerk    discard, log
 assertion          with evidence      the score

String similarity: edit distance and the Jaro family#

Blocking decides which pairs get compared. String comparison decides what the comparison says.

Levenshtein distance is the minimum number of single-character insertions, deletions and substitutions needed to turn one string into the other. Vladimir Levenshtein published it in Russian in 1965 in Doklady Akademii Nauk SSSR, volume 163, number 4, pages 845 to 848; the English translation appeared in Soviet Physics Doklady, volume 10, number 8, pages 707 to 710, in 1966. The standard dynamic-programming computation is the Wagner-Fischer algorithm, published in the Journal of the ACM, volume 21, issue 1, pages 168 to 173, in 1974, and it runs in time proportional to the product of the two string lengths.

The matrix is worth seeing once. Each cell holds the distance between the two prefixes ending at that row and column.

        ""   S    M    Y    T    H
   ""    0   1    2    3    4    5
   S     1   0    1    2    3    4
   M     2   1    0    1    2    3
   I     3   2    1    1    2    3
   T     4   3    2    2    1    2
   H     5   4    3    3    2    1

The bottom right cell reads 1: SMITH and SMYTH are one substitution apart.

Plain Levenshtein has a specific blind spot. It charges two edits for a transposition, because swapping two adjacent characters looks like two substitutions, and transposition is the commonest typing error there is. Fred Damerau, in A technique for computer detection and correction of spelling errors, Communications of the ACM, volume 7, issue 3, pages 171 to 176, March 1964, reported that more than 80 per cent of the spelling errors he studied were a single insertion, deletion, substitution or transposition. The variant charging one for an adjacent transposition is Damerau-Levenshtein, and for name data it is the better default.

The Jaro family was built for record linkage rather than spelling correction, and it behaves differently in a way that matters. Jaro similarity counts characters appearing in both strings within a window, counts how many of those are out of order, and combines three ratios. The window is the floor of half the longer string’s length, minus one. Transpositions count as half the number of matched characters appearing in a different relative order. The result is one for identical strings and zero for strings with no characters in common.

Matthew Jaro introduced it in Advances in Record-Linkage Methodology as Applied to Matching the 1985 Census of Tampa, Florida, in the Journal of the American Statistical Association, 1 June 1989, pages 414 to 420. William Winkler added a prefix bonus in String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage, ERIC document ED325505, in 1990. The bonus raises the score when the strings share a leading prefix, up to a maximum prefix length of four characters, with a standard scaling constant of 0.1. The reasoning is empirical: people get the beginnings of names right far more often than the ends.

Here are the values for the pairs in our worked example and three classics, computed by hand from the definitions above.

Two things to read off that table. MARTHA against MARHTA is two edits under plain Levenshtein and one under Damerau-Levenshtein, yet Jaro-Winkler puts it at 0.961, because transposition is what Jaro was designed to forgive. And SMITH against SMYTH is a single edit yet scores lower than MARTHA against MARHTA, because in a five-character string one non-matching character costs proportionally more. The two measures disagree about which pair is closer, and neither is wrong; they measure different things. Choose per field and document the choice.

The failure no string metric can address: a similarity of exactly 1.000 does not mean the same person. Where one given name and family name combination is shared by tens of thousands of people, an exact string match on the full name is weak evidence, and only the u probability tells you so. String similarity feeds the comparison level. It is not the score.

Phonetic keys, and the languages they were not written for#

Phonetic keys reduce a name to a code that is stable across spelling variants, so variants land in the same block. They are blocking tools first and comparison tools second.

Soundex is the oldest and by a wide margin the most deployed. Robert C. Russell patented it in the United States: patent 1,261,167, granted 2 April 1918, and patent 1,435,663, granted 14 November 1922. Margaret K. Odell is named alongside Russell in most histories of the method. The United States National Archives publishes the coding rules used for the census indexes, and they are short enough to state in full. Keep the first letter of the surname; code the remaining letters by this table, disregarding A, E, I, O, U, H, W and Y entirely.

Two letters with the same code standing side by side are coded once. If an H or a W separates two consonants that share a code, the consonant on the right is not coded. Vowels between two consonants that share a code do separate them, and both are coded. Truncate to three digits, or pad with zeros to reach three. The result is one letter and three digits. The National Archives gives Jackson as J250 and Lee as L000.

Notice the size of the output space. One letter followed by three digits drawn from zero to six gives 8,918 combinations, and since padding zeros can only appear at the end, the reachable set is 26 times 259, or 6,734 distinct codes. A national register of forty million people therefore has, at best, about six thousand family-name buckets, and the real distribution is far more skewed than that. Soundex is a coarse sieve, and was designed to be.

The failures are of two opposite kinds. It over-collapses. Compute a few by hand and the problem is immediate.

SMITH and SMYTHE collapsing together is exactly what you wanted. SANDY joining them is not. SCHMIDT failing to join them is the same failure in the other direction, and it is the canonical example, because Schmidt is the German form of the same occupational name.

It also under-collapses whenever the initial letter varies, because the first letter is never coded. CATHERINE gives C365 and KATHERINE gives K365, so two spellings of one name can never share a block. TCHAIKOVSKY gives T221 and CHAIKOVSKI gives C212. The method’s most consequential design decision, preserving the initial letter uncoded, is also its biggest source of missed matches, and it is worst precisely where transliteration is involved.

That brings us to the failure that matters most for the majority of the world’s population: Soundex was built for English surnames written by English-speaking clerks. Take a set of Indian names, transliterated as they commonly are.

The first pair works. The second does not: Chatterjee and Chattopadhyay are the anglicized and Sanskritized renderings of one Bengali surname, and Soundex files them in different blocks, so a deduplication run using Soundex blocking never compares them. The third fails too: Mohd is the standard written abbreviation of Mohammed across South Asia and the Gulf, appears in millions of records, and codes to M300, sharing no block with the M530 of the full form.

The successors improved matters without solving them.

NYSIIS, the New York State Identification and Intelligence System algorithm, was devised in 1970 by the body that became the New York State Division of Criminal Justice Services. It codes the first letter rather than preserving it, and handles several English digraphs explicitly.

Daitch-Mokotoff Soundex was created in 1985 by the genealogists Gary Mokotoff and Randy Daitch, precisely because Russell Soundex performed badly on Slavic and Yiddish surnames. It produces six digits rather than three, codes the initial character instead of preserving it, and can return several codes for one name where the pronunciation is genuinely ambiguous. That last property, returning a set rather than a value, is the important architectural idea.

Metaphone, published by Lawrence Philips in Computer Language, volume 7, number 12, December 1990, replaced Soundex’s letter table with a rule set over English spelling patterns. Double Metaphone followed, its implementation described in the June 2000 issue of the C/C++ Users Journal. It returns a primary and a secondary code, so a name whose pronunciation depends on its language of origin is filed under both, and a pair matches if any code on one side equals any code on the other. Its rules attempt to cover English words of Slavic, Germanic, Celtic, Greek, French, Italian, Spanish and Chinese origin, using on the order of a hundred distinct contexts for the letter C alone. Metaphone 3 was released in October 2009 as a commercial product; its publisher claims roughly 99 per cent accuracy for English words, non-English words familiar to Americans, and names commonly found in the United States. Note the boundary of that claim: it is a marketing claim about a named population, not an established fact about names, and it says nothing about names as recorded in Chennai or Lagos or Jakarta.

The honest position in 2026: phonetic keys are a cheap, mature blocking aid that works acceptably on the language they were tuned for and degrades systematically rather than randomly elsewhere. Systematic degradation is the dangerous kind, because it removes whole communities rather than a random sample of records. If your register serves a population whose names came through transliteration, measure pairs completeness by name origin rather than overall, or you will ship a system that deduplicates one community well and another badly and reports one healthy-looking number.

Biometric deduplication and the one-to-N problem#

Biometric deduplication asks the same question with different evidence: does this new subject already exist in the gallery? It is a one-to-many search, written 1:N, and it is not a one-to-one verification repeated N times, for reasons that are arithmetic rather than engineering.

Get the vocabulary exact, because the two pairs of terms are routinely confused. They are defined in ISO/IEC 19795-1:2021, Information technology - Biometric performance testing and reporting - Part 1: Principles and framework, second edition, 27 May 2021.

At the level of a single comparison, false match rate, FMR, is the proportion of comparisons between different subjects wrongly declared to match, and false non-match rate, FNMR, is the proportion of comparisons within one subject wrongly declared not to match. At the level of a search, false positive identification rate, FPIR, is the proportion of searches for subjects not in the gallery that return one or more candidates above threshold, and false negative identification rate, FNIR, is the proportion of searches for subjects who are in the gallery that fail to return the right entry above threshold. Separately, failure to enrol and failure to acquire count the people from whom no usable sample could be obtained, and in national systems those are not rounding errors.

The relation between the two levels is the whole problem. If a search compares the probe against every one of N gallery entries independently, the chance of at least one false match is one minus the quantity one minus FMR, raised to the power N, which for small FMR is close to N multiplied by FMR.

The same table read the other way gives the design requirement. To hold FPIR at one in a thousand against a gallery of 1.4 thousand million people, the underlying per-comparison false match rate must be about 7 in 1e13. No single biometric modality reaches that. This is the entire reason national deduplication systems fuse several modalities rather than picking the best one.

What can be reached is measurable, and NIST publishes the measurements. The Face Recognition Technology Evaluation, formerly the Face Recognition Vendor Test, runs a continuous 1:N identification track. Its public results page, last updated on 4 August 2026, reports FNIR at the threshold that limits FPIR to 0.003, against galleries of stated size, each person enrolled from a single image. Against a gallery of 12,000,000 mugshots searched with a mugshot, the leading submission when checked in August 2026 was idemia_013, dated 1 July 2026, at an FNIR of 0.0005, with nec_010 and qazsmartvisionai_002 next at 0.0007. Those are the easy conditions. The same table shows how fast accuracy falls when the image does not cooperate.

A miss rate of 0.05 per cent under studio conditions and 4.6 per cent on a profile view is a factor of about ninety, from the same algorithms, on the same day. A figure quoted for a face system without its capture conditions and gallery size is not a figure.

Fingerprints tell a consistent story. NIST Interagency Report 8034, Fingerprint Vendor Technology Evaluation, by Watson, Fiumara, Tabassi, Cheng, Flanagan and Salamon, published on 8 January 2015, reports for the most accurate submissions, at an FPIR of one in a thousand: an FNIR of 1.9 per cent for a single index finger against 100,000 enrolled subjects, 0.27 per cent for two index fingers against 1,600,000 subjects, and 0.09 per cent for ten-finger flat impressions against 3,000,000 subjects. Eighteen vendors took part. Those three rows show the fusion effect directly: adding fingers cuts the miss rate by roughly a factor of seven each time, even as the gallery grows.

That is the arithmetic that shaped the largest deduplication system ever built. India’s Unique Identification Authority, established on 28 January 2009, enrols ten fingerprints, two irises and a facial image, and issues an Aadhaar number only after checking the new biometric record against every record already held. The first number was issued in September 2010. The UIDAI dashboard displayed a cumulative total of 1,451,262,807 Aadhaar numbers generated when checked in August 2026.

UIDAI published its own measured deduplication accuracy in Role of Biometric Technology in Aadhaar Enrolment, dated 31 December 2011, based on a live gallery of 84 million enrolment records. It reports a false positive identification rate of 0.057 per cent, measured with a probe set of 4 million records, a false negative identification rate of 0.035 per cent, measured against 31,399 known duplicates, and a biometric failure-to-enrol rate of 0.14 per cent. The architecture ran three automatic biometric identification systems from different suppliers in parallel, both to raise throughput and because combining independent systems improves accuracy beyond what any one achieves. The central finding was that accuracy using both irises and ten fingerprints was more than an order of magnitude better than any single modality.

Work the implication of that 0.057 per cent. An FPIR of 0.00057 against a gallery of 84 million implies a per-comparison false match rate of about 6.8 in 1e12. Held constant and extrapolated to a gallery of 1.4 thousand million, that gives a search-level FPIR of roughly 0.95 per cent, about one new enrolment in a hundred surfacing a false candidate. The extrapolation is rough and UIDAI’s operational thresholds are not public, but the order of magnitude explains why a system at that scale needs a large manual adjudication stage behind the automatic one, and why it has one.

The failure modes are not hypothetical. The Comptroller and Auditor General of India’s performance audit of UIDAI, reported in the Indian press in April 2022, found that UIDAI had cancelled more than 475,000 Aadhaar numbers as duplicates as at November 2019, an average of about 145 a day over the period examined [UNVERIFIED: the CAG report number and the exact date it was tabled in Parliament].

And a single false positive from a 1:N search can cost a person their liberty. After the Madrid commuter train bombings of 11 March 2004, the FBI searched a latent fingerprint from the scene against its automated identification system and, on 20 March 2004, concluded that it matched Brandon Mayfield, a lawyer in Oregon. He was arrested on 6 May 2004 and released on 20 May 2004, after Spanish authorities announced on 19 May that the print belonged to an Algerian national, Ouhnane Daoud. The United States government settled part of Mayfield’s lawsuit for a reported two million dollars on 29 November 2006. The mechanism is the one in the table above: a candidate list from a very large gallery contains near-misses by construction, and a human examiner comparing a candidate against a target is subject to confirmation bias in a way a blind comparison is not. Face recognition has produced the same failure with the same structure. Robert Williams was arrested by the Detroit Police Department in January 2020 and held overnight after a facial recognition search run by Michigan State Police returned his old driving licence photograph as a candidate against surveillance footage of a shoplifting. He had nothing to do with it.

One last biometric fact changes system design: error rates are not uniform across demographic groups. NIST Interagency Report 8280, Face Recognition Vendor Test Part 3: Demographic Effects, by Grother, Ngan and Hanaoka, 19 December 2019, established that finding, and the current FRTE 1:N page continues to report it. Thresholds are set for each algorithm to give an FPIR of 0.002 or lower on searches of women born in Eastern Europe, and the published table then shades cells where FPIR for another group runs 20, 40 or 80 times larger. It also reports the inequity summaries required by ISO/IEC 19795-10:2024, a Gini coefficient and the ratio of the maximum of eight group FPIR values to their geometric mean. A headline accuracy number quoted without its demographic breakdown hides exactly the failure mode that ends in court.

Threshold as a policy instrument#

There is one score distribution for true matches and another for non-matches, they overlap, and a threshold cuts across both. Moving it trades one error for the other along a curve. Plotting FNIR against FPIR as the threshold sweeps gives the detection error trade-off curve, and that curve, not any single point on it, characterizes a system.

Work an example on our forty-million-record register. Suppose a deduplication run produces one million candidate pairs after blocking, of which 4,000 are true duplicates.

Those counts illustrate the shape rather than being measured, and the shape is the lesson: each step up the threshold removes wrong joins faster than right ones at first, then slower, while the duplicates you fail to catch climb the whole way. At a cut of 0.999 you have made five wrong joins and left about 1,490 duplicates in the register.

No arithmetic picks the row. Picking it needs two things arithmetic does not contain: the cost of a wrong join and the cost of a missed duplicate, in the same units. In a payments register a wrong join stops a living person’s money and a missed duplicate pays a ghost. In a clinical register a wrong join puts one person’s medication list in another person’s chart. In a marketing database both errors cost a stamp.

Two operational conventions follow. First, use two thresholds and staff the middle. Size the middle band by the review capacity you actually have, and measure the clerks: a review queue that is never worked is worse than none, because it converts a known uncertainty into a hidden one. Second, publish the threshold and the date it was set, treat changes to it as changes to policy rather than configuration, and re-measure after every change to the source data, because the score distribution moves whenever the data does.

A worked matching example, carried through to a decision#

Now the full example, end to end, with every number visible. Two records from our forty-million-record national health register.

record  R-4471                 R-9082
------  --------------------   --------------------
given   PRIYA                  PRIYAA
family  SUBRAMANIAN            SUBRAMANIAM
dob     1987-03-14             1987-03-14
sex     F                      F
post    600017                 600017
mobile  9840012345             (null)

Step one, blocking. The family-name phonetic code plus birth year puts both records in the same block, so the pair is generated as a candidate. Note in passing that Soundex on these two gives S165 for both, since the differing final letters M and N share code 5, so this pair survives Soundex blocking; the Chattopadhyay case earlier in the chapter would not have.

Step two, comparison levels. Jaro-Winkler on the family names: SUBRAMANIAN against SUBRAMANIAM. Both are eleven characters. The matching window is the floor of eleven over two, minus one, which is four. Ten characters match in place and none are transposed, so Jaro gives one third of the sum of ten elevenths, ten elevenths and one, which is 0.9394. The common prefix is capped at four characters, so Jaro-Winkler adds 0.4 times the shortfall from one, giving 0.9636. That clears the 0.92 cut, so the family name lands on the “close” level.

The given names: PRIYA against PRIYAA, five characters against six, window two, five matches, no transpositions. Jaro is one third of the sum of one, five sixths and one, which is 0.9444. Prefix four, so Jaro-Winkler is 0.9667. Also “close”.

Dates of birth are equal. Postcodes are equal. Sex agrees. The mobile number is present on one side and absent on the other, so the comparison is not applicable and contributes nothing. Treating a null as a disagreement is a common and serious bug; it charges the pair for evidence that was never collected.

Step three, the prior. Forty million records give about 8.0e14 pairs. Assume 600,000 true duplicate pairs, from an estimated duplicate rate of about 1.5 per cent. The prior probability that a randomly chosen pair matches is 7.5e-10, and the log to base 2 of the prior odds is -30.31 bits.

Step four, the sum.

Step five, the decision. A total of 5.10 bits is odds of about 34 to 1, a posterior of 0.9717. With the upper threshold at a posterior of 0.99, which is 6.63 bits, and the lower at 0.10, which is minus 3.17 bits, this pair falls in the middle band. Outcome: A2, possible link, queued for clerical review with the evidence table above attached so the clerk sees why.

Now change one thing. Suppose R-9082 does carry a mobile number and it is 9840012345, identical.

The mobile-exact weight is 17.61 bits, so the total becomes 22.71 bits, a posterior of 0.99999985. Outcome: A1, positive link, no human needed. One field moved this pair across two thresholds, which is what a u probability of about one in half a million buys you.

Now a third record for contrast. R-5510 reads PRIYA SUBRAMANIAN, sex F, born 1987-03-04, postcode 600032, mobile 9884477661.

Minus 9.52 bits is a posterior of 0.0014. Outcome: A3, positive non-link. Read that carefully, because it is the result that convinces people the model is doing real work. Two records with an exactly equal full name, the same recorded sex, and birth dates in the same month of the same year are separated with a confidence of about 999 in 1,000, purely because the prior in a forty-million-record register is brutal and because the postcode and mobile disagree. A human eyeballing those two rows would very likely have merged them.

Merge, unmerge, and why the arrow only points one way#

The matcher produces a belief. Something then has to act on it, and this is where the ghosts are actually made.

The traditional action is a merge: pick one record as the survivor, apply survivorship rules to choose a value for each field, repoint foreign keys from the loser to the survivor, and delete or tombstone the loser. Survivorship rules are typically “most recently updated wins”, “most trusted source wins”, or “longest non-null value wins”. The result is often called a golden record.

Merge is easy to implement and it destroys information three ways at once. It destroys field-level provenance, so you can no longer say which source contributed the surviving address. It destroys the loser’s record identity, so any external system holding that identifier now has a dangling reference. And it merges the histories, so transactions written afterwards carry no marker of which original identity they belonged to.

An unmerge must therefore reconstruct three things that were deliberately thrown away: which pre-merge record each surviving field value came from, which post-merge transactions belong to which constituent, and what every downstream system was told. The first is recoverable if you kept an audit log. The second is generally unrecoverable by automatic means, because nobody recorded it at the time. The third depends on systems you do not control.

The standards literature is admirably blunt. The IHE IT Infrastructure Technical Framework defines the Patient Identity Feed transaction, which carries an HL7 version 2 message with trigger event A40, "Merge Patient

• Internal ID", when a patient identity source merges two records inside one identifier domain. Volume 2, section 3.8.4.2.4 states the position in one sentence: “Changes resulting from an A40 Merge message are not reversible. No UnMerge message is supported by this transaction.” That is the standard, not one vendor’s shortcoming. Volume 1 of the framework stood at revision 20.2, dated 11 November 2025, when checked in August

The scale of the corrective work is documented. The Bipartisan Policy Center’s 2012 study reports that Sharp HealthCare identified more than 652,000 unlinked records for one patient between 2001 and 2012, corrected 568,000, and still had over 84,000 outstanding; its survey of 128 chief information officers found 19 per cent reporting an adverse event in the previous year caused by a patient information mismatch. The Pew Charitable Trusts, in Enhanced Patient Matching Is Critical to Achieving Full Promise of Digital Health Records, 2 October 2018, reported match rates within a single facility as low as 80 per cent and between organizations as low as 50 per cent.

The architectural answer is to separate the belief from the action.

DESTRUCTIVE MERGE, what most systems do

  before   R-4471 (Priya)        R-9082 (Priyaa)
                  \                  /
  after            R-4471 survives
                   R-9082 deleted
                   field origins lost
                   later rows attach to R-4471 only

REVERSIBLE LINK, what to build instead

  before   R-4471                R-9082
                  \                  /
  after            C-00713 cluster, a computed view
                   |
                   +- member R-4471, asserted 2026-02-11
                   +- member R-9082, asserted 2026-02-11
                   +- evidence: score 22.71 bits, rule v7
                   +- decided by: automatic, threshold 0.99
                   both source rows untouched and addressable

Five design rules follow, and they are the practical output of this chapter.

1. Never delete or overwrite a source record. Matching decisions are assertions about records, not edits to them.
2. Give the cluster its own identifier, distinct from every member identifier, and hand it to downstream systems only when they can tolerate it changing.
3. Store the evidence with the assertion: score, model version, threshold in force, timestamp, and whether a human or a rule decided. An assertion without its evidence cannot be reviewed, only trusted or discarded.
4. Make withdrawal of an assertion a first-class operation with its own record, so unlinking is an event with a date rather than an absence.
5. Stamp every downstream row with the member identifier current when it was written, not only the cluster identifier. That one rule is what makes a later unmerge possible, and it costs one column.

Build that and an unmerge becomes: withdraw the assertion, recompute the clusters, let each downstream row follow its member identifier home. Skip it and an unmerge becomes a project.

Measuring a matcher, and the numbers that are usually missing#

A matcher that is not measured is a rumour. Four measurements matter and most deployments have at most two.

Pairwise precision and recall on a labelled sample. Precision is the share of links made that are correct; recall is the share of true links made. Both need ground truth, meaning a human-labelled sample. Sampling uniformly is wasteful because true matches are rare; stratify by score band and weight the estimates back.

Pairs completeness of the blocking stage, measured separately. Blocking losses do not appear in pairwise recall computed over candidate pairs alone, which is the commonest measurement error in the field: if blocking discards a fifth of the true matches, the matcher reports excellent recall while the system misses a fifth of the duplicates.

Cluster-level metrics, because pairwise metrics do not capture over-merging. A monster cluster of fifty thousand records can have superb pairwise precision and still be a catastrophe. Report the cluster size distribution, the largest cluster, and the count of clusters above a size implausible for the domain.

Drift. Score distributions move when the source data moves, when a new supplier starts contributing, or when a population changes. Re-measure on a schedule and after every source change, and keep the history so a change in match rate can be attributed.

Two further points. Transitivity must be resolved deliberately, and correlation clustering, or a graph partition penalizing both missing and spurious edges within a cluster, usually beats both connected components and the strict all-pairs rule. And record negative decisions, not only positive ones: a pair a clerk examined and rejected is expensive knowledge, and if it is not stored the same pair returns next month and may be decided the other way by a different clerk.

8.98 Common wrong ideas#

Wrong: If two records have the same name and date of birth they are the same person. Right: Name and date of birth agree by coincidence far more often than intuition suggests; one Texas county held 69,807 pairs of distinct patients agreeing on both, per the Bipartisan Policy Center’s 2012 study, so that agreement deserves a weight derived from its measured coincidence rate rather than treatment as proof.

Wrong: Fuzzy matching means using a string similarity function instead of an equality test. Right: String similarity only sets the comparison level for one field; the decision comes from combining every field’s level with its m and u probabilities and a prior reflecting the size of the register, and a similarity of 1.000 on a common name is still weak evidence.

Wrong: A matcher should output match or no match. Right: The Fellegi-Sunter rule of 1969 produces three outcomes, positive link, possible link and positive non-link, and the middle region is where the system reports its own uncertainty; deleting it does not remove the uncertain pairs, it decides them without telling anyone.

Wrong: Biometrics solve deduplication because fingerprints are unique. Right: Uniqueness of the trait is not the constraint; the constraint is that a search compares against every gallery entry, so a per-comparison false match rate of one in a million yields a false positive on about 63 per cent of searches of a million-record gallery, which is why national systems fuse ten fingerprints with two irises instead of relying on one modality.

Wrong: A published accuracy figure for a face recognition system tells you how it will perform. Right: NIST’s FRTE 1:N results, current at 4 August 2026, show the leading algorithms moving from an FNIR of 0.0005 on mugshot probes against a 12-million gallery to 0.0460 on 90-degree profile views against a 1.6-million gallery, so a figure without its capture conditions, gallery size, threshold and demographic breakdown is not a figure.

Wrong: Soundex handles spelling variation in names. Right: Soundex was designed for English surnames written by English-speaking clerks and never codes the first letter, so CATHERINE and KATHERINE cannot share a block, and it separates Chatterjee from Chattopadhyay and Mohammed from Mohd, meaning its failures fall on whole communities rather than on random records.

Wrong: Blocking is a performance optimization with no effect on accuracy. Right: Blocking decides which pairs are ever compared, so every true match whose records land in different blocks is lost with no error message, and the only way to know how many is to measure pairs completeness against a labelled sample.

Wrong: The matching threshold is a technical setting for the engineering team. Right: The threshold fixes the ratio between two harms falling on different people, a wrong join and a missed duplicate, so it is a policy decision that should be recorded with a date and an owner and re-measured whenever the source data changes.

Wrong: If a merge turns out to be wrong we can just unmerge it. Right: Merging discards field-level provenance and the losing record’s identity, and transactions written afterwards carry no marker of which constituent they belong to, which is why the IHE IT Infrastructure Technical Framework states plainly that changes from an A40 merge are not reversible and no unmerge message is supported.

Wrong: Adding more matching fields always improves accuracy. Right: The additive score assumes conditional independence, so adding correlated fields such as postcode and city, or given name and sex, counts the same evidence twice and inflates scores most for related people living together, which is exactly the population a wrong merge harms most.

8.99 Chapter summary in 20 lines#

1. Deciding whether two records describe the same person is a statistical question, and answering it as though it were exact manufactures a certainty the evidence does not contain.
2. The two failure modes are duplicates, one person becoming two records, and phantoms, two people collapsing into one, and the second is far more harmful.
3. Deterministic matching compares canonical forms for equality, and fails on transcription variation, missing values, legitimate change over time and coincidental collision.
4. Collision is the underrated failure: Harris County, Texas held 69,807 pairs of distinct patients sharing both full name and date of birth, per the Bipartisan Policy Center’s 2012 study.
5. Probabilistic record linkage weighs each field by how often it agrees for true matches, the m probability, divided by how often it agrees for random pairs, the u probability.
6. Fellegi and Sunter set out the model in the Journal of the American Statistical Association, volume 64, issue 328, pages 1183 to 1210, December 1969, building on Newcombe’s 1959 paper in Science.
7. Their rule has two thresholds and three outcomes, positive link, possible link and positive non-link, and the middle region is a feature rather than an admission of defeat.
8. Logarithms to base 2 turn the likelihood ratio into additive weights in bits, one bit being one doubling of the odds, so a score becomes a sum a person can read.
9. The prior matters enormously: in a forty-million-record register the starting position is about minus thirty bits, so evidence worth twenty-five bits still leaves a probable non-match.
10. Comparing every pair costs N squared over two comparisons, about 9.8e17 pairs for a register of 1.4 thousand million people, roughly thirty-one thousand core-years at a million pairs a second.
11. Blocking cuts that to a tractable number by comparing only records sharing a key, and its true cost is pairs completeness, the share of real matches it silently refuses to consider.
12. Levenshtein distance, published in Russian in 1965 and translated in 1966, counts edits; Damerau’s 1964 paper found over 80 per cent of typing errors were a single edit or transposition.
13. Jaro similarity of 1989 and Winkler’s 1990 prefix bonus were built for record linkage specifically, and forgive transposition where plain edit distance does not.
14. Soundex, patented by Russell in 1918 and 1922, never codes the first letter, which is why Catherine and Katherine can never share a block and why transliterated names fail systematically.
15. Metaphone of 1990, Double Metaphone of 2000 and Daitch-Mokotoff of 1985 code the initial character and can return several codes per name, but none of them is neutral across languages.
16. A one-to-many biometric search is not a one-to-one check repeated: a per-comparison false match rate of one in a million gives a false positive on about 63 per cent of million-record searches.
17. UIDAI’s 2011 report measured a false positive identification rate of 0.057 per cent and a false negative rate of 0.035 per cent on a gallery of 84 million, using ten fingerprints and two irises.
18. False match rate and false non-match rate trade along a curve, so choosing a threshold means choosing a ratio between two harms falling on different people, which makes it policy.
19. Merging destroys field provenance, the losing record’s identity and the attribution of later transactions, which is why the IHE framework states that an A40 merge is not reversible.
20. Build clusters as withdrawable assertions over untouched source records, store the evidence and threshold with each assertion, stamp downstream rows with the member identifier, and unmerge becomes an operation instead of a project.

Chapter sources: Fellegi and Sunter, “A Theory for Record Linkage”, Journal of the American Statistical Association, volume 64, issue 328, pages 1183 to 1210, December 1969; Newcombe and colleagues, “Automatic Linkage of Vital Records”, Science, volume 130, issue 3381, pages 954 to 959, October 1959; Levenshtein, Doklady Akademii Nauk SSSR, volume 163, number 4, pages 845 to 848, 1965, translated in Soviet Physics Doklady, volume 10, number 8, pages 707 to 710, 1966; Wagner and Fischer, Journal of the ACM, volume 21, issue 1, pages 168 to 173, 1974; Damerau, Communications of the ACM, volume 7, issue 3, pages 171 to 176, March 1964; Jaro, “Advances in Record-Linkage Methodology as Applied to Matching the 1985 Census of Tampa, Florida”, Journal of the American Statistical Association, 1 June 1989, pages 414 to 420; Winkler, “String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage”, ERIC ED325505, 1990; Russell, United States patents 1,261,167 of 2 April 1918 and 1,435,663 of 14 November 1922, with the coding rules published by the United States National Archives; the NYSIIS algorithm of 1970; Mokotoff and Daitch, Daitch-Mokotoff Soundex, 1985; Philips, Metaphone, Computer Language volume 7 number 12, December 1990, Double Metaphone in the C/C++ Users Journal of June 2000, and Metaphone 3 of October 2009; ISO/IEC 19795-1:2021, “Biometric performance testing and reporting - Part 1: Principles and framework”, second edition, 27 May 2021, and ISO/IEC 19795-10:2024 for demographic differentials; the NIST Face Recognition Technology Evaluation 1:N identification results page as last updated 4 August 2026; NIST Interagency Report 8034, “Fingerprint Vendor Technology Evaluation”, 8 January 2015; NIST Interagency Report 8280, “Face Recognition Vendor Test Part 3: Demographic Effects”, Grother, Ngan and Hanaoka, 19 December 2019; UIDAI, “Role of Biometric Technology in Aadhaar Enrolment”, 31 December 2011, and the UIDAI Aadhaar dashboard as displayed in August 2026; the IHE IT Infrastructure Technical Framework, Volume 2 section 3.8.4.2.4 on the Patient Identity Feed and HL7 version 2 trigger event A40, Volume 1 at revision 20.2 of 11 November 2025; Bipartisan Policy Center, “Looking for a Perfect Match: Challenges and Strategies for Matching Patients’ Scattered Health Data”, June 2012; The Pew Charitable Trusts, “Enhanced Patient Matching Is Critical to Achieving Full Promise of Digital Health Records”, 2 October 2018; the Splink documentation of the Ministry of Justice Analytical Services for the log-odds form of the Fellegi-Sunter model; and the United States Department of Justice Office of the Inspector General review of the FBI’s handling of the Brandon Mayfield case, arising from the Madrid bombings of 11 March 2004.