Entity Resolution & Record Linkage: Fuzzy Matching, Splink & Dedupe at Scale

entity resolution is the problem you hit the moment two systems have to agree on who someone is without sharing an ID. One database calls her "Jonathan A. Smith," the billing system has "Jon Smith," the support tool typed "Jonathon Smyth," and a CSV upload spelled the street "Ave" where the CRM wrote "Avenue." No foreign key joins those rows, yet every one of them is the same customer, and the business will make wrong revenue, wrong shipping, and wrong compliance decisions until you decide they are. That decision — collapsing many noisy records into one real-world entity — is what entity resolution does, and it is far more common in day-to-day data engineering than the tidy JOIN … ON id most tutorials assume.

This guide walks the whole discipline end to end, the way you would actually build it and the way interviewers actually probe it. It covers record linkage across sources that share no key, fuzzy matching with edit distance and token and phonetic similarity, the probabilistic deduplication math behind the Fellegi-Sunter model, and the tools — Splink and the dedupe library — that make it production-grade. Each stage pairs a teaching block with a worked example: the input records, real SQL or Python, a step-by-step trace of what the algorithm does, the output it produces, and a concept-by-concept breakdown of why it is the right approach. By the end you will be able to design an ER pipeline that turns a pile of duplicates into clean golden records, defend every stage under a precision-versus-recall constraint, and answer the scenario questions these systems generate in interviews.

When you want hands-on reps alongside the reading, drill string-similarity mechanics on the string-processing practice library →, rehearse pipeline design on the ETL practice library →, and sharpen matching logic on the pattern-matching practice library →.

---

On this page

• The entity-resolution problem & the ER pipeline
• Blocking & candidate generation — cutting the comparison space
• Similarity & fuzzy matching — edit distance, tokens & phonetics
• Probabilistic matching — Fellegi-Sunter, match weights & Splink
• Clustering & dedupe at scale — connected components
• Cheat sheet — Entity resolution recipes & reference
• Frequently asked questions
• Practice on PipeCode

---

1. The entity-resolution problem & the ER pipeline

Entity resolution is a precision/recall problem, not an equi-join

The framing that changes how you build everything downstream: entity resolution is the task of deciding which records refer to the same real-world entity when no shared identifier exists, and because the evidence is noisy, it is fundamentally a precision/recall trade-off rather than a boolean join. An equi-join answers "are these two keys byte-for-byte equal?" ER answers "given imperfect names, addresses, dates, and phones, is the probability these two rows are the same person high enough to merge them — accepting that too-eager merging creates false matches and too-cautious merging leaves duplicates behind?"

Why an exact join fails. The reasons duplicates survive an = comparison are boringly predictable, which is exactly why they are automatable.

• No shared key. The CRM has its own customer id, billing has another, a third-party list has none — nothing to join on.
• Typos and OCR noise. "Smith" / "Smtih" / "Smyth"; a scanned form reads "Rd" as "Pd".
• Formatting drift. "Ave" vs "Avenue", "St." vs "Street", "[phone]" vs "0770 900123", uppercase vs lowercase, trailing spaces.
• Nicknames and cultural name order. "Bob" for "Robert", "Jon" for "Jonathan", surname-first in some locales.
• Missing and partial values. One record has a date of birth, the other does not; one has an email, the other a phone.

The vocabulary, disambiguated. These terms overlap and interviewers like to hear you separate them cleanly.

• Entity resolution (ER). The umbrella term: figure out which records map to which real-world entities.
• Record linkage. ER across two or more datasets that lack a common key — classic in health, census, and fraud work (link hospital records to a death registry).
• Deduplication (dedupe). ER within a single dataset — collapse duplicate rows in one customer table.
• Master data management (MDM). The operational program that maintains the surviving "golden records" over time; ER is the engine inside it.

The standard ER pipeline — six stages every system has. Whether you hand-roll it or use Splink, the shape is the same, and naming the stages is half of a good interview answer.

• 1. Normalize / standardize. Lowercase, trim, expand abbreviations, parse names and addresses into components, cast dates to ISO. This is the single cheapest quality win.
• 2. Block / index. Generate candidate pairs cheaply so you never compare all pairs (the O(n²) killer). Covered in section 2.
• 3. Compare / score. For each candidate pair, compute per-field similarity — a comparison vector. Covered in section 3.
• 4. Classify. Turn the comparison vector into match / non-match / possible-match, via rules or a probabilistic model. Covered in section 4.
• 5. Cluster. Resolve the graph of pairwise matches into entities (transitive closure / connected components). Covered in section 5.
• 6. Canonicalize. Merge each cluster into one golden record with survivorship rules.

The two error axes you are always trading. Every ER knob moves one of these, usually at the expense of the other.

• Precision — of the pairs you called matches, how many really are? Low precision = false merges (two different people become one "customer").
• Recall — of the true matches, how many did you catch? Low recall = missed merges (the same person stays split into duplicates).
• The lever — a stricter threshold raises precision and lowers recall; a looser one does the reverse. There is no single "correct" setting, only the one your use case demands (fraud wants recall; billing merges want precision).

Worked example — why an exact join misses duplicates and normalization recovers them

Detailed explanation. The fastest way to feel the problem is to run an exact join on realistic messy data, watch it return almost nothing, then apply cheap normalization and watch matches reappear — while noticing the ones normalization still cannot catch (those are what sections 2–4 exist for). Normalization is deterministic string surgery: casefold, strip punctuation and whitespace, expand a small abbreviation dictionary, and split composite fields into parts.

• Casefold + trim — " John SMITH " and "john smith" collapse to the same token.
• Expand abbreviations — "Ave" -> "avenue", "St" -> "street", so address strings line up.
• Strip punctuation from phones — "[phone]" and "0770900123" become the same digits.
• What it cannot fix — "Smith" vs "Smyth", "Jon" vs "Jonathan" — those need fuzzy and phonetic matching, not normalization.

Question. Two customer records describe the same person. Show why an exact join returns zero matches and how normalization recovers the match on the fields it can.

Input.

Field	Record A (CRM)	Record B (Billing)
name	John SMITH	john smith
street	12 Oak Ave	12 Oak Avenue
phone	[phone]	0770900123
dob	1990-04-02	(missing)

Code.

import re

ABBREV = {"ave": "avenue", "st": "street", "rd": "road", "dr": "drive"}

def normalize_name(s: str) -> str:
    s = (s or "").strip().lower()
    s = re.sub(r"[^a-z ]", "", s)          # drop punctuation/digits
    return re.sub(r"\s+", " ", s).strip()  # collapse internal spaces

def normalize_street(s: str) -> str:
    s = (s or "").strip().lower()
    s = re.sub(r"[.,]", "", s)
    toks = [ABBREV.get(t, t) for t in s.split()]
    return " ".join(toks)

def normalize_phone(s: str) -> str:
    return re.sub(r"\D", "", s or "")      # keep digits only

A = {"name": "John SMITH", "street": "12 Oak Ave", "phone": "[phone]"}
B = {"name": "john smith ", "street": "12 Oak Avenue", "phone": "0770900123"}

exact = (A["name"] == B["name"], A["street"] == B["street"], A["phone"] == B["phone"])
norm  = (
    normalize_name(A["name"])   == normalize_name(B["name"]),
    normalize_street(A["street"]) == normalize_street(B["street"]),
    normalize_phone(A["phone"]) == normalize_phone(B["phone"]),
)
print("exact :", exact)   # (False, False, False)
print("norm  :", norm)    # (True, True, True)

Step-by-step trace.

1. The raw join compares "John SMITH" == "john smith " — different case and a trailing space — so it is False; all three fields fail and the join emits no pair.
2. normalize_name casefolds and collapses whitespace, so both names become "john smith" → equal.
3. normalize_street expands "ave" -> "avenue", so both streets become "12 oak avenue" → equal.
4. normalize_phone strips non-digits, so both phones become "0770900123" → equal.
5. The date of birth is missing in B, so it neither agrees nor disagrees — it simply carries no evidence (section 4 handles that formally).

