Picture a library system before any of its branches shared a computer. Each branch keeps its own card catalog, and the same patron might hold a card at the downtown branch under “J. Doe” and a card at the uptown branch under “Jane A. Doe”, registered years apart with a different apartment number on file. A librarian who wants to combine those two borrowing histories into one record cannot just check whether the names are spelled identically. She has to weigh several imperfect clues at once, the name, the birth year on file, the phone number, and decide whether the balance of evidence says “same person” or “two different people who happen to look similar on paper.”

A medical record deduplication system is that librarian’s job, done automatically, at a scale where guessing wrong is not a returned-book fine but a patient safety incident. A regional hospital network with 400 participating source systems and 50 million tracked patient identities ingests roughly 200,000 new or updated demographic records a day, and for every one of them the system has to answer “is this an existing patient we already know, or someone new” without a universal identifier it can simply look up. Two records for the same person almost never look identical: a maiden name changes, a transposed digit corrupts a date of birth, a self-pay patient never provides a Social Security number, a family shares one home phone line across three different people.

The naive approach is to require an exact match on some identifier, SSN plus name plus date of birth, and treat anything less as a different person. That collapses immediately in real hospital data. SSNs are frequently missing, self-reported incorrectly, or withheld for privacy reasons, especially for newborns and undocumented patients. Exact string matching on names misses the ordinary variation of nicknames, transliteration, and marriage. Fuzzy matching alone, done as an ad hoc weighted similarity score, has no principled way to say how much a matching SSN should count compared to a matching ZIP code, and no natural way to translate that fuzziness into a numeric threshold anyone can defend to an auditor. Comparing every incoming record against all 50 million existing patients is also simply not computationally viable at the latency this system needs.

The forces in tension are recall, precision, throughput, and reversibility, and healthcare weighs them unlike almost any other domain. Missing a true duplicate (recall) means a fragmented medical history, redundant tests, and a clinician working from an incomplete allergy or medication list. Incorrectly merging two different patients (precision) means one person’s chart shows another person’s blood type, drug allergies, and diagnoses, an error with direct clinical consequences. Comparing every record against the full population (throughput) does not scale past a small hospital. And because even a well-tuned model will occasionally be wrong, every merge decision has to be reversible years later without losing a single field of data. We need to solve for a bounded-cost candidate search that scales sublinearly with population size, a scoring model with mathematically principled confidence bands rather than an arbitrary similarity number, a conflict resolution layer that produces one coherent golden record from disagreeing source data, and a fully reversible, auditable trail of every decision, because in this domain an incorrect merge is not an inconvenience, it is an incident report.

Requirements and Constraints

Functional Requirements

• Ingest patient demographic records from heterogeneous hospital systems via HL7 v2 ADT feeds, FHIR Patient resources, and periodic batch CSV extracts from legacy systems
• Generate blocking keys for each incoming record and retrieve a bounded candidate set of potentially matching existing patients, without scanning the full population
• Score every candidate pair using a probabilistic record linkage model and classify each pair as match, non_match, or review
• Route review pairs to a human review queue along with the underlying field-by-field comparison evidence
• On a confirmed match (automatic or reviewer-approved), resolve field-level conflicts between source records using survivorship rules and materialize a single golden record
• Maintain a durable, append-only audit trail of every merge decision, including a full snapshot of both source records and the reasoning that produced the decision
• Support unmerging a previously merged pair, restoring both source records as independent identities without losing any data recorded since the merge

Non-Functional Requirements

• Scale: 50 million golden patient identities, 400 participating hospital source systems, roughly 200,000 new or updated records ingested per day
• Match latency: p95 under 2 seconds for a single incoming record on the real-time admission feed, from arrival to an auto-merge, auto-non-match, or queued-for-review decision
• Batch throughput: able to absorb a nightly flat-file batch of up to 50,000 records from legacy hospital feeds within a 2-hour processing window
• Accuracy: false-merge rate (two distinct patients incorrectly combined) under 1 in 100,000 merges; missed-duplicate rate under 2%, both measured against a labeled clerical-review sample
• Availability: 99.9% for the real-time matching path; an outage must fail toward queuing records for later matching, never toward guessing a merge decision
• Auditability: every merge and unmerge decision must be reconstructable years later, meeting a multi-year, HIPAA-aligned retention requirement
• Reversibility: any merge must be fully undoable at any point after it happens, without permanent loss of either source record’s data

Constraints and Assumptions

• We are not designing the clinical data model (labs, medications, encounters) itself, only the patient identity layer and the stable golden identifier that clinical records reference
• Source systems are assumed to emit demographic changes reliably through existing HL7 or FHIR interfaces; the interface engines themselves are out of scope
• We assume a single legal entity (a hospital network or health information exchange) with data-sharing agreements already in place. Cross-organization matching without such agreements is a legal and policy problem, not an engineering one, and is out of scope
• Downstream clinical decision support that consumes the golden record (allergy checks, drug interaction warnings) is a consumer of this system, not part of it
• Field-level provenance (which source system supplied which value, and when) is assumed to be available on every source record

High-Level Architecture

The system has six major components: the Ingestion and Normalization Gateway, the Blocking Service, the Matching Engine, the Merge Resolution and Golden Record Service, the Master Patient Index (the identity graph store), and the Audit and Unmerge Service.

