Deduplicating Patient Identities with Deterministic Matching

Problem Statement

The same patient arrives at the laboratory under many spellings: “Ren Nakamura” and “Nakamura, Ren”, an MRN with and without leading zeros, a date of birth entered as 03/02/1984 in one feed and 1984-03-02 in another. If each variant becomes its own patient record, a result binds to a fragment of the person’s history and a delta check compares against the wrong baseline; if two genuinely different patients are collapsed because their names and birth years happen to align, a result lands on the wrong chart. Deterministic identity deduplication resolves every inbound demographic set to one stable identity_key — the key the Patient Identity & Order Matching stage reconciles a result’s order against — by matching only on exact, normalized evidence and refusing to auto-merge when the evidence is weak. This page builds that resolver in typed Python: normalize the tokens, block to keep comparison cheap, derive a reproducible key, and route genuine conflicts to human review instead of silently merging them.

Prerequisites

Before wiring this into the identity service, confirm the following baseline:

  • Runtime: Python 3.11+, pydantic>=2.6, and pytest>=8 for the verification fixtures.
  • Demographic source: inbound demographics already extracted from the message by the Instrument Data Ingestion & HL7/CSV Pipelines tier, with the assigning-authority namespace preserved on the MRN.
  • Identity store: a persistent store keyed by identity_key, holding one canonical record per resolved patient plus the set of source demographics that resolved to it.
  • Governance: a human-review queue for conflicts, since deterministic dedup proposes merges by exact evidence but never auto-merges on partial evidence — the same review discipline the Security & Access Controls layer audits.

Step-by-Step Implementation

Step 1: Normalize the demographic tokens

Deterministic matching is exact-match on normalized tokens, so normalization is the whole game — two spellings of one patient must reduce to identical tokens, and two different patients must not. Casefold and strip accents from names, tokenize order-independently, normalize the MRN within its assigning authority (trim insignificant leading zeros, keep the authority namespace so the same digits under different authorities stay distinct), and parse the date of birth to a calendar date.

python
from __future__ import annotations

import datetime as dt
import unicodedata
from pydantic import BaseModel, ConfigDict, field_validator


def _fold(text: str) -> str:
    stripped = unicodedata.normalize("NFKD", text).encode("ascii", "ignore").decode()
    return stripped.casefold().strip()


def name_tokens(name: str) -> tuple[str, ...]:
    cleaned = _fold(name).replace(",", " ")
    return tuple(sorted(t for t in cleaned.split() if t))


class Demographics(BaseModel):
    model_config = ConfigDict(frozen=True, extra="forbid")

    assigning_authority: str
    mrn: str
    name: str
    birth_date: dt.date

    @field_validator("mrn")
    @classmethod
    def _norm_mrn(cls, v: str) -> str:
        digits = v.strip().upper()
        # trim insignificant leading zeros while keeping an all-zero guard
        return digits.lstrip("0") or "0"

    @property
    def tokens(self) -> tuple[str, ...]:
        return name_tokens(self.name)

    @property
    def authority_mrn(self) -> str:
        return f"{self.assigning_authority}:{self.mrn}"

The authority_mrn composite is deliberate: an MRN is scoped to the facility that issued it, so AUTH-A:9912 and AUTH-B:9912 are two different people and must never collapse just because the digits match.

Step 2: Reduce the comparison space with blocking

Comparing every inbound record against every stored identity is quadratic and unnecessary. Blocking partitions candidates into small buckets that share a cheap, stable key, so a match is only ever sought within one bucket. A good blocking key is loose enough that true matches never fall in different buckets, but tight enough that buckets stay small; a common choice is the birth date combined with the first character of the sorted surname token.

python
def blocking_key(d: Demographics) -> str:
    surname_initial = d.tokens[0][:1] if d.tokens else "?"
    return f"{d.birth_date.isoformat()}|{surname_initial}"

Blocking is an index, not a decision: landing in the same block never implies a match, it only means two records are worth comparing. The match decision is still the exact-key test in Step 3. Choosing a blocking key that includes birth date matters because birth date is the strongest single demographic discriminator and is rarely mis-keyed in a way that changes the block.