Output:

Comparison	name	street	phone
Exact =	❌	❌	❌
After normalization	✅	✅	✅

Rule of thumb. Always normalize before you match — deterministic standardization is the cheapest recall you will ever buy, and it shrinks the work the fuzzy and probabilistic stages have to do.

---

2. Blocking & candidate generation — cutting the comparison space

Blocking is the stage that makes entity resolution tractable — never compare all pairs

The invariant to burn in: comparing every pair of records is O(n²) and impossible at any real scale, so blocking (a.k.a. indexing) groups records into blocks by a cheap key and only compares records that share a block — trading a small loss of recall for an enormous reduction in comparisons. One million records is ~500 billion pairs; a good blocking scheme turns that into tens of millions, which is the difference between a job that finishes and one that never does.

Why O(n²) is fatal. The number of unique pairs in n records is n·(n−1)/2. At 1M records that is ~5×10¹¹ comparisons; even at a microsecond each that is days of compute — and every pair still needs several expensive string-similarity calls. Blocking is not an optimization you add later; it is the load-bearing wall.

The core blocking methods.

• Standard blocking. Compute a blocking key per record (e.g. first 4 letters of surname + birth year, or Soundex(surname)), group by it, and compare only within each group. Simple, fast, the default.
• Phonetic blocking. Use a phonetic code (Soundex/Metaphone) as the key so "Smith" and "Smyth" land in the same block — recovers matches plain-prefix blocking would split.
• Sorted-neighborhood method (SNM). Sort all records by a key, then slide a fixed window of size w down the list and compare only records within the window. Records with slightly different keys still meet at the window boundary.
• Multi-pass / disjunctive blocking (canopies). Run several blocking passes with different keys (block on phone, then on email prefix, then on Soundex(name)+zip) and union the candidate pairs. A pair survives if any pass groups it — this is how you claw recall back.

The blocking trade-off you must name. Two metrics quantify a scheme, and interviewers love the tension between them.

• Reduction ratio (RR) — 1 − (pairs_after_blocking / total_pairs). Higher is cheaper. Blocking that produces a handful of pairs has RR near 1.
• Pair completeness (PC) — fraction of true-match pairs that survive blocking (blocking recall). A key that is too tight (e.g. exact full name) has high RR but drops true matches with typos in the key → low PC.
• The rule — you want high RR and high PC; a single tight key rarely gives both, which is exactly why multi-pass blocking exists.

Common traps to pre-empt.

• Blocking on a dirty field — if you block on surname and the surname has the typo, the true pair never shares a block. Block on something robust (phonetic code, or multiple keys).
• A key so coarse it barely reduces — blocking on country puts millions in one block; RR is near zero and you are back to O(n²) inside the block.
• Forgetting skew — one giant block (e.g. Soundex of a very common name) dominates runtime; cap or sub-block large blocks.
• Assuming one pass is enough — a single blocking key almost always sacrifices recall on the field it keys on; union multiple passes.

Standard blocking keys & the comparison-count math — a worked teaching example

Detailed explanation. The point of standard blocking is captured in one calculation: instead of C(n,2) comparisons over the whole dataset, you do Σ C(bᵢ,2) summed over blocks of size bᵢ, and because that sum is dominated by the squares of block sizes, many small blocks beat one big one dramatically. Choose a key with enough distinct values to make blocks small, but robust enough that true matches still collide.

• Key design — first4(surname) + birth_year gives many distinct values → small blocks.
• Comparisons after blocking — Σ bᵢ(bᵢ−1)/2; balanced small blocks minimize it.
• Reduction ratio — compare that sum to n(n−1)/2.
• Watch skew — if one block holds 40% of records, it alone dominates the sum.

Question. For 10,000 customer records, compare the all-pairs cost against blocking by Soundex(surname) when it yields 2,000 blocks averaging 5 records each. What is the reduction ratio?

Input.

Quantity	Value
Records n	10,000
All-pairs comparisons	n(n−1)/2
Blocks	2,000
Avg block size b	5

Code.

from collections import defaultdict
import jellyfish  # phonetic + string metrics

def block_key(rec):
    # robust phonetic key so "Smith"/"Smyth" collide
    return jellyfish.soundex(rec["surname"]) if rec.get("surname") else "_"

def candidate_pairs(records):
    blocks = defaultdict(list)
    for r in records:
        blocks[block_key(r)].append(r["id"])
    pairs = []
    for ids in blocks.values():
        for i in range(len(ids)):
            for j in range(i + 1, len(ids)):   # within-block pairs only
                pairs.append((ids[i], ids[j]))
    return pairs, blocks

