Tokenization and Privacy-Preserving Record Linkage

In plain language

To study a patient across separate databases - what their insurance paid for, what their hospital chart shows, whether and when they died - you have to recognize the same person in each one, but privacy law blocks sending names between organizations. Tokenization solves this by scrambling each person's identifiers into a fixed, irreversible code (a token) using the same recipe everywhere, so matching tokens means the same patient, with no names exchanged. The catch is that linkage is never perfect: some real matches are missed and some wrong matches slip in, so you must report a match rate and check linkage errors. And because people with messy or unstable identifiers link less often, the linked group can quietly differ from everyone you started with - a selection problem you have to look for.

Almost every interesting real-world question now spans datasets that no single custodian holds: pharmacy and medical claims know what was paid for, the EHR knows labs and vitals, a death index knows the fact and date of death, and SDOH vendors know neighborhood and area-level deprivation. Joining them on a person requires identifiers, but the whole US privacy regime (HIPAA) is built to stop clear-text identifiers from being shipped between parties. Tokenization resolves the tension: each party runs the same deterministic, salted, one-way hashing recipe over standardized identifiers (name, date of birth, sex, sometimes a partial SSN or address) to produce an irreversible token. Two records that hashed to the same token belong to the same person; nobody had to send a name. The HIPAA de-identification logic is usually expert determination - a qualified statistician certifies that the token plus the retained data carry a very small re-identification risk - rather than the Safe Harbor checklist, because linkage needs a stable cross-dataset key that Safe Harbor would strip.

What actually happens in the US ecosystem

A token vendor (Datavant, HealthVerity, and similar) defines several token "recipes," each over a different identifier bundle, so that a missing or mistyped field in one recipe can be rescued by another. Crucially, tokens are site-keyed (encrypted again with a key unique to each data partner) so the same person carries a different token at site A than at site B; an honest broker holds a crosswalk that re-encrypts site A tokens into site B's space so the join can happen without either side learning the other's raw token. Deterministic linkage then joins on exact token equality. Probabilistic / Bloom-filter PPRL is the fuzzier cousin: each identifier is split into character n-grams and hashed into a bit vector (a Bloom filter); two vectors are compared by set-overlap similarity (Dice/Jaccard), so near matches - a hyphenated surname, a transposed birth month - still link with a calibrated threshold. Bloom-filter PPRL is what makes privacy-preserving probabilistic matching possible at all (Schnell, Bachteler, Reiher 2009).

Pros, cons, and trade-offs

(specific and comparative). - vs direct-identifier (clear-text) deterministic linkage: Tokenization buys you a legally shippable key and a defensible de-identification posture; the cost is that you can no longer eyeball or hand-adjudicate a borderline pair, you inherit whatever the vendor's identifier standardization did, and an exact-token join is brittle to the very typos a human reviewer would have forgiven. Prefer clear-text linkage only inside a single custodian or an honest-broker enclave where PHI exchange is permitted; prefer tokenization the moment data crosses organizational boundaries. - vs probabilistic / Bloom-filter PPRL within tokenization: A single deterministic token is precise (few false matches) but unforgiving (more false misses when identifiers are imperfect). A multi-token waterfall - try the strongest recipe, then fall back to weaker recipes for the unmatched - raises the match rate but each weaker recipe trades precision for recall, so false matches creep in on the rescued records. Bloom-filter PPRL recovers even more true pairs but needs threshold tuning and a small clerically reviewed or gold-standard sample to set the cut. Prefer deterministic-only when a false link is more damaging than a missed one (e.g., attributing a death to the wrong patient); prefer a waterfall or PPRL when coverage of the linkable population is the binding constraint. - vs treating "linked" as a clean merge: The seductive error is to link, drop the unmatched, and analyze the linked cohort as if it were the source cohort. Linkage is a measurement with error in two directions and a selection mechanism, not a lossless join.

When to use

Whenever the exposure, outcome, or confounders live in different datasets and you need them on one row: claims exposure with EHR labs for confounding control; a claims cohort linked to the death index for an all-cause mortality endpoint; claims or EHR linked to SDOH vendors for area-level deprivation; tumor registry linked to claims for treatment and cost; or multi-site networks that must pool person-level data they are not allowed to share in the clear. Tokenization is also the practical substrate for de-duplicating the same patient who appears in two overlapping data feeds.

When NOT to use - and when it is actively misleading

- Do not report a linked analysis without a match rate and, where possible, false-match and false-miss estimates from a validation sample (a subset with a trusted gold-standard linkage). A 70% match rate silently discards 30% of the cohort; pretending the linked 70% is the whole cohort is the central trap. - Selection bias from the linkable subpopulation. Whether a person links is not random. People with stable names and addresses, continuous insurance, and full identifiers link at much higher rates than mobile, younger, recently immigrated, or intermittently insured people - and those traits correlate with exposure and outcome. If you restrict to the linked subset, you are conditioning on linkage, which can open a collider path and bias the effect estimate. Report match rate by subgroup, compare linked vs unlinked on observed characteristics, and consider weighting (inverse-probability-of-linkage) or a sensitivity analysis. - False matches contaminate the outcome. A wrong token link can graft another person's death or hospitalization onto your patient, biasing event rates in a direction that depends on the linkage error structure. Treat false matches like outcome misclassification, not like random noise. - Do not assume Bloom-filter or token recipes are perfectly privacy-preserving; frequency and pattern attacks on Bloom filters exist, which is why salting, site-keying, and expert determination - not the hashing alone - carry the de-identification claim.

Data-source operational depth