Step 3: Derive the deterministic identity key

The identity key is a stable, reproducible function of the strong evidence — the authority-scoped MRN, the birth date, and the sorted name tokens. Because it is a pure hash of normalized inputs, the same patient always hashes to the same key on every run and in every process, which is exactly what makes dedup deterministic and auditable. Two records with identical strong evidence share a key and are the same identity by construction; no scoring, no threshold.

python
import hashlib


def identity_key(d: Demographics) -> str:
    material = "|".join((
        d.authority_mrn,
        d.birth_date.isoformat(),
        " ".join(d.tokens),
    ))
    return hashlib.sha256(material.encode("utf-8")).hexdigest()[:32]

Using a cryptographic hash is not about secrecy — it is about getting a fixed-width, collision-resistant key that is stable across languages and storage layers. Any two records that normalize to the same MRN, birth date, and name tokens produce the same identity_key; anything that differs in the strong evidence produces a different key and is treated as a different identity until a human says otherwise.

Step 4: Resolve, and hold conflicts instead of merging

Resolution reads the block, then decides among three outcomes. If the exact identity_key already exists, reuse it. If the key is absent and no near-collision exists in the block, mint a new identity. If the block contains a record that matches on some strong fields but disagrees on another — same MRN and birth date but different name tokens, the classic signature of an MRN typo or a shared-MRN data-entry error — do not auto-merge and do not silently mint: raise a conflict for human review. Auto-merging on partial evidence is how two patients become one record.

python
from enum import Enum
from typing import Protocol


class Resolution(str, Enum):
    EXISTING = "EXISTING"
    NEW = "NEW"
    CONFLICT = "CONFLICT"


class IdentityStore(Protocol):
    async def block(self, blocking_key: str) -> list[Demographics]: ...
    async def has_key(self, identity_key: str) -> bool: ...


class IdentityResult(BaseModel):
    resolution: Resolution
    identity_key: str
    reason: str | None = None


def _partial_collision(inbound: Demographics, peer: Demographics) -> bool:
    """Same MRN and DOB but different name tokens => suspicious, not a match."""
    return (
        inbound.authority_mrn == peer.authority_mrn
        and inbound.birth_date == peer.birth_date
        and inbound.tokens != peer.tokens
    )


class IdentityResolver:
    def __init__(self, store: IdentityStore) -> None:
        self._store = store

    async def resolve(self, d: Demographics) -> IdentityResult:
        key = identity_key(d)
        if await self._store.has_key(key):
            return IdentityResult(resolution=Resolution.EXISTING, identity_key=key)
        peers = await self._store.block(blocking_key(d))
        if any(_partial_collision(d, p) for p in peers):
            return IdentityResult(
                resolution=Resolution.CONFLICT, identity_key=key,
                reason="mrn_dob_match_name_mismatch",
            )
        return IdentityResult(resolution=Resolution.NEW, identity_key=key)

A CONFLICT never writes a merge and never writes a new identity as if it were clean — it holds the record and surfaces both candidates to a technologist, who confirms whether it is one patient (a name change or correction) or two (a shared-MRN error to escalate). Probabilistic similarity may rank the review queue, but it never crosses the auto-merge boundary.

Deterministic patient-identity resolution flow Inbound patient demographics enter at the top. A normalization step reduces the MRN, date of birth, and name to canonical tokens. A blocking step derives a cheap bucket key and reads candidate peers from the identity store on the right. A deterministic identity-key step hashes the strong evidence. A compare step forks three ways: an existing key reuses the identity; an absent key with no collision mints a new identity; and a partial collision, where the MRN and birth date match but the name tokens differ, is held as a conflict for human review rather than auto-merged. inbound patient demographics Normalize tokens authority:MRN · DOB · name tokens Blocking DOB + surname initial → bucket Identity Store block peers Deterministic identity key sha256(mrn | dob | tokens) Compare to block exact key vs partial collision key exists key absent collision Reuse identity existing identity_key Mint identity new identity_key Conflict → hold no auto-merge · review