A record arrives from a hospital system, HL7 v2 for a live admission, FHIR for an API-integrated system, or a batch CSV drop for a legacy feed, and the Ingestion and Normalization Gateway standardizes its fields into one internal shape before anything downstream ever sees it. The Blocking Service then generates several independent blocking keys for the record and retrieves the union of candidate patients that share any of those keys, cutting the comparison universe from 50 million down to a bounded set, typically 20 to 200 candidates. The Matching Engine scores every candidate pair using the Fellegi-Sunter probabilistic linkage model, producing a log-likelihood ratio for each pair. Pairs scoring above the upper threshold flow directly to the Merge Resolution and Golden Record Service; pairs in the gray zone between thresholds go to a human review queue, and an approved review feeds into the same Merge Resolution path.

The Merge Resolution and Golden Record Service applies field-level survivorship rules to reconcile any conflicting data between the two source records and writes a single golden record to the Master Patient Index, which is the durable identity graph every clinical system references by its stable mpi_id. In parallel, the Audit and Unmerge Service records an immutable snapshot of both source records and the exact rule trace that produced the merge, which is the only mechanism that ever allows a merge to be reversed later.

Component Deep Dives

The Ingestion and Normalization Gateway

This component’s job is to turn wildly inconsistent demographic data from 400 different hospital systems into one consistent internal shape before any matching logic ever runs.

A smart engineer’s first instinct is to treat normalization as a minor preprocessing step, trimming whitespace and uppercasing strings. In practice, a large share of dedup quality problems trace back to normalization inconsistency rather than the matching algorithm itself. A hospital that silently changes its date-of-birth format, or a feed that sends ZIP+4 codes where the rest of the system expects five digits, corrupts every blocking key and comparator built on top of that field, for every record from that source, until someone notices.

# Normalizes an inbound HL7/FHIR patient record into the internal comparison shape
# Demonstrates: multi-format DOB parsing, phone digit stripping, deterministic PII tokenization
import re
import hmac
import hashlib
from datetime import datetime

DOB_FORMATS = ("%Y-%m-%d", "%Y%m%d", "%m/%d/%Y", "%d-%b-%Y")

def parse_dob(raw: str) -> str:
    raw = raw.strip()
    for fmt in DOB_FORMATS:
        try:
            return datetime.strptime(raw, fmt).strftime("%Y-%m-%d")
        except ValueError:
            continue
    raise ValueError(f"unrecognized DOB format: {raw!r}")

def normalize_phone(raw: str) -> str:
    digits = re.sub(r"\D", "", raw or "")
    return digits[-10:] if len(digits) >= 10 else digits

def tokenize_ssn(raw_ssn: str, hmac_key: bytes) -> str:
    digits = re.sub(r"\D", "", raw_ssn or "")
    if len(digits) != 9:
        return ""
    return hmac.new(hmac_key, digits.encode(), hashlib.sha256).hexdigest()

def normalize_record(raw: dict, hmac_key: bytes) -> dict:
    return {
        "source_system_id": raw["source_system_id"],
        "external_mrn": raw["mrn"].strip(),
        "first_name": raw["first_name"].strip().upper(),
        "last_name": raw["last_name"].strip().upper(),
        "dob": parse_dob(raw["dob"]),
        "sex": raw.get("sex", "U").strip().upper()[:1],
        "zip5": re.sub(r"\D", "", raw.get("zip", ""))[:5],
        "phone": normalize_phone(raw.get("phone", "")),
        "ssn_token": tokenize_ssn(raw.get("ssn", ""), hmac_key),
    }

The SSN is deterministically tokenized with an HMAC rather than stored or compared in plaintext. This keeps the field usable as a strong comparator (two tokens are equal if and only if the original SSNs were equal) without the system ever persisting raw SSNs longer than the ingestion request itself.

The Blocking Service

This component’s job is to cut the comparison universe from 50 million patients down to a small, bounded candidate set per incoming record, without ever discarding the true match.

The tempting shortcut is to block on one strict key, exact last name plus exact date of birth. That breaks on nicknames, maiden names, and the single most common real-world error in patient data entry, a transposed day and month in the date of birth. A false negative at the blocking stage can never be recovered downstream. If a true duplicate never becomes a candidate pair, the Matching Engine never sees it, no matter how good its scoring is. The fix is to run several independent blocking strategies in parallel and take the union of their candidate sets, trading extra compute for recall that no single key can guarantee alone.

# Generates multiple blocking keys per record so a true match candidate is unlikely to be missed
# Demonstrates: phonetic blocking key, sorted-neighborhood key, union of candidate sets
def soundex(name: str) -> str:
    name = name.upper()
    codes = {**dict.fromkeys("BFPV", "1"), **dict.fromkeys("CGJKQSXZ", "2"),
             **dict.fromkeys("DT", "3"), "L": "4", **dict.fromkeys("MN", "5"), "R": "6"}
    if not name:
        return "0000"
    first_letter = name[0]
    encoded = first_letter
    prev_code = codes.get(first_letter, "")
    for ch in name[1:]:
        code = codes.get(ch, "")
        if code and code != prev_code:
            encoded += code
        prev_code = code
    return (encoded + "000")[:4]

def blocking_keys(record: dict) -> list:
    birth_year = record["dob"][:4]
    keys = [
        f"nm:{soundex(record['last_name'])}:{birth_year}",
        f"zd:{record['zip5']}:{record['dob']}",
    ]
    if len(record["phone"]) >= 7:
        keys.append(f"ph:{record['phone'][-7:]}")
    return keys

def candidate_record_ids(index, record: dict) -> set:
    candidates = set()
    for key in blocking_keys(record):
        candidates |= index.lookup(key)  # posting list for this blocking key
    return candidates