- Claims: Identifiers come from enrollment/eligibility files; tokens are usually generated by the vendor on the closed-claims feed. Match rates are highest here because insurers maintain clean member identifiers, but Medicare Advantage and gaps in enrollment shrink the observable and therefore the linkable window. - EHR: Identifiers can be messy (free-text names, missing SSN, registration typos), so EHR is where probabilistic/Bloom-filter PPRL earns its keep and where the multi-token waterfall recovers the most pairs. - Registry / mortality: The death index (state files or a commercial composite) is the canonical reason to link; match quality here directly determines outcome ascertainment, so false matches and false misses must be quantified, not assumed. - Linked (the deliverable): Reconcile token recipes across vendors, document which recipe matched each pair, carry a match-confidence field forward, and keep the unmatched records so match rate and selection can be audited downstream.

Worked example

Scenario

We have 1,000 patients in a claims cohort and want to link them to an external death index using tokens. We first try a strong token recipe, then run a weaker recipe on whoever is left (a waterfall), and we split the cohort into patients with stable identifiers and more mobile patients to see whether linkage is even across groups and how much linkage error the weak recipe adds.

Dataset

Cohort-level linkage counts an analyst would assemble from the matched and unmatched token output.

Steps

• Strong recipe matches across both subgroups = 540 + 280 = 820 of the 1,000 patients.

• Strong-recipe match rate = 820 / 1000 = 0.82, so 180 patients did not link on the strong token alone.

• The weaker recipe rescues 60 more patients, so the overall match rate after the waterfall = (820 + 60) / 1000 = 0.88.

• The weak recipe is looser, so it injects false matches; at a precision of 0.90 the false matches = 60 * 0.10 = 6 wrong links.

• Look at selection - the stable subgroup links far better than the mobile subgroup, 540 / 600 = 0.90 versus 280 / 400 = 0.70, so the linked cohort over-represents stable-identifier patients.

Result

Overall match rate after the waterfall = 880/1000 = 0.88, but about 6 of the rescued links are false matches and the stable subgroup linked at 0.90 versus 0.70 for the mobile subgroup - so analyzing only the linked patients over-represents stable-identifier people and risks selection bias.

Timeline Spec

Title

One token-matched patient appearing across claims, EHR, and the death index

Window

Start

2021-01-01

End

2023-03-31

Label

Calendar span across three linked datasets

Events

• Label

  Claims enrollment (token match)

  Start

  2021-01-01

  Length Days

  730

  Quantity

  Token A

• Label

  EHR encounters (token match)

  Start

  2021-03-15

  Length Days

  615

  Quantity

  Token A

• Label

  SDOH vendor record (token match)

  Start

  2021-06-01

  Length Days

  1

  Quantity

  Token A

• Label

  Death-index record (token match)

  Start

  2023-02-10

  Length Days

  1

  Quantity

  Token A

Spans

• Kind

  exposed

  Start

  2021-01-01

  End

  2022-12-31

  Label

  Claims: continuous enrollment

• Kind

  followup

  Start

  2021-03-15

  End

  2022-11-20

  Label

  EHR: encounter coverage

Result

Label

One token links claims+EHR+mortality; cohort match rate 880/1000 = 0.88

Value

0.88

Runnable example

import pandas as pd

def linkage_quality(cohort: pd.DataFrame) -> dict:
    n = len(cohort)
    n_matched = int(cohort["matched"].sum())
    match_rate = n_matched / n

    # False match: linked but not actually the same person (precision failure).
    fm = int(((cohort["matched"]) & (~cohort["truly_same_person"])).sum())
    false_match_rate = fm / n_matched if n_matched else 0.0

    # False miss: truly the same person but left unmatched (recall failure).
    n_true = int(cohort["truly_same_person"].sum())
    miss = int(((~cohort["matched"]) & (cohort["truly_same_person"])).sum())
    false_miss_rate = miss / n_true if n_true else 0.0

    # Selection: match rate by subgroup exposes the linkable subpopulation.
    by_subgroup = (
        cohort.groupby("subgroup")["matched"].mean().round(3).to_dict()
    )

    # Records rescued only by the weak recipe carry the most false-match risk.
    weak = cohort[(cohort["matched"]) & (cohort["recipe"] == "B")]
    weak_false_match_rate = (
        float((~weak["truly_same_person"]).mean()) if len(weak) else 0.0
    )

    return {
        "n": n,
        "match_rate": round(match_rate, 3),
        "false_match_rate": round(false_match_rate, 3),
        "false_miss_rate": round(false_miss_rate, 3),
        "match_rate_by_subgroup": by_subgroup,
        "weak_recipe_false_match_rate": round(weak_false_match_rate, 3),
    }

library(data.table)

linkage_quality <- function(cohort) {
  setDT(cohort)
  n         <- nrow(cohort)
  n_matched <- sum(cohort$matched)
  n_true    <- sum(cohort$truly_same_person)

  match_rate <- n_matched / n
  fm   <- sum(cohort$matched & !cohort$truly_same_person)
  miss <- sum(!cohort$matched & cohort$truly_same_person)
  false_match_rate <- if (n_matched > 0) fm / n_matched else 0
  false_miss_rate  <- if (n_true > 0)    miss / n_true  else 0

  by_subgroup <- cohort[, .(match_rate = round(mean(matched), 3)), by = subgroup]

  weak <- cohort[matched == TRUE & recipe == "B"]
  weak_false_match_rate <- if (nrow(weak) > 0)
    mean(!weak$truly_same_person) else 0

  list(
    n = n,
    match_rate = round(match_rate, 3),
    false_match_rate = round(false_match_rate, 3),
    false_miss_rate = round(false_miss_rate, 3),
    match_rate_by_subgroup = by_subgroup,
    weak_recipe_false_match_rate = round(weak_false_match_rate, 3)
  )
}