n = 10_000
all_pairs = n * (n - 1) // 2                    # 49,995,000
blocked   = 2_000 * (5 * (5 - 1) // 2)          # 2000 * 10 = 20,000
reduction = 1 - blocked / all_pairs
print(all_pairs, blocked, round(reduction, 5)) # 49995000 20000 0.9996

Step-by-step trace.

1. All-pairs cost is 10000·9999/2 = 49,995,000 comparisons — the number blocking must avoid.
2. Each block of 5 contributes C(5,2) = 10 within-block pairs.
3. With 2,000 such blocks the candidate set is 2,000 × 10 = 20,000 pairs.
4. Reduction ratio = 1 − 20,000 / 49,995,000 ≈ 0.9996 — blocking removed 99.96% of the work.
5. The residual risk is pair completeness: any true match whose surnames Soundex-differ (rare, but real) is now unreachable — which motivates a second blocking pass on a different field.

Output:

Strategy	Comparisons	Reduction ratio
All pairs	49,995,000	0 (baseline)
Block by Soundex(surname)	20,000	~0.9996

Rule of thumb. Pick a blocking key with enough distinct values that blocks stay small (single digits to low hundreds), and make it phonetic or otherwise typo-robust so true pairs still share a block.

Sorted-neighborhood method — a worked teaching example

Detailed explanation. The sorted-neighborhood method (SNM) fixes standard blocking's brittle boundary: instead of hard buckets, it sorts records by a key and slides a window of size w, comparing every record with the w−1 records around it, so two records with slightly different keys still meet near the window edge. Its comparison count is roughly (w−1)·n — linear in n for a fixed window — and its recall depends on choosing a sort key where true matches sort close together.

• Sort key — a concatenation like surname + first_name (or a phonetic version) so near-duplicates are adjacent.
• Window w — larger w catches more true pairs (higher PC) but costs more comparisons.
• Cost — about (w−1)·(n − w/2) comparisons ≈ linear in n.
• Multi-pass SNM — sort by different keys on different passes and union, exactly like disjunctive blocking.

Question. Sort 8 records by a name key and generate candidate pairs with a sliding window of size w = 3. How many comparisons, and which true pair does the window catch that exact-key bucketing would miss?

Input.

Sorted position	Record	sort key
1	r-31	smith john
2	r-08	smith jon
3	r-55	smyth john
4	r-12	smythe joan
5	r-02	soto ana
6	r-77	soto anna
7	r-40	stone bea
8	r-19	stone ben

Code.

def sorted_neighborhood(records, key, w=3):
    ordered = sorted(records, key=key)
    pairs = []
    for i in range(len(ordered)):
        # compare record i with the next w-1 records inside the window
        for j in range(i + 1, min(i + w, len(ordered))):
            pairs.append((ordered[i]["id"], ordered[j]["id"]))
    return pairs

recs = [
    {"id": "r-31", "k": "smith john"}, {"id": "r-08", "k": "smith jon"},
    {"id": "r-55", "k": "smyth john"}, {"id": "r-12", "k": "smythe joan"},
    {"id": "r-02", "k": "soto ana"},  {"id": "r-77", "k": "soto anna"},
    {"id": "r-40", "k": "stone bea"}, {"id": "r-19", "k": "stone ben"},
]
pairs = sorted_neighborhood(recs, key=lambda r: r["k"], w=3)
print(len(pairs))   # 13

Step-by-step trace.

1. The records are already ordered by k; each record pairs with the next w−1 = 2 neighbors.
2. Positions 1–7 each emit 2 pairs and position 8 emits 0 (window runs off the end): 2×6 + 1 = 13 pairs total — linear, not quadratic.
3. The window over positions 1–3 pairs smith john↔smyth john, catching the "Smith"/"Smyth" typo pair that a hard exact-key bucket would have split into different blocks.
4. Increasing w to 4 would additionally reach smythe joan, raising pair completeness at the cost of more comparisons.

Output:

Window (positions)	Candidate pairs
1–3	(r-31,r-08), (r-31,r-55), (r-08,r-55)
2–4	(r-08,r-12), (r-55,r-12)
…	…
Total (w=3)	13

Rule of thumb. Use sorted-neighborhood when a single sort key lines up near-duplicates well; tune w up for recall, and run a second pass on a different sort key to catch pairs the first ordering separated.

Interview scenario on blocking a large deduplication job

You must deduplicate 20 million customer records nightly. A single blocking key on surname misses people whose surname was mistyped, but blocking on nothing is O(n²) and cannot finish. Design a blocking scheme that is both cheap (high reduction ratio) and high-recall (high pair completeness), and justify it.

Solution Using multi-pass (disjunctive) blocking with a candidate union

Answer choices (as an interviewer would frame them).

• A. Compare all pairs — correctness over speed.
• B. One blocking key: exact full name. Fast, simple.
• C. Multi-pass blocking: pass 1 Soundex(surname)+birth_year, pass 2 email_local_part, pass 3 phone_last7+zip3; union the candidate pairs, dedupe, then score.
• D. Block on country to keep it simple.

Code.

Elimination:
A  all pairs        -> 20M records = ~2e14 pairs, never finishes         [reject: O(n^2)]
B  exact full name  -> any typo in name drops the true pair (low PC)     [reject: recall]
D  block on country -> one giant block ~ back to O(n^2) inside it        [reject: no reduction]
C  disjunctive multi-pass -> high RR per pass, high PC via union         [ACCEPT]

Step-by-step trace.

1. Name the constraint: "20M nightly" demands high reduction ratio; "misses mistyped surnames" demands high pair completeness — you need both, so no single tight key suffices.
2. A is O(n²) and cannot run at 20M — eliminate on cost.
3. B keys on the very field that carries the typo, so a mistyped surname never shares a block — eliminate on recall.
4. D produces a handful of enormous blocks; comparisons inside one block are again O(block²) ≈ O(n²) — eliminate on no real reduction.
5. C runs three complementary passes: a phonetic-name+year pass catches misspelled surnames, an email pass catches people whose name changed but email did not, a phone+zip pass catches the rest; unioning the pairs means a true match survives if any pass groups it, maximizing PC while each pass keeps blocks small for high RR.

Output:

Requirement	Mechanism
Tractable at 20M	Small blocks per pass → high reduction ratio
Survive surname typos	Phonetic key + alternate passes on email/phone
High recall	Union of candidate pairs across passes
No monster block	Keys with many distinct values; sub-block if skewed

Why this works — concept by concept:

• Disjunctive coverage — unioning passes means a true pair only has to be caught by one blocking key, so a typo in the field one pass uses is rescued by another pass keyed on a different field.
• Phonetic robustness — a Soundex/Metaphone key makes the surname pass tolerant to the exact misspellings the scenario calls out, lifting pair completeness where exact keys fail.
• Reduction per pass — each key is chosen to have many distinct values, so every pass keeps blocks small and the per-pass reduction ratio near 1, keeping total candidates in the tens of millions rather than 10¹⁴.
• Cost — blocking is O(n) to key + hash-group per pass, and the number of passes is a small constant; total work is O(k·n + candidate_pairs), which is what makes a 20M nightly dedupe feasible at all.

SQL
Topic — optimization
Reducing the comparison space: join & scan optimization

Practice →

ETL Topic — etl Candidate-generation and pipeline-staging problems

Practice →

---

3. Similarity & fuzzy matching — edit distance, tokens & phonetics

Fuzzy matching turns each candidate pair into a comparison vector of per-field similarity scores

The invariant: for every candidate pair, the comparison stage produces a comparison vector — one similarity score per field — and the art is choosing the right metric per field, because typos, word-order differences, and sound-alikes each fail a different measure. A name typo wants character edit distance; a reordered multi-word address wants token/set similarity; a phonetically-spelled surname wants a phonetic code. Use the wrong metric and a true match scores low.

The three families of string similarity.

• Character edit distance. How many single-character edits turn one string into another. Levenshtein counts insertions, deletions, substitutions; Damerau-Levenshtein also counts transpositions; Jaro-Winkler is tuned for short strings (names), rewarding a common prefix and tolerating transpositions, returning a 0–1 similarity. Best for typos in a single token.
• Token / set similarity. Split strings into tokens (words) or character n-grams and compare sets. Jaccard = |A∩B| / |A∪B|; cosine/TF-IDF weights rare tokens more; trigram (q-gram) similarity uses overlapping 3-character shingles. Best for word-order and partial matches ("John A Smith" vs "Smith, John"; "12 Oak Ave Apt 3" vs "Apt 3, 12 Oak Avenue").
• Phonetic encoding. Map a string to a code representing how it sounds, so spelling variants collapse. Soundex is the classic (keeps first letter + 3 consonant digits); Metaphone/Double Metaphone is more accurate for English. Best for sound-alike surnames ("Smith"/"Smyth", "Catherine"/"Kathryn").

Turning scores into a decision. Fuzzy matching does not, by itself, decide "match." It produces the comparison vector; the classification stage (section 4) weights and thresholds it. But even a rules-based system uses these scores directly.

• Per-field thresholds — jaro_winkler(name) ≥ 0.9 AND jaccard(address_tokens) ≥ 0.6 AND phone_exact → match.
• Normalize each score to 0–1 so fields are comparable before weighting.
• Handle nulls explicitly — a missing field is neither agree nor disagree; do not score it 0 (that punishes the pair as if it disagreed).

Common traps.

• Using edit distance on multi-word fields — "John Smith" vs "Smith John" has a large Levenshtein distance despite being the same; use token similarity there.
• Using raw distance, not normalized similarity — a distance of 2 means different things for a 4-char vs 40-char string; normalize by length.
• Phonetic-only matching — Soundex is coarse ("Robert" and "Rupert" can collide); use it to block or as one signal, not as the sole decision.
• Scoring nulls as disagreement — silently tanks recall on sparse fields.

Levenshtein & Jaro-Winkler for typos — a worked teaching example

Detailed explanation. Levenshtein distance is computed with a classic dynamic-programming table where cell (i,j) holds the edit distance between the first i characters of one string and first j of the other; you normalize it to a 0–1 similarity by 1 − distance/max_len. Jaro-Winkler is purpose-built for short person-names: it scores matching characters within a sliding window, penalizes transpositions, and adds a bonus for a shared prefix, so "Jonathan"/"Johnathon" scores high even though its Levenshtein distance is nonzero.

• Levenshtein — count insert/delete/substitute edits; DP is O(m·n) time.
• Normalized similarity — 1 − dist / max(len_a, len_b) to compare across lengths.
• Jaro-Winkler — window-matched chars, transposition penalty, prefix bonus; 1.0 = identical.
• When each wins — Levenshtein for general typos; Jaro-Winkler tuned for names/short strings.

Question. Score "Jonathan" vs "Johnathon" with normalized Levenshtein and with Jaro-Winkler; which better reflects that these are the same name?

Input.

Field	Value A	Value B
first_name	Jonathan	Johnathon
length	8	9

Code.

import jellyfish

def levenshtein_dp(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,        # deletion
                dp[i][j - 1] + 1,        # insertion
                dp[i - 1][j - 1] + cost, # substitution
            )
    return dp[m][n]

a, b = "Jonathan", "Johnathon"
dist = levenshtein_dp(a, b)                        # 3
lev_sim = 1 - dist / max(len(a), len(b))           # 1 - 3/9 = 0.667
jw = jellyfish.jaro_winkler_similarity(a, b)       # ~0.91
print(dist, round(lev_sim, 3), round(jw, 3))       # 3 0.667 0.91

Step-by-step trace.

1. The DP table fills so that dp[8][9] = 3: "Jonathan"→"Johnathon" needs to insert an h, substitute a→o, and adjust the tail — three edits.
2. Normalized Levenshtein similarity is 1 − 3/9 ≈ 0.667 — moderate, and arguably too low to trust alone for a name.
3. Jaro-Winkler matches most characters within its window, applies a small transposition penalty, and adds a prefix bonus for the shared "John…"/"Jon…" start, yielding ≈ 0.91.
4. Jaro-Winkler's higher score better reflects reality: these are the same name with an insertion, and its prefix bonus is exactly the signal that person-names rarely differ at the start.

Output:

Metric	Score	Reads as
Levenshtein distance	3	3 edits
Normalized Levenshtein	0.667	"somewhat similar"
Jaro-Winkler	~0.91	"very likely same name"

Rule of thumb. For person-name fields, prefer Jaro-Winkler (or Damerau-Levenshtein) over plain normalized Levenshtein — the prefix bonus and transposition handling match how names actually vary.

Jaccard/trigram tokens & Soundex/Metaphone phonetics — a worked teaching example

Detailed explanation. For multi-word fields and sound-alikes, character edit distance is the wrong tool; you switch to set similarity and phonetic codes. Jaccard over word tokens ignores order, so "Smith, John A" and "John Smith" overlap heavily; trigram (3-character shingle) Jaccard catches partial-word typos too. In parallel, Soundex/Metaphone reduce a surname to a sound code so "Smith" and "Smyth" hash to the same value, giving a binary phonetic-agreement signal you fold into the comparison vector.

• Token Jaccard — |A∩B| / |A∪B| over word sets; order-independent.
• Trigram Jaccard — same formula over overlapping 3-grams; tolerant to one-letter typos.
• Soundex/Metaphone — encode-then-equate; a boolean "sounds the same" feature.
• Combine — one comparison vector cell per signal, not a single blended number too early.

Question. Compare "John A Smith" vs "Smith John" with token Jaccard, and "Smith" vs "Smyth" with Soundex and Metaphone. What does the comparison vector look like?

Input.

Field	Value A	Value B
full_name	John A Smith	Smith John
surname	Smith	Smyth

Code.

import jellyfish

def token_jaccard(a: str, b: str) -> float:
    sa, sb = set(a.lower().split()), set(b.lower().split())
    return len(sa & sb) / len(sa | sb) if (sa | sb) else 0.0

def trigrams(s: str):
    s = f"  {s.lower()} "
    return {s[i:i+3] for i in range(len(s) - 2)}

def trigram_jaccard(a: str, b: str) -> float:
    ta, tb = trigrams(a), trigrams(b)
    return len(ta & tb) / len(ta | tb) if (ta | tb) else 0.0

jac   = token_jaccard("John A Smith", "Smith John")   # {john,smith} shared, {a} extra
tri   = trigram_jaccard("Smith", "Smyth")
sx_eq = jellyfish.soundex("Smith") == jellyfish.soundex("Smyth")   # S530 == S530 -> True
mp_eq = jellyfish.metaphone("Smith") == jellyfish.metaphone("Smyth")
print(round(jac, 3), round(tri, 3), sx_eq, mp_eq)     # 0.667 ~0.44 True True

Step-by-step trace.

1. Tokenizing gives A={john, a, smith}, B={smith, john}; intersection {john, smith} = 2, union {john, a, smith} = 3, so token Jaccard = 2/3 ≈ 0.667 — high despite the reversed order and the extra middle initial.
2. Trigram Jaccard on "Smith"/"Smyth" shares shingles like smi? no — it shares the framing and th shingles, giving a partial score ~0.44, flagging them as similar-but-not-identical strings.
3. Soundex("Smith") and Soundex("Smyth") both encode to S530, so the phonetic-agreement feature is True.
4. Metaphone also equates them, corroborating the sound-alike signal; the vector now carries three independent pieces of evidence instead of one blurred number.

Output:

Comparison feature	Value
token Jaccard (full_name)	0.667
trigram Jaccard (surname)	~0.44
Soundex agrees (surname)	True
Metaphone agrees (surname)	True

Rule of thumb. Use token/trigram Jaccard for multi-word and reordered fields and a phonetic code for surnames; keep each signal as its own comparison-vector cell so the classifier can weight them independently.

Interview scenario on choosing a similarity metric

You are matching two records: A = {name: "Robert J. Williams", address: "48 King St", dob: "1985-06-11"} and B = {name: "Bob Williams", address: "48 King Street, Apt 2", dob: "1985-06-11"}. A single Levenshtein distance on the concatenated record scores them "far apart." Design a per-field similarity scheme that correctly recognizes them as a likely match, and explain each choice.

Solution Using a weighted composite score over per-field metrics

Answer choices.

• A. One Levenshtein distance over the whole concatenated record string.
• B. Per-field metrics — Jaro-Winkler + nickname map on name, token Jaccard on address, exact on dob — combined into a weighted composite score.
• C. Soundex on everything and match if any code agrees.
• D. Exact match on all fields.

Code.

Elimination:
A  whole-string Levenshtein -> "Robert J. Williams" vs "Bob Williams" far  [reject: wrong metric]
C  Soundex-only, any-agree  -> too coarse, high false-match rate           [reject: precision]
D  exact all fields         -> fails on Bob/Robert, St/Street, Apt         [reject: recall]
B  per-field metrics + weighted composite                                  [ACCEPT]

Step-by-step trace.

1. Constraint: name differs by nickname (Bob/Robert) and middle initial, address differs by abbreviation and an apartment suffix, dob is identical — different fields need different metrics.
2. A concatenates then edit-distances, so word-order and nickname differences dominate the score — eliminate (wrong metric for multi-field, multi-word data).
3. C uses only phonetics with an any-agree rule, which is far too loose and will merge unrelated people — eliminate on precision.
4. D demands exact equality and dies on Bob≠Robert, St≠Street, the apartment suffix — eliminate on recall.
5. B scores each field with its right metric: a nickname lookup plus Jaro-Winkler makes Bob Williams/Robert J. Williams agree on surname and resolve the given name; token Jaccard makes the two addresses overlap on {48, king, street}; dob matches exactly; a weighted sum (dob and name weighted heavily) clears the match threshold.

Output:

Field	Metric	Score
name	nickname map + Jaro-Winkler	~0.92
address	token Jaccard (normalized)	~0.6
dob	exact	1.0
Composite (weighted)	—	above match threshold

Why this works — concept by concept:

• Right metric per field — names get Jaro-Winkler + a nickname dictionary, multi-word addresses get token Jaccard, and identifiers get exact match, so each field's true agreement is measured rather than blurred by one global distance.
• Nickname/synonym normalization — mapping Bob→Robert before comparison turns a spurious mismatch into an agreement, recovering recall that no character metric could.
• Weighted composite — weighting high-discriminating fields (dob, surname) above low-discriminating ones (a common first name) is a hand-rolled preview of the Fellegi-Sunter weights section 4 learns automatically.
• Cost — per-field scoring runs only on the blocked candidate pairs, and each metric is O(field_length) or a dictionary lookup, so the composite is cheap precisely because blocking already shrank the pair set.

Strings
Topic — string-processing
Edit distance and string-similarity problems

Practice →

Matching Topic — pattern-matching Fuzzy-matching and pattern-matching problems

Practice →

---

4. Probabilistic matching — Fellegi-Sunter, match weights & Splink

Probabilistic matching learns how much each field's agreement is worth instead of guessing weights

The invariant: the Fellegi-Sunter model scores a pair by summing, across fields, a match weight log2(m/u) — where m is the probability a field agrees given the pair is a true match and u is the probability it agrees by chance — so that agreeing on a rare, discriminating field (email) is worth far more than agreeing on a common one (first name = "John"), and two thresholds split the summed score into match / possible-match / non-match. Hand-picked weights are fragile; Fellegi-Sunter derives them from the data, and Splink estimates them without labeled training data using the EM algorithm.

Why a fixed threshold on a hand-weighted sum breaks. If you hand-weight "name agreement = 3, dob agreement = 5" you have implicitly guessed how discriminating each field is. But agreement on first_name = "John" is weak evidence (lots of Johns) while agreement on first_name = "Ignatius" is strong; a fixed weight cannot express that, and it certainly cannot be re-derived when your data changes. Probabilistic matching replaces guesses with estimated probabilities.

The Fellegi-Sunter quantities, defined.

• m-probability (m) — P(field agrees | pair is a true match). High for reliable fields (a correct dob agrees ~0.95 of the time even among true matches, allowing for typos).
• u-probability (u) — P(field agrees | pair is NOT a match) ≈ the chance of coincidental agreement. For dob, u ≈ 1/365-ish (tiny); for first_name, u is much larger (many share a name).
• Agreement weight — when a field agrees, add log2(m/u). Small u (rare coincidental agreement) → large positive weight.
• Disagreement weight — when a field disagrees, add log2((1−m)/(1−u)), which is negative (disagreement is evidence against a match).
• Total match score — sum the per-field weights; a higher score = more evidence the pair matches.

Two thresholds, three outcomes. Fellegi-Sunter is explicitly three-way, which is a feature interviewers look for.

• Above the upper threshold → match (auto-merge).
• Below the lower threshold → non-match (leave separate).
• In between → possible match → send to human clerical review (or a stricter secondary rule).

Estimating m and u without labels — the EM algorithm. You rarely have a labeled set of true matches, so you cannot count m and u directly. The Expectation-Maximization (EM) algorithm treats "is this pair a match?" as a hidden variable and iterates: (E) given current m/u, estimate each pair's match probability; (M) given those probabilities, re-estimate m/u. Repeat to convergence. u can also be estimated cheaply by random sampling (two random records are almost never a match, so their agreement rate ≈ u).

Splink — Fellegi-Sunter, productionized. Splink is an open-source library (from the UK Ministry of Justice) that implements Fellegi-Sunter at scale on DuckDB, Spark, or Athena.

• Comparisons & comparison levels — per field you define levels (exact / near via Jaro-Winkler ≥ 0.9 / else), each with its own m/u.
• Blocking rules — Splink blocks candidate pairs with SQL-like rules you supply (mirrors section 2).
• Training — estimate_u_using_random_sampling for u; estimate_parameters_using_expectation_maximisation for m (and refines u).
• Predict & cluster — predict() returns pairwise match probabilities; cluster_pairwise_predictions_at_threshold() runs connected components (section 5).

Fellegi-Sunter match-weight computation — a worked teaching example

Detailed explanation. The core Fellegi-Sunter calculation is small enough to do by hand, and doing it once makes the whole model click: for each field you know m and u, you add log2(m/u) when it agrees and log2((1−m)/(1−u)) when it disagrees, then sum. The magic is that a small u (coincidental agreement is rare) produces a big positive weight, so agreeing on email swamps agreeing on a common first name.

• Agreement weight — log2(m/u); larger when u is small (discriminating field).
• Disagreement weight — log2((1−m)/(1−u)); negative, penalizing mismatch.
• Sum across fields — independence assumption keeps it a simple sum of log-weights.
• Compare to thresholds — the summed score maps to match / possible / non-match.

Question. A pair agrees on email and dob but disagrees on first_name. Given the m/u below, compute the total match weight and classify it against an upper threshold of +6 and lower of −4.

Input.

Field	Agrees?	m	u
email	yes	0.90	0.0005
dob	yes	0.95	0.003
first_name	no	0.85	0.02

Code.

import math

def agreement_weight(m, u):     # field agrees
    return math.log2(m / u)

def disagreement_weight(m, u):  # field disagrees
    return math.log2((1 - m) / (1 - u))

w_email = agreement_weight(0.90, 0.0005)      # log2(1800)   ~ +10.81
w_dob   = agreement_weight(0.95, 0.003)       # log2(316.7)  ~  +8.31
w_name  = disagreement_weight(0.85, 0.02)     # log2(0.153)  ~  -2.71

total = w_email + w_dob + w_name              # ~ +16.41
print(round(w_email, 2), round(w_dob, 2), round(w_name, 2), round(total, 2))
# 10.81 8.31 -2.71 16.41

Step-by-step trace.

1. Email agrees and its u is tiny (0.0005 — two random people almost never share an email), so log2(0.90/0.0005) = log2(1800) ≈ +10.81 — a huge positive vote.
2. Dob agrees with u ≈ 0.003, giving log2(0.95/0.003) = log2(316.7) ≈ +8.31 — another strong positive.
3. First name disagrees, so it contributes log2((1−0.85)/(1−0.02)) = log2(0.153) ≈ −2.71 — a modest penalty, small because name disagreement among true matches is not that rare (people mistype, use nicknames).
4. The sum is 10.81 + 8.31 − 2.71 ≈ +16.41, far above the +6 upper threshold → classify as match, because two rare-agreement fields overwhelm one common-field disagreement.

Output:

Field	Weight
email (agree)	+10.81
dob (agree)	+8.31
first_name (disagree)	−2.71
Total	+16.41 → match

Rule of thumb. Agreement on a low-u (rare, discriminating) field is worth far more than agreement on a common one; that asymmetry is the whole reason probabilistic matching beats a hand-weighted sum.

A Splink model, end to end — a worked teaching example

Detailed explanation. Splink turns the Fellegi-Sunter math above into a few configuration objects: you declare link_type (dedupe one table or link two), the blocking rules that generate candidate pairs, and a comparisons list where each field defines comparison levels (exact / fuzzy / else). You then let Splink estimate u by random sampling and m by EM — no labels required — before predict() returns pairwise match probabilities you threshold and cluster.

• link_type — dedupe_only (one table) or link_only/link_and_dedupe (two+ tables) — this is your record-linkage vs dedupe switch.
• Blocking rules — SQL predicates that generate comparisons (e.g. same dob, or same Soundex(surname)).
• Comparisons — per-field levels with library helpers (jaro_winkler_at_thresholds), each level carrying an m/u.
• Train → predict → cluster — estimate u by sampling, m by EM, then predict() and cluster_pairwise_predictions_at_threshold().

Question. Configure a Splink model to deduplicate a customers table on first_name, surname, dob, and email, train it without labels, and produce clusters at a 0.95 probability threshold.

Input.

Config choice	Value
link_type	dedupe_only
Blocking rules	l.dob = r.dob; l.surname = r.surname
Fuzzy fields	first_name, surname (Jaro-Winkler); email (exact/near)
Cluster threshold	0.95 match probability

Code.

from splink.duckdb.linker import DuckDBLinker
import splink.duckdb.comparison_library as cl

settings = {
    "link_type": "dedupe_only",
    # Blocking: only compare pairs sharing dob OR surname (union of two rules)
    "blocking_rules_to_generate_predictions": [
        "l.dob = r.dob",
        "l.surname = r.surname",
    ],
    # Per-field comparison levels -> each level gets its own m/u
    "comparisons": [
        cl.jaro_winkler_at_thresholds("first_name", [0.9, 0.7]),
        cl.jaro_winkler_at_thresholds("surname",    [0.9, 0.7]),
        cl.exact_match("dob"),
        cl.exact_match("email", term_frequency_adjustments=True),
    ],
}

linker = DuckDBLinker(df_customers, settings)

# 1) Estimate u (coincidental agreement) by sampling random non-match pairs
linker.estimate_u_using_random_sampling(max_pairs=1e6)

# 2) Estimate m via EM, using a blocking rule to build the training pairs
linker.estimate_parameters_using_expectation_maximisation("l.dob = r.dob")
linker.estimate_parameters_using_expectation_maximisation("l.surname = r.surname")

# 3) Predict pairwise match probabilities, then cluster into entities
pairs = linker.predict(threshold_match_probability=0.9)
clusters = linker.cluster_pairwise_predictions_at_threshold(pairs, threshold_match_probability=0.95)

Step-by-step trace.

1. The two blocking rules generate candidate pairs from records that share a dob or a surname — a disjunctive block that keeps the comparison set small while covering typo'd names via the dob rule.
2. estimate_u_using_random_sampling draws random pairs (almost all non-matches) and measures how often each comparison level agrees by chance → the u probabilities.
3. estimate_parameters_using_expectation_maximisation runs EM over the blocked pairs to learn the m probabilities (how often each level agrees among true matches) without any labels.
4. predict() sums the learned Fellegi-Sunter weights per pair into a match probability and keeps pairs above 0.9.
5. cluster_pairwise_predictions_at_threshold(..., 0.95) runs connected components over the ≥0.95 edges, emitting a stable cluster_id per resolved entity.

Output:

Stage	Result
Blocking	candidate pairs (share dob or surname)
u estimation	coincidental-agreement rates per level
EM (m)	true-match agreement rates per level
predict → cluster	pairwise probabilities → cluster_id per entity

Rule of thumb. Let Splink estimate u by sampling and m by EM rather than hand-setting weights; choose blocking rules that are a disjunction so a typo in one field is covered by another.

Interview scenario on linking two datasets with no shared key

You must link a 5-million-row CRM table to a 4-million-row billing table. There is no common customer id; both have name, address, dob, and email of varying completeness. You have no labeled matches. Design a matching approach that produces calibrated, thresholdable match scores and justify why it beats deterministic rules.

Solution Using a Splink probabilistic (Fellegi-Sunter) linkage model

Answer choices.

• A. Deterministic rule: match if name AND dob are exactly equal.
• B. Fuzzy-only: match if jaro_winkler(name) ≥ 0.9, no probabilities.
• C. Splink Fellegi-Sunter model: link_only, disjunctive blocking, comparison levels per field, EM-estimated m/u, threshold + cluster.
• D. Train a supervised classifier on the labeled matches.

Code.

Elimination:
A  exact name+dob            -> typos/nicknames/missing dob drop true links  [reject: recall]
B  fuzzy name only, no probs -> one field, no calibration, no rare-field wgt [reject: precision]
D  supervised classifier     -> requires labeled matches you do not have     [reject: no labels]
C  Splink Fellegi-Sunter (link_only) + EM                                     [ACCEPT]

Step-by-step trace.

1. Constraint: two tables, no shared key (→ link_only record linkage), no labels (→ unsupervised), varying completeness (→ need per-field weighting and null handling), and "calibrated thresholdable scores" (→ probabilistic, not rule-based).
2. A is deterministic exact-match: any nickname, typo, or missing dob silently drops a true link — eliminate on recall.
3. B uses a single fuzzy field with no probability calibration and cannot express that email-agreement is worth more than name-agreement — eliminate on precision and calibration.
4. D needs labeled training pairs, which the scenario explicitly lacks — eliminate (no labels).
5. C fits Splink in link_only mode: disjunctive blocking rules generate candidates across the two tables, comparison levels capture exact/fuzzy agreement per field, u comes from random sampling and m from EM (no labels), and predict() yields calibrated per-pair match probabilities you can threshold and hand off to clustering — precisely the calibrated, unsupervised, multi-field solution the constraints demand.

Output:

Requirement	Mechanism
No shared key, two tables	Splink link_only
No labels	EM for m, sampling for u
Varying completeness	Per-field comparison levels + null handling
Calibrated thresholds	Fellegi-Sunter match probabilities

Why this works — concept by concept:

• Record linkage without a key — link_only compares across the two sources on evidence, not identifiers, which is the entire point when no common id exists.
• Unsupervised weight learning — EM estimates m and random sampling estimates u, so the model calibrates itself from the data instead of needing labeled matches the scenario does not have.
• Discriminating-field weighting — Fellegi-Sunter automatically makes email-agreement worth more than name-agreement via log2(m/u), giving precision that a single-field fuzzy rule cannot.
• Cost — blocking bounds the pairs to compare, EM converges in a handful of passes over that bounded set, and prediction is a linear scan, so a 5M×4M linkage runs in the blocked-pair budget rather than the 2×10¹³ full cross-product.

Matching
Topic — pattern-matching
Probabilistic matching and scoring problems

Practice →

Design Topic — design Record-linkage system design problems

Practice →

---

5. Clustering & dedupe at scale — connected components

Pairwise matches are graph edges — clustering resolves them into entities, then survivorship builds golden records

The invariant: the matcher outputs pairwise decisions, but an entity can span many records, so you treat records as nodes and matches as edges and compute connected components (transitive closure) to group them — then collapse each component into one golden record with survivorship rules, being careful that transitivity can chain weak links into wrong merges. Clustering is where pairwise probability becomes an actual deduplicated entity, and it is where large-scale ER lives or dies on the choice of algorithm.

The transitivity problem you must call out. If A matches B and B matches C, connected components will put A, B, and C in one cluster — even if A and C were never directly compared, or were compared and did not match. This is both a feature (it links records via intermediaries) and a hazard (a single bad edge can merge two distinct people).

• The upside — chains recover matches you never directly scored (A–C via B).
• The hazard — one false-positive edge silently merges two real entities ("over-merging").
• The mitigations — raise the clustering threshold above the pairwise threshold; use stricter graph clustering (e.g. remove low-weight edges, require higher connectivity) instead of naive connected components; cap cluster size and flag giant clusters for review.

Clustering algorithms, from simplest to safest.

• Connected components (union-find). Merge any records joined by an edge above threshold. Fast (~O(edges·α) with union-find), but maximally transitive → most prone to over-merging.
• Threshold tuning. Cluster only on high-probability edges (e.g. ≥0.95) even if you predicted at ≥0.9, so weak edges do not chain clusters together.
• Stricter graph clustering — algorithms that require dense connectivity (not just a single connecting edge) resist chaining; Splink offers higher-threshold clustering for exactly this.

Canonicalization / survivorship — building the golden record. Once a cluster is fixed, you merge its records into one. Survivorship rules decide which value wins per field.

• Most recent — take the value from the record with the latest updated_at (good for addresses, phones).
• Most complete / longest — prefer the non-null, most detailed value (full name over an initial).
• Highest source trust — a ranked source priority (verified billing > scraped list).
• Most frequent — majority vote across the cluster for a field.
• Keep provenance — store which source each surviving value came from; MDM and audits need it.

Big-data ER — doing all of this at hundreds of millions of rows.

• Splink on Spark — the same Fellegi-Sunter model with the Spark backend; blocking becomes a Spark join, prediction a distributed scan, and clustering a distributed connected-components job (GraphFrames).
• Partition by block — parallelize comparison by shipping each block to a partition; skewed giant blocks must be salted/sub-blocked or they bottleneck one executor.
• The dedupe library — a Python option that uses active learning (it asks a human to label a few uncertain pairs) to train weights; great for smaller/medium dedupe where you can label a bit.
• Connected components at scale — Spark GraphFrames connectedComponents() or an iterative label-propagation join is the standard distributed clustering primitive.

Interview signals — what a senior answer includes. When asked to "dedupe customers at scale," strong candidates name: (1) blocking to avoid O(n²), (2) a probabilistic matcher with learned weights, (3) connected-components clustering with a note about the transitivity/over-merge risk, (4) survivorship rules for the golden record, and (5) the precision/recall lever and how they would evaluate it without labels. Weak answers jump straight to "fuzzy match everything."

Connected components over match pairs — a worked teaching example

Detailed explanation. Given a set of pairwise matches, the job is to find groups where every record is connected to the others directly or transitively — the connected components of the match graph — and union-find (disjoint-set) is the classic near-linear algorithm: find returns a set's representative, union merges two sets, and path compression keeps it fast. The output is a cluster_id (the representative) per record.

• Nodes — the records; edges — the pairwise matches above the clustering threshold.
• union(a, b) — merge the two records' sets.
• find(x) — the set representative, with path compression.
• Result — records sharing a representative form one entity.

Question. Given match pairs (1,2), (2,3), (4,5) over records 1..6, compute the connected components (clusters). Note the transitive 1–3 link that was never directly matched.

Input.

Match pair	Interpretation
(1, 2)	record 1 ↔ record 2
(2, 3)	record 2 ↔ record 3
(4, 5)	record 4 ↔ record 5
record 6	no matches (singleton)

Code.

def find(parent, x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # path compression
        x = parent[x]
    return x

def union(parent, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra != rb:
        parent[rb] = ra                 # merge b's set into a's

def connected_components(ids, pairs):
    parent = {i: i for i in ids}        # each record starts as its own set
    for a, b in pairs:
        union(parent, a, b)
    clusters = {}
    for i in ids:
        clusters.setdefault(find(parent, i), []).append(i)
    return list(clusters.values())

ids   = [1, 2, 3, 4, 5, 6]
pairs = [(1, 2), (2, 3), (4, 5)]
print(connected_components(ids, pairs))   # [[1, 2, 3], [4, 5], [6]]

Step-by-step trace.

1. Start with every record its own set: {1}{2}{3}{4}{5}{6}.
2. union(1,2) merges to {1,2}; union(2,3) finds 2's representative (1) and merges 3 → {1,2,3} — record 3 is now linked to record 1 transitively, through 2, though 1 and 3 were never directly compared.
3. union(4,5) merges {4,5}; record 6 has no edges and stays a singleton.
4. Grouping by representative yields three clusters — each becomes one entity for canonicalization.

Output:

cluster_id (rep)	Records	Note
1	1, 2, 3	1–3 linked transitively via 2
4	4, 5	direct match
6	6	singleton, no duplicates

Rule of thumb. Cluster with union-find for speed, but set the clustering threshold higher than the pairwise threshold so a single weak edge cannot chain two entities into one over-merged cluster.

Survivorship / golden-record construction — a worked teaching example

Detailed explanation. After clustering, canonicalization applies per-field survivorship rules to collapse a cluster into one master record: pick the freshest value for volatile fields, the most complete value for descriptive fields, and the highest-trust source when sources conflict — and retain provenance so you can audit which record supplied each field. The rules are field-specific by design; there is no single "best record," only the best value per field.

• Recency — latest updated_at wins for address/phone/email.
• Completeness — longest non-null wins for name (full over initial).
• Source trust — a ranked priority breaks ties.
• Provenance — record the winning value's source id per field.

Question. Merge a 3-record cluster into one golden record using recency for contact fields, completeness for name, and source-trust billing > crm > list.

Input.

record	source	updated_at	name	email	phone
r1	crm	2024-01-10	J Smith	[e-mail]	(null)
r2	billing	2026-07-01	Jonathan Smith	(null)	0770900123
r3	list	2023-05-02	Jon Smith	[e-mail]	0770900000

Code.

SOURCE_TRUST = {"billing": 3, "crm": 2, "list": 1}

def golden_record(cluster):
    def most_recent(field):
        cand = [r for r in cluster if r.get(field)]
        return max(cand, key=lambda r: r["updated_at"])[field] if cand else None

    def most_complete(field):
        cand = [r for r in cluster if r.get(field)]
        return max(cand, key=lambda r: len(r[field]))[field] if cand else None

    def highest_trust(field):
        cand = [r for r in cluster if r.get(field)]
        return max(cand, key=lambda r: SOURCE_TRUST[r["source"]])[field] if cand else None

    return {
        "name":  most_complete("name"),    # longest non-null
        "email": most_recent("email"),     # freshest contact
        "phone": highest_trust("phone"),   # trust billing over list
    }

cluster = [
    {"source": "crm",     "updated_at": "2024-01-10", "name": "J Smith",        "email": "[e-mail]",   "phone": None},
    {"source": "billing", "updated_at": "2026-07-01", "name": "Jonathan Smith", "email": None,        "phone": "0770900123"},
    {"source": "list",    "updated_at": "2023-05-02", "name": "Jon Smith",      "email": "[e-mail]", "phone": "0770900000"},
]
print(golden_record(cluster))
# {'name': 'Jonathan Smith', 'email': '[e-mail]', 'phone': '0770900123'}

Step-by-step trace.

1. name — the completeness rule compares non-null names by length: "Jonathan Smith" (14) beats "Jon Smith" (9) and "J Smith" (7) → "Jonathan Smith".
2. email — the recency rule looks only at records with a non-null email: r1 (crm, 2024-01-10) and r3 (list, 2023-05-02). max by updated_at picks the later date, 2024-01-10 → r1's [e-mail].
3. phone — the trust rule compares sources among non-null phones: r2 (billing, trust 3) beats r3 (list, trust 1) → 0770900123.
4. Each field is resolved independently, so the golden record is a composite — no single input row equals it, which is exactly what survivorship is meant to produce.

Output:

Field	Rule	Winning value	From
name	most complete	Jonathan Smith	billing (r2)
email	most recent non-null	[e-mail]	crm (r1)
phone	highest source trust	0770900123	billing (r2)

Rule of thumb. Survivorship is per-field, not per-record: choose recency for volatile contact data, completeness for descriptive fields, and a source-trust ranking to break ties — and always keep provenance.

Interview scenario on end-to-end dedupe at scale

You have ~50 million customer records spread across three systems (CRM, billing, a marketing list), no shared key, and you must produce one deduplicated set of golden customer records on a nightly Spark job. Design the full pipeline and defend the clustering choice against over-merging.

Solution Using Spark blocking → Splink → connected components → canonicalization

Answer choices.

• A. Cross-join all three tables and fuzzy-match every pair on Spark.
• B. Exact-match on name+dob only, then keep distinct.
• C. Spark pipeline: normalize → disjunctive blocking → Splink (Spark) Fellegi-Sunter predict → GraphFrames connected components at a high clustering threshold → per-field survivorship.
• D. Load all 50M into one machine and run an in-memory dedupe library.

Code.

Elimination:
A  cross-join 50M      -> ~1.25e15 pairs, no cluster survives it        [reject: O(n^2)]
B  exact name+dob      -> misses typos/nicknames/missing dob            [reject: recall]
D  single machine 50M  -> does not fit; no parallelism                  [reject: scale]
C  Spark block -> Splink -> GraphFrames CC (high thresh) -> survivorship [ACCEPT]

Step-by-step trace.

1. Constraints: 50M rows (→ distributed/Spark), three sources no shared key (→ record linkage + dedupe), nightly (→ bounded runtime), and "defend against over-merging" (→ conservative clustering).
2. A cross-joins to ~10¹⁵ pairs — it cannot finish on any cluster — eliminate on O(n²).
3. B exact-matches and drops every typo, nickname, and missing-dob true match — eliminate on recall.
4. D cannot fit 50M records and their pairwise work on one machine and throws away parallelism — eliminate on scale.
5. C runs the full pipeline distributed: normalize fields, generate candidates with disjunctive blocking rules as Spark joins (partitioned by block, salting skewed blocks), score pairs with Splink's Spark-backed Fellegi-Sunter model, then cluster with GraphFrames connected components — but at a higher threshold than the pairwise predict threshold so weak edges cannot chain distinct people together — and finally apply per-field survivorship to emit golden records with provenance.

Output:

Stage	Spark mechanism
Normalize	mapPartitions / SQL UDFs
Block	disjunctive join keys, partition-by-block, salt skew
Match	Splink Fellegi-Sunter (Spark backend)
Cluster	GraphFrames connected components, high threshold
Canonicalize	per-field survivorship + provenance

Why this works — concept by concept:

• Blocking as a Spark join — expressing candidate generation as a partitioned join is what keeps 50M records off the O(n²) cliff and lets each block resolve in parallel.
• Distributed Fellegi-Sunter — Splink's Spark backend applies the same learned m/u weights at scale, so precision does not degrade just because the data got big.
• Conservative clustering — setting the connected-components threshold above the pairwise threshold directly counters the transitivity/over-merge hazard, trading a little recall for the precision a customer golden record demands.
• Cost — total work is O(normalize n + candidate pairs + edges·α): blocking bounds the pairs, EM is a few passes, and union-find/GraphFrames is near-linear in edges, so the nightly job scales with the data instead of its square.

Design
Topic — design
Clustering and dedupe system-design problems

Practice →

Course
Course — ETL system design
ETL system design for data engineering interviews

Practice →

---

Cheat sheet — Entity resolution recipes & reference

The ER pipeline in one line. normalize → block → compare (comparison vector) → classify (match/possible/non-match) → cluster (connected components) → canonicalize (golden record).

Similarity-metric picker.

Field / problem	Best metric
Single-token typo (name spelling)	Jaro-Winkler / Damerau-Levenshtein
General typo, any string	Normalized Levenshtein (1 − dist/maxlen)
Multi-word, reordered (address, full name)	Token Jaccard / cosine TF-IDF
Partial-word typo	Trigram (q-gram) Jaccard
Sound-alike surname	Soundex (coarse) / Metaphone (better)
Exact identifier (email, dob, id)	Exact match, term-frequency adjusted

Blocking method picker.

Situation	Method
Simple, one robust key	Standard blocking (group by key)
Typo-prone key field	Phonetic blocking (Soundex/Metaphone key)
Near-duplicates sort together	Sorted-neighborhood (window w)
Need high recall, several keys	Multi-pass / disjunctive (union candidates)
Skewed giant block	Salt / sub-block the large key

• Track reduction ratio (how much work removed) and pair completeness (true matches retained) — a good scheme scores high on both.

Fellegi-Sunter / Splink glossary.

Term	Meaning
m (m-probability)	P(field agrees | true match)
u (u-probability)	P(field agrees | non-match) — coincidental agreement
agreement weight	log2(m/u) added when a field agrees
disagreement weight	log2((1−m)/(1−u)) added when it disagrees
match score	sum of per-field weights
two thresholds	above → match, below → non-match, between → clerical review
EM	learns m (and u) without labels
Splink	scalable Fellegi-Sunter on DuckDB/Spark/Athena
dedupe library	active-learning ER (labels a few pairs)

Precision vs recall tuning checklist.

• Stricter match threshold → higher precision, lower recall (fewer false merges, more missed).
• Looser threshold / more blocking passes → higher recall, lower precision.
• Cluster threshold should exceed the pairwise threshold to fight transitive over-merging.
• Evaluate without labels via: cluster-size distribution (giant clusters = over-merge), manual review of a sample of borderline pairs, and holding out a hand-labeled gold set if you can build one.

Scale recipe. Spark: normalize (UDF) → disjunctive blocking (partitioned join, salt skew) → Splink Spark Fellegi-Sunter predict → GraphFrames connected components (high threshold) → per-field survivorship with provenance.

---

Frequently asked questions

What is the difference between entity resolution, record linkage, and deduplication?

entity resolution is the umbrella task of deciding which records refer to the same real-world entity. Record linkage is entity resolution across two or more datasets that share no common key (e.g. linking a CRM table to a billing table), while deduplication is entity resolution within a single dataset (collapsing duplicate rows in one table). They use the same machinery — normalize, block, compare, classify, cluster — and Splink even exposes them as link_only, dedupe_only, and link_and_dedupe modes of the same model.

What is blocking and why do I need it?

Blocking (also called indexing) groups records into buckets by a cheap key and only compares records that share a bucket, so you never compare all pairs. It matters because comparing every pair is O(n²): one million records is ~500 billion pairs, which is computationally impossible, whereas blocking cuts that to tens of millions. The trade-off is between reduction ratio (how much work you remove) and pair completeness (how many true matches survive), which is why production systems run multiple blocking passes on different keys and union the candidates.

Fuzzy matching vs probabilistic matching — which should I use?

Fuzzy matching (edit distance, Jaccard, phonetics) measures how similar two field values are; probabilistic matching (Fellegi-Sunter) decides whether a pair is a match by learning how much each field's agreement is worth. In practice you use both: fuzzy metrics build the comparison vector, and the probabilistic model weights and thresholds it. Reach for a pure fuzzy rule only for small, well-understood problems; use probabilistic matching (Splink) when you need calibrated scores, many fields of varying reliability, or record linkage at scale.

What is Splink and when should I use it over the dedupe library?

Splink is an open-source implementation of the Fellegi-Sunter probabilistic model that runs on DuckDB, Spark, or Athena, estimates its weights with the EM algorithm (no labels required), and scales to hundreds of millions of records. The dedupe Python library instead uses active learning — it asks you to label a handful of uncertain pairs to train weights — which is excellent for small-to-medium deduplication where you can afford a little labeling. Choose Splink for large-scale, unsupervised record linkage; choose dedupe when the dataset is modest and a few human labels are easy to provide.

How do I evaluate entity-resolution quality without labeled data?

Without a gold set you rely on indirect signals: inspect the cluster-size distribution (a handful of enormous clusters usually means transitive over-merging), manually review a random sample of borderline pairs near your threshold, and check precision/recall on any small hand-labeled subset you can build. Splink also provides diagnostic charts (match-weight waterfalls, m/u values per comparison level) that let you sanity-check whether the learned weights are sensible. The most reliable practice is to hand-label a few hundred pairs to estimate precision and recall even if you cannot label everything.

How does entity resolution scale to hundreds of millions of records?

You keep it off the O(n²) cliff with blocking expressed as a distributed join, run a probabilistic matcher (Splink on Spark) that applies learned weights in parallel, and cluster the pairwise matches with a distributed connected-components job (Spark GraphFrames). Skew is the main enemy: a single giant block (a very common name) bottlenecks one executor, so you salt or sub-block large keys. This blocking-plus-probabilistic-plus-graph-clustering shape, with per-field survivorship at the end, is the standard answer for dedupe at scale.

---

Practice on PipeCode

Turn entity resolution into muscle memory

Articles explain blocking, fuzzy matching, and Fellegi-Sunter weights; PipeCode drills build the reflex an interview actually tests — computing an edit distance under time pressure, designing a blocking scheme that survives typos, and defending a clustering threshold against over-merging. Pipecode.ai is Leetcode for Data Engineering — scenario-first practice on SQL, ETL, string processing, and pattern matching tuned to the trade-offs record-linkage and deduplication problems reward.

Practice ETL problems →
Practice string-processing problems →