Each blocking key lookup is an O(1) hash access plus an O(bucket_size) scan of the posting list, which turns an O(n^2) full-population comparison into roughly O(n * b), where b is the average candidate bucket size, 20 to 200 records in our system. The phonetic key absorbs spelling variation, the ZIP-plus-DOB key catches married-name changes, and the phone-suffix key catches shared-household registrations where the name itself was entered inconsistently.

The Matching Engine

This component’s job is to take a bounded set of candidate pairs and assign each one a mathematically principled confidence score, not an ad hoc similarity heuristic.

Many engineers reach for a single similarity number, an average of string-edit distances or a cosine similarity over concatenated fields, because it is simple to implement. That approach has no principled way to weight a matching SSN far more heavily than a matching ZIP code, and no natural probabilistic meaning that would let anyone justify a specific numeric threshold. The Matching Engine instead uses the Fellegi-Sunter probabilistic record linkage model, which estimates, per field, how likely true matches are to agree and how likely two unrelated people are to agree by chance, and combines those into one interpretable score. We cover the exact likelihood math, the worked numeric example, and how the underlying probabilities are estimated in the Key Algorithms and Protocols section below.

# Builds the per-field comparison vector the scorer consumes for one candidate pair
# Demonstrates: exact-match and fuzzy comparators feeding into a single agreement vector
from difflib import SequenceMatcher

def fuzzy_agree(a: str, b: str, threshold: float = 0.85) -> bool:
    return SequenceMatcher(None, a, b).ratio() >= threshold

def build_comparison_vector(record_a: dict, record_b: dict) -> dict:
    return {
        "ssn": (record_a["ssn_token"] == record_b["ssn_token"]) if record_a["ssn_token"] and record_b["ssn_token"] else None,
        "last_name": fuzzy_agree(record_a["last_name"], record_b["last_name"]),
        "first_name": fuzzy_agree(record_a["first_name"], record_b["first_name"]),
        "dob": record_a["dob"] == record_b["dob"],
        "sex": record_a["sex"] == record_b["sex"],
        "zip5": record_a["zip5"] == record_b["zip5"],
        "phone": (record_a["phone"] == record_b["phone"]) if record_a["phone"] and record_b["phone"] else None,
    }

The Merge Resolution and Golden Record Service

This component’s job is to turn a confirmed match, automatic or human-approved, into one coherent golden record without silently discarding data from either source.

The instinctive shortcut is “the most recently updated source record wins, entirely.” That fails because the most recently updated record rarely wins on every field simultaneously, a record updated last month for a new home address might still be missing an allergy that was only ever recorded in an older chart from a different hospital. Survivorship has to operate field by field, not record by record.

# Computes a golden record from all currently-linked active source records for one mpi_id
# Demonstrates: field-level survivorship, source trust ranking, multi-valued field union
SOURCE_TRUST_RANK = {"insurance_verified": 3, "hospital_registration": 2, "self_reported": 1}

def resolve_field(candidates: list) -> dict:
    # candidates: [{"value": ..., "source_trust": ..., "updated_at": ..., "source_system_id": ...}, ...]
    non_null = [c for c in candidates if c["value"] not in (None, "")]
    if not non_null:
        return {"value": None, "winning_source": None}
    ranked = sorted(
        non_null,
        key=lambda c: (SOURCE_TRUST_RANK.get(c["source_trust"], 0), c["updated_at"]),
        reverse=True,
    )
    winner = ranked[0]
    return {"value": winner["value"], "winning_source": winner["source_system_id"]}

def build_golden_record(active_source_records: list) -> dict:
    golden = {}
    for field in ("first_name", "last_name", "dob", "address", "phone"):
        candidates = [
            {"value": r.get(field), "source_trust": r["source_trust"],
             "updated_at": r["updated_at"], "source_system_id": r["source_system_id"]}
            for r in active_source_records
        ]
        golden[field] = resolve_field(candidates)

    golden["allergies"] = sorted({
        allergy for r in active_source_records for allergy in r.get("allergies", [])
    })
    return golden

Multi-valued clinical fields, allergies and active medications especially, are unioned across every linked source record rather than overwritten by whichever source ranks highest. Losing an allergy during a merge is not a data quality nuisance, it is a patient safety risk.

The Master Patient Index

This component’s job is to durably hold the mapping from every source record to one stable golden identity, and answer “who is this patient” fast enough for live clinical workflows.

The natural first assumption is that an MPI is one row per patient, updated in place. It is better modeled as a graph: source records are nodes, and merge or unmerge decisions are edges, because a patient’s identity is not a single flat state, it is a lineage of linking decisions that has to remain traceable and reversible.

-- Retrieve every source record currently linked to a patient's golden identity
-- Demonstrates: identity graph traversal for one mpi_id, active links only
SELECT sr.record_id, sr.source_system_id, sr.external_mrn, il.linked_at
FROM identity_links il
JOIN source_records sr ON sr.record_id = il.record_id
WHERE il.mpi_id = $1
  AND il.status = 'active'
ORDER BY il.linked_at;

The store is sharded by hash(mpi_id), so every link and golden record for one patient co-locates on the same shard, which keeps the by-far most common query, “give me everything linked to this patient”, entirely local with no cross-shard fan-out.

The Audit and Unmerge Service

This component’s job is to guarantee that every merge decision the system ever makes can be explained and, if wrong, undone, without losing a single field of clinical data.