Verification & Testing

Prove the two claims that matter: identical patients under different spellings resolve to one key, and a partial collision holds instead of merging.

python
import pytest


def _demo(**over) -> Demographics:
    base = dict(assigning_authority="AUTH-A", mrn="0009912",
                name="Ren Nakamura", birth_date=dt.date(1984, 3, 2))
    return Demographics(**{**base, **over})


def test_spelling_variants_share_a_key():
    a = identity_key(_demo(name="Ren Nakamura", mrn="0009912"))
    b = identity_key(_demo(name="Nakamura, Ren", mrn="9912"))
    assert a == b  # comma order and leading zeros normalize away


def test_different_authority_does_not_collapse():
    a = identity_key(_demo(assigning_authority="AUTH-A"))
    b = identity_key(_demo(assigning_authority="AUTH-B"))
    assert a != b  # same digits, different issuing facility


class BlockStore:
    def __init__(self, peers: list[Demographics]) -> None:
        self._peers = peers

    async def block(self, blocking_key: str) -> list[Demographics]:
        return self._peers

    async def has_key(self, identity_key: str) -> bool:
        return False


@pytest.mark.asyncio
async def test_mrn_dob_match_name_mismatch_holds():
    peer = _demo(name="Rex Nakahara")  # same MRN+DOB, different name tokens
    res = await IdentityResolver(BlockStore([peer])).resolve(_demo())
    assert res.resolution is Resolution.CONFLICT

Expected: all three pass. test_spelling_variants_share_a_key confirms that comma-order and leading-zero differences normalize away to one key. test_different_authority_does_not_collapse confirms the authority namespace keeps identical MRN digits from two facilities distinct. test_mrn_dob_match_name_mismatch_holds proves the resolver refuses to auto-merge a suspicious partial collision and routes it to review. Round-trip IdentityResult.model_validate_json(res.model_dump_json()) to confirm the decision record is byte-stable for the audit sink.

Compliance Note

HIPAA §164.312©(1) requires integrity controls that protect PHI from improper alteration, and an identity merge is one of the most consequential alterations a laboratory system can make — an incorrect merge blends two patients’ records irreversibly. Deterministic keying makes every merge decision attributable and reproducible: the same evidence always yields the same identity_key, and every resolution writes a record naming the inputs and outcome. Holding partial collisions for human review rather than auto-merging is the patient-safety control behind the integrity requirement; a wrong merge is a wrong-patient event by another name, the same hazard class the Patient Identity & Order Matching stage guards at result binding. Writing resolution records to an append-only sink under the CLIA §493.1105 retention window keeps the identity history reconstructable for inspection.

Troubleshooting

One patient fragmented into several identities.

Root cause: normalization is too strict, so trivial spelling differences change the strong evidence and therefore the key — a hyphenated surname tokenized differently, or an MRN kept zero-padded on one feed. Fix: strengthen name_tokens and _norm_mrn so equivalent inputs reduce identically (casefold, strip accents, sort tokens, trim insignificant zeros within the authority), and add a fixture pinning the variants that should share a key.

Two different patients collapsed into one identity.

Root cause: the identity key was built from weak evidence — name and birth year alone, or an MRN without its assigning authority — so two people aligned. Fix: key on the authority-scoped MRN plus full birth date plus name tokens, and never widen the block into an auto-merge; a block hit is only a reason to compare, never a reason to merge.

The resolver keeps raising conflicts for the same corrected name.

Root cause: a legitimate name correction (marriage, a fixed typo) keeps producing a new key that partially collides with the old identity, so every result re-triggers a hold. Fix: once a human confirms the merge, record an alias so the store’s has_key/block lookups resolve both the old and new tokens to the confirmed identity_key, clearing the recurring conflict without weakening the matching rule.

Dedup is slow at scale.

Root cause: comparison is running against the whole identity store rather than a block, making resolution quadratic. Fix: index by blocking_key and compare only within the bucket; the exact-key has_key lookup should be O(1) and the partial-collision scan should touch only the handful of peers sharing a birth date and surname initial.

Part of: Patient Identity & Order Matching.