The instinctive shortcut is to write a log line: “merged record 123 and 456.” That is not enough to reverse anything, because by the time an error is discovered, the golden record has likely been updated further by newer source data, and the pre-merge state has to be reconstructable independent of what the golden record looks like today.

# Reverses a previously confirmed merge using only the immutable audit snapshot
# Demonstrates: idempotent unmerge, identity graph edge removal, golden record recompute
class MergeAlreadyReversed(Exception):
    pass

def unmerge(db, mpi_store, merge_event_id: str, reversed_by: str) -> None:
    event = db.fetch_merge_event(merge_event_id)
    if event["reversed_at"] is not None:
        raise MergeAlreadyReversed(merge_event_id)

    with db.transaction():
        db.mark_link_inactive(event["record_id_a"], event["mpi_id"])
        db.mark_link_inactive(event["record_id_b"], event["mpi_id"])

        new_mpi_a = db.create_golden_record_for(event["snapshot_a"])
        new_mpi_b = db.create_golden_record_for(event["snapshot_b"])

        db.record_reversal(merge_event_id, reversed_by, new_mpi_a, new_mpi_b)
        mpi_store.recompute_golden_record(event["mpi_id"])  # in case other records still link here

Unmerge never assumes the original mpi_id disappears, since more than two records may have linked to it since the original merge. Recomputing the surviving golden record from whatever links remain active, rather than deleting the identity outright, is what keeps a three-way or four-way merge history safe to partially reverse.

Data Model

The durable state splits into five tables: the normalized source records themselves, the blocking key postings that make candidate lookup fast, the scored candidate pairs, the golden identities, and the append-only merge audit trail.

-- Raw normalized records as received from each hospital source system
CREATE TABLE source_records (
    record_id           BIGSERIAL PRIMARY KEY,
    source_system_id    INTEGER NOT NULL,
    external_mrn        TEXT NOT NULL,
    first_name          TEXT NOT NULL,
    last_name           TEXT NOT NULL,
    dob                 DATE NOT NULL,
    sex                 CHAR(1) NOT NULL DEFAULT 'U',
    zip5                CHAR(5),
    phone               VARCHAR(10),
    ssn_token           CHAR(64),
    source_trust        TEXT NOT NULL
        CHECK (source_trust IN ('insurance_verified', 'hospital_registration', 'self_reported')),
    ingested_at         TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    updated_at          TIMESTAMPTZ NOT NULL DEFAULT NOW()
) PARTITION BY RANGE (ingested_at);

CREATE INDEX ON source_records (source_system_id, external_mrn);
CREATE INDEX ON source_records (last_name, dob);

-- Blocking key postings, rebuilt whenever a source record's identifying fields change
CREATE TABLE record_blocking_keys (
    key_value           TEXT NOT NULL,
    record_id           BIGINT NOT NULL REFERENCES source_records(record_id),
    key_type            TEXT NOT NULL CHECK (key_type IN ('name_dob', 'zip_dob', 'phone')),
    PRIMARY KEY (key_value, record_id)
);
CREATE INDEX ON record_blocking_keys (key_value);

-- One row per scored candidate pair, kept for model tuning and threshold audits
CREATE TABLE match_scores (
    pair_id             BIGSERIAL PRIMARY KEY,
    record_id_a         BIGINT NOT NULL REFERENCES source_records(record_id),
    record_id_b         BIGINT NOT NULL REFERENCES source_records(record_id),
    llr_score           NUMERIC(6,3) NOT NULL,
    decision            TEXT NOT NULL CHECK (decision IN ('match', 'non_match', 'review')),
    scored_at           TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    UNIQUE (record_id_a, record_id_b)
);
CREATE INDEX ON match_scores (decision, scored_at) WHERE decision = 'review';

-- Golden identities. mpi_id is the stable patient identifier every clinical system references
CREATE TABLE golden_records (
    mpi_id              UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    first_name          TEXT,
    last_name           TEXT,
    dob                 DATE,
    address             TEXT,
    phone               VARCHAR(10),
    allergies           TEXT[] NOT NULL DEFAULT '{}',
    version             INTEGER NOT NULL DEFAULT 1,
    updated_at          TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

-- Graph edges linking source records to a golden identity. Never deleted, only marked inactive
CREATE TABLE identity_links (
    link_id             BIGSERIAL PRIMARY KEY,
    record_id           BIGINT NOT NULL REFERENCES source_records(record_id),
    mpi_id              UUID NOT NULL REFERENCES golden_records(mpi_id),
    status              TEXT NOT NULL DEFAULT 'active' CHECK (status IN ('active', 'inactive')),
    linked_at           TIMESTAMPTZ NOT NULL DEFAULT NOW()
);
CREATE INDEX ON identity_links (mpi_id) WHERE status = 'active';
CREATE INDEX ON identity_links (record_id) WHERE status = 'active';

-- Append-only, immutable merge and unmerge audit trail
CREATE TABLE merge_events (
    event_id            BIGSERIAL PRIMARY KEY,
    mpi_id              UUID NOT NULL REFERENCES golden_records(mpi_id),
    record_id_a         BIGINT NOT NULL REFERENCES source_records(record_id),
    record_id_b         BIGINT NOT NULL REFERENCES source_records(record_id),
    llr_score           NUMERIC(6,3) NOT NULL,
    decision_type       TEXT NOT NULL CHECK (decision_type IN ('auto', 'reviewed')),
    reviewer_id         TEXT,
    field_decisions     JSONB NOT NULL,
    snapshot_a          JSONB NOT NULL,
    snapshot_b          JSONB NOT NULL,
    occurred_at         TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    reversed_at         TIMESTAMPTZ,
    reversed_by         TEXT
) PARTITION BY RANGE (occurred_at);

CREATE INDEX ON merge_events (mpi_id, occurred_at DESC);
CREATE INDEX ON merge_events (reversed_at) WHERE reversed_at IS NULL;

source_records is partitioned monthly by ingested_at, keeping the hot, recently written partitions small and their indexes efficient. merge_events is also partitioned monthly, but unlike a typical operational log it is not pruned after a short window, it is retained for a multi-year, HIPAA-aligned compliance period, since regulators expect merge history to be reconstructable long after the fact. The system-wide sharding key is hash(mpi_id), so golden_records and identity_links for one patient always co-locate; record_blocking_keys and match_scores are sharded by record_id instead, since blocking and scoring happen before a golden identity even exists for a genuinely new patient.

Key Algorithms and Protocols

The Fellegi-Sunter Scoring Function

A record linkage decision is a hypothesis test between two explanations for why two records look similar: they describe the same person (a match, M), or they happen to share attributes by coincidence (a non-match, U). For each comparison field i, we define two conditional probabilities: m_i, the probability the field agrees given the pair is a true match, and u_i, the probability the field agrees given the pair is a true non-match, two unrelated people.

Assuming the fields are conditionally independent given the match status, the full likelihood ratio for an observed agreement pattern is the product of the per-field ratios. Taking log2 turns that product into a sum and gives each field an interpretable weight:

w_i(agree)    = log2(m_i / u_i)
w_i(disagree) = log2((1 - m_i) / (1 - u_i))
total score R = sum(w_i for every scored field)

A field with high m_i and low u_i, SSN, where true matches almost always agree and unrelated people almost never do, contributes a large positive weight on agreement. A field with weak discriminating power, sex, which only splits the population roughly in half, barely moves the score either way.

Field	m (agree given match)	u (agree given non-match)	Weight if agree	Weight if disagree
SSN	0.95	0.0002	+12.21	-4.32
Last name	0.93	0.0140	+6.05	-3.82
First name	0.91	0.0200	+5.51	-3.44
Date of birth	0.97	0.0008	+10.24	-5.06
Sex	0.99	0.5000	+0.99	-5.64
ZIP code	0.85	0.0800	+3.41	-2.62
Phone (last 7)	0.80	0.0010	+9.64	-2.32

# Fellegi-Sunter pairwise scoring: sums per-field log-likelihood-ratio weights
# Demonstrates: real m/u probabilities, missing-field handling, total score computation
import math

FIELD_PROBABILITIES = {
    "ssn":        {"m": 0.95, "u": 0.0002},
    "last_name":  {"m": 0.93, "u": 0.0140},
    "first_name": {"m": 0.91, "u": 0.0200},
    "dob":        {"m": 0.97, "u": 0.0008},
    "sex":        {"m": 0.99, "u": 0.5000},
    "zip5":       {"m": 0.85, "u": 0.0800},
    "phone":      {"m": 0.80, "u": 0.0010},
}

def field_weight(field: str, agree: bool) -> float:
    m = FIELD_PROBABILITIES[field]["m"]
    u = FIELD_PROBABILITIES[field]["u"]
    if agree:
        return math.log2(m / u)
    return math.log2((1 - m) / (1 - u))

def score_pair(comparison_vector: dict) -> float:
    # comparison_vector: {"ssn": True, "last_name": True, ..., "phone": None}
    # None means the field was missing on one side and is excluded from scoring
    return sum(
        field_weight(field, agree)
        for field, agree in comparison_vector.items()
        if agree is not None
    )

Consider an incoming record that agrees with an existing patient on first name, last name, date of birth, ZIP, and sex, but disagrees on SSN (a typo in a self-reported field) and phone (the patient changed numbers). Summing the table above: 10.24 + 5.51 + 6.05 + 3.41 + 0.99 - 4.32 - 2.32 = 19.56. With an upper threshold of 20 and a lower threshold of -5, this pair falls just short of automatic merge and lands in the gray zone for human review, exactly the scenario the confidence threshold tuning section below is built to handle deliberately, not accidentally.

Estimating m and u with Expectation-Maximization

In practice, a hospital network rarely has a large labeled set of confirmed true matches and true non-matches sitting around to estimate m_i and u_i directly. The standard extension treats each candidate pair’s true match status as a hidden variable and runs Expectation-Maximization: alternate between estimating the probability each pair is a true match given the current m/u estimates (the E-step), and re-estimating m/u using those probabilities as soft labels (the M-step), until the estimates stop moving.

# EM estimation of Fellegi-Sunter m/u probabilities from unlabeled comparison vectors
# Demonstrates: E-step posterior computation, M-step parameter re-estimation
FIELDS = ("ssn", "last_name", "first_name", "dob", "sex", "zip5", "phone")

def pair_likelihood(vector: dict, m: dict, u: dict, is_match: bool) -> float:
    likelihood = 1.0
    for field in FIELDS:
        agree = vector.get(field)
        if agree is None:
            continue
        p = m[field] if is_match else u[field]
        likelihood *= p if agree else (1 - p)
    return likelihood

def em_step(vectors: list, m: dict, u: dict, prior: float):
    # E-step: posterior P(match | vector) for every observed comparison vector
    posteriors = []
    for vector in vectors:
        p_match = prior * pair_likelihood(vector, m, u, True)
        p_nonmatch = (1 - prior) * pair_likelihood(vector, m, u, False)
        total = p_match + p_nonmatch
        posteriors.append(p_match / total if total else 0.0)

    # M-step: re-estimate each field's m and u as posterior-weighted agreement rates
    new_m, new_u = {}, {}
    total_post = sum(posteriors)
    total_nonpost = sum(1 - p for p in posteriors)
    for field in FIELDS:
        agree_mass_match = sum(
            post for vector, post in zip(vectors, posteriors) if vector.get(field) is True
        )
        agree_mass_nonmatch = sum(
            (1 - post) for vector, post in zip(vectors, posteriors) if vector.get(field) is True
        )
        new_m[field] = agree_mass_match / total_post if total_post else m[field]
        new_u[field] = agree_mass_nonmatch / total_nonpost if total_nonpost else u[field]

    new_prior = total_post / len(vectors)
    return new_m, new_u, new_prior

def fit_em(vectors: list, iterations: int = 20) -> tuple:
    m = {f: 0.9 for f in FIELDS}
    u = {f: 0.1 for f in FIELDS}
    prior = 0.05
    for _ in range(iterations):
        m, u, prior = em_step(vectors, m, u, prior)
    return m, u, prior

Each EM iteration is O(pairs * fields), and convergence typically takes 15 to 30 iterations on a few hundred thousand sampled candidate pairs, cheap enough to rerun monthly as new hospital source systems join and field agreement statistics shift. EM is sensitive to initialization for fields with weak discriminating power, sex being the obvious example in our table, and a common practical fix is seeding m/u from a small labeled clerical-review sample rather than a pure guess, anchoring the weakest field instead of letting EM drift toward a degenerate solution.

Confidence Threshold Tuning

A raw log-likelihood score is only useful once you decide where the boundaries sit. Fellegi and Sunter’s original formulation sets an upper threshold above which a pair auto-merges and a lower threshold below which a pair auto-rejects, with everything in between routed to a human. Where exactly to set those two numbers is a business decision as much as a statistical one, and in healthcare the cost of the two error types is wildly asymmetric. A false merge risks mixing two people’s blood type, allergy list, and medication history. A missed duplicate is a nuisance a human can reconcile later. A gray-zone case costs a reviewer a few minutes.

# Sweeps candidate thresholds against a labeled clerical-review sample to pick upper/lower bounds
# Demonstrates: asymmetric cost minimization for threshold selection
FALSE_MERGE_COST = 500_000   # a wrongly combined patient chart, in relative cost units
FALSE_NONMATCH_COST = 50     # a missed duplicate, reconciled manually later
REVIEW_COST = 2              # one reviewer touching a gray-zone case

def evaluate_thresholds(labeled_pairs: list, upper: float, lower: float) -> dict:
    # labeled_pairs: [{"score": float, "is_true_match": bool}, ...]
    false_merges = sum(1 for p in labeled_pairs if p["score"] >= upper and not p["is_true_match"])
    false_nonmatches = sum(1 for p in labeled_pairs if p["score"] <= lower and p["is_true_match"])
    reviewed = sum(1 for p in labeled_pairs if lower < p["score"] < upper)
    total_cost = (
        false_merges * FALSE_MERGE_COST
        + false_nonmatches * FALSE_NONMATCH_COST
        + reviewed * REVIEW_COST
    )
    return {
        "false_merges": false_merges,
        "false_nonmatches": false_nonmatches,
        "reviewed": reviewed,
        "total_cost": total_cost,
    }

def sweep_thresholds(labeled_pairs: list, candidates: list) -> tuple:
    best = None
    for upper in candidates:
        for lower in candidates:
            if lower >= upper:
                continue
            result = evaluate_thresholds(labeled_pairs, upper, lower)
            if best is None or result["total_cost"] < best[1]["total_cost"]:
                best = ((upper, lower), result)
    return best

The heavy asymmetry between FALSE_MERGE_COST and the other two costs is deliberate, and is exactly why the upper threshold in a healthcare MPI tends to sit conservatively high, 20 or more bits of evidence in our scale, compared to a similar system deduplicating, say, a marketing contact list, where a false merge just means a slightly wrong email address.

Scaling and Performance

The system scales along three largely independent axes: the blocking index, sharded by blocking-key hash to spread candidate lookup volume; the matching worker pool, autoscaled for scoring compute; and the Master Patient Index, sharded by hash(mpi_id) on a fixed-size ring that scales independently of ingestion volume entirely.

Capacity Estimation:

Given:
  - 50,000,000 golden patient identities in the MPI
  - 400 hospital source systems
  - 200,000 new/updated records/day via real-time HL7/FHIR feeds (~2.3/sec avg)
  - Nightly legacy batch: up to 50,000 records from flat-file EDI hospitals, 2-hour window
  - Average 40 candidate pairs generated per record after blocking
  - ~0.05% of scored pairs fall into the manual review gray zone

Real-time matching path:
  Records/sec (avg): 200,000 / 86,400 ~= 2.3/sec
  Candidate pairs scored/sec (avg): 2.3 * 40 ~= 93/sec
  Peak (multi-hospital admission surge): ~20x average ~= 1,860 pairs/sec

Nightly batch path:
  Records: 50,000
  Candidate pairs: 50,000 * 40 = 2,000,000
  Required throughput to clear in 2 hours: 2,000,000 / 7,200s ~= 278 pairs/sec sustained
  Matching worker pool: ~4 workers steady state, autoscale to ~40 during the batch window

Manual review queue:
  Total pairs scored/day: (200,000 + 50,000) * 40 = 10,000,000
  Gray-zone pairs/day: 10,000,000 * 0.0005 ~= 5,000/day
  Reviewer throughput: ~180 cases/reviewer/day
  Review team sized for the queue: ~28 reviewers with headroom

Storage:
  source_records: ~78,000,000 accumulated rows (50M unique patients, ~1.56 source records each)
    at ~450 bytes/row: ~35GB
  merge_events: ~60,000 merge events/day, ~7KB/event (two snapshots + rule trace): ~420MB/day
    retained for a 10-year compliance window, partitioned monthly
  identity_links: ~78,000,000 active edges at ~80 bytes/row: ~6.2GB

The read-to-write ratio at the Master Patient Index is heavily read-skewed, clinical systems look up a patient’s golden record far more often than the matching pipeline writes one, so golden_records sits behind a read-through cache keyed by mpi_id. That cache is invalidated synchronously on every merge and unmerge write rather than relying on a short TTL, because briefly serving a stale, pre-merge or pre-unmerge view to a clinician is not an acceptable trade in this domain the way it might be for a video CDN or a product catalog.

Failure Modes and Recovery

Failure	Detection	Impact	Recovery
Blocking index shard overloaded by a common surname and birth-year cohort	Bucket size alarms, p99 candidate lookup latency spike	Real-time matching latency SLA breached for records hitting that key	Split the hot shard’s key range; overflow candidates route to an async path instead of blocking the real-time SLA
Matching worker crash mid-score	Health check plus in-flight job timeout in the queue	The candidate pair is left unscored	Job queue redelivers the pair to a healthy worker; scoring is idempotent, so a duplicate score simply overwrites with the same result
Normalization bug on one source feed (a hospital changes its DOB format)	Drift monitoring flags a sudden change in blocking key cardinality or agreement rate for that source_system_id	Silent recall loss, the source stops generating true-positive candidates	Quarantine and reprocess the affected date range once the feed is fixed
Merge Resolution Service crash after scoring, before commit	Idempotency check on the merge_events insert	Pair scored but not yet merged	Retry from the persisted match_scores row; the write is one transaction, so it either fully commits (golden record, link, and audit event together) or not at all
EM re-estimation converges to a degenerate solution (m and u collapse toward each other)	Automated check for minimum required separation between m_i and u_i before promoting new estimates	New estimates would silently weaken discriminating power for a key field	Reject the run, keep the last known-good table, alert the data science on-call
Erroneous merge discovered weeks later	A clinician or data steward flags a golden record with contradictory data (two different blood types, for example)	The golden record shows data belonging to two different people	unmerge() replays the audit snapshot; both records restored as independent identities, golden record recomputed from remaining active links

Comparison of Approaches

Approach	Latency	Complexity	Failure Mode	Best Fit
Deterministic exact match (SSN + exact name + exact DOB)	Sub-millisecond index lookup	Low	Misses any typo, name change, or missing SSN; recall collapses on real hospital data	Small, single-system deployments with a clean, mandatory unique identifier
Simple weighted similarity score (average string-edit distance, arbitrary threshold)	Low, single comparison pass	Low to Medium	No principled way to combine field-level discriminating power; thresholds are hard to defend to an auditor	Prototyping, or low-stakes domains like a marketing contact list
Fellegi-Sunter with EM-tuned thresholds (this design)	Single-digit milliseconds per candidate pair after blocking	High (blocking infra, EM tuning, review workflow, audit trail)	Field independence assumption can overstate confidence for correlated fields	Regional or national health information exchanges with tens of millions of patients across many source systems
Machine-learned pairwise classifier (gradient-boosted trees or a neural matcher) over the same features	Comparable once trained; higher retraining overhead	Very high (labeled data pipeline, retraining, explainability tooling)	Harder to explain any single decision to a compliance auditor than a transparent log-likelihood sum	Large, well-resourced organizations with existing labeled merge data and dedicated ML infrastructure
Full manual review of every ingested record	Minutes to hours per record	Low (no algorithm to build)	Cannot scale past a small daily volume; reviewer fatigue introduces its own error rate	A one-time historical data cleanup project, not an ongoing pipeline

For a hospital network at tens of millions of patients across hundreds of independently operated source systems, Fellegi-Sunter with EM-tuned thresholds is the right call. It is the only option here that combines sub-5ms scoring latency with a scoring rationale that can be explained field by field to a compliance auditor years after the fact. The machine-learned classifier is a reasonable future upgrade once enough labeled merge data accumulates, but it trades transparency for accuracy gains that matter less, in a regulated domain, than being able to explain exactly why any single merge happened.

Key Takeaways

• Blocking sets the ceiling on recall: any true duplicate that blocking fails to surface as a candidate pair can never be found by the matching engine, no matter how good the scoring model is.
• Fellegi-Sunter turns similarity into a probability statement: log-likelihood-ratio weights, not an arbitrary similarity score, are what make a numeric merge threshold defensible.
• The independence assumption is a simplification, not a law: correlated fields, like a shared household address, can overstate a pair’s confidence, so field selection matters as much as the scoring math itself.
• Thresholds encode a cost decision, not just a statistical one: in healthcare, the cost of a false merge dwarfs the cost of a missed duplicate or an extra manual review case, and the thresholds should reflect that asymmetry explicitly.
• Survivorship is field-level, not record-level: the most recently updated source record is rarely correct on every field simultaneously.
• An identity graph, not a flat table, is what makes unmerge possible: durable links plus an immutable event log are what let a merge be undone years later without losing data.
• Multi-valued clinical fields should be unioned, never overwritten: an allergy lost during a merge is a patient safety risk, not a data quality nuisance.
• Human review is architecture, not a fallback: the gray zone between thresholds is a deliberate design surface, sized and staffed like any other component in the system.

The counter-intuitive lesson is that the hardest part of this system is not the probabilistic math, which is decades old and well understood, it is resisting the temptation to make merges more automatic than the underlying cost asymmetry actually justifies. A system that never asks a human for help is not evidence of a better model. In a domain where a false merge is a patient safety incident, it is evidence of thresholds tuned by someone who has not yet had to explain a wrongly merged chart to a hospital’s compliance office.

Frequently Asked Questions

Q: Why not just require every hospital system to use the same national patient identifier and skip probabilistic matching entirely?

A: The United States has no single mandated national patient identifier, and even health systems that do operate with one see identifiers mistyped, duplicated, or issued more than once for the same person at registration. Probabilistic matching is not a workaround for a missing identifier, it is a necessary safety net even when a supposedly unique identifier already exists, because that identifier is still entered by a human being at a front desk.

Q: Why not use a machine-learned classifier instead of a formula from 1969?

A: A trained classifier can match or exceed Fellegi-Sunter’s raw accuracy given enough labeled data, but it trades away exactly what regulated healthcare needs most: the ability to explain any single decision as a sum of readable, per-field contributions. A gradient-boosted tree’s decision boundary is not something you can hand a compliance auditor and walk through field by field. Fellegi-Sunter remains the right default until an organization has both a large labeled dataset of confirmed merges and the operational maturity to explain a model’s decisions some other way.

Q: How do you avoid a snowball effect where one bad merge chains into more bad merges?

A: Merging A with B, and separately B with C, can transitively imply A equals C without those two records ever being directly compared. The Merge Resolution Service requires direct pairwise evidence for any new link, and any identity cluster that grows beyond two or three linked records triggers a mandatory cluster-level human review before any further automatic merges are allowed onto it, since a chain of merges compounds risk faster than any single pairwise decision does.

Q: Why not lower the review threshold band to reduce reviewer workload, since most gray-zone cases end up approved anyway?

A: A high approval rate in the gray zone does not mean the band is unnecessary, it means the band is correctly catching the ambiguous cases that should be looked at, including the minority that should not be approved. Tightening the band to cut workload shifts risk toward false merges even while the base approval rate stays high, which is exactly the tradeoff the cost function in the threshold tuning section is built to make visible rather than absorb silently.

Q: What happens when two hospital systems institutionally merge and bring two independent Master Patient Indexes that now need to be reconciled?

A: Treat it as a bulk batch job, not real-time traffic. Run the full blocking-and-scoring pipeline between the two populations in a staging environment before either system starts writing to a unified MPI, expect a much higher gray-zone review volume than day-to-day operations, and staff the review team temporarily for the reconciliation window rather than trying to absorb it into steady-state capacity.

Q: Why keep both original source records after a merge instead of just combining their fields into one row?

A: Discarding the originals is exactly what makes unmerge impossible. The audit snapshot exists precisely so that a merge decision, however confident at the time, can be fully reversed without reconstructing lost data from whatever the golden record happens to look like months later.

Interview Questions

Q: Design the scoring function for a system that must combine several weak and strong signals into a single merge decision a compliance auditor can later explain field by field. What tradeoffs would you make?

Expected depth: Discuss why Fellegi-Sunter log-likelihood weights are more auditable than an opaque similarity score or a black-box classifier, the field independence assumption and when it breaks down for correlated fields, and how per-field m/u probabilities let you explain any decision as a sum of readable contributions rather than a single unexplainable number.

Q: A hospital network wants to merge two previously separate 20-million-record patient populations into one Master Patient Index. How would you approach the reconciliation, and how does it differ from steady-state real-time matching?

Expected depth: Discuss reframing this as a bounded blocking problem rather than a naive all-pairs comparison, sizing throughput and temporarily staffing the review team for a one-time spike, staging the reconciliation to a lower-traffic window, and validating aggregate false-merge and false-nonmatch rates on a sample before letting the bulk job write to the live index.

Q: Walk through what has to happen when a data steward discovers, six months later, that two different patients were incorrectly merged. What must be true about the system’s design for the fix to be safe?

Expected depth: Trace the unmerge path: locate the immutable merge event snapshot, verify no other identity links have accumulated on top of the merged identity since, restore both source records as independent identities, recompute any surviving golden record, and invalidate downstream clinical caches. Discuss why a system without an immutable pre-merge snapshot cannot do this safely at all.

Q: How would you tune confidence thresholds for a brand-new hospital source system joining the exchange, before you have any labeled ground truth for that system’s data quality?

Expected depth: Discuss bootstrapping from existing, well-calibrated m/u estimates, running the new source in a shadow mode that logs decisions without merging, sampling a portion of shadow decisions for manual labeling to validate or adjust source-specific quality assumptions, and gradually promoting the source from shadow to live matching as confidence in its data quality grows.

Q: Your blocking strategy generates too many candidates for common surnames in one region, overloading a shard during peak admission hours. How do you fix this without weakening recall?

Expected depth: Discuss splitting the hot key range rather than loosening the blocking key itself, adding a secondary, more selective blocking pass specific to the overloaded range, and separating latency-sensitive real-time traffic from an asynchronous overflow path for excess candidates rather than dropping candidates to protect the SLA.