Methodology

In the first step, raw identifying fields were cleaned and standardised to improve comparability across records. This included normalisation of names (e.g., removing punctuation, standardising capitalisation, handling common prefixes) and transformation of dates of birth and age fields into comparable formats. Implausible values were flagged, and missingness was explicitly retained rather than imputed, allowing downstream steps to account for uncertainty.

Given the enormous size of the NHLS dataset, it is computationally infeasible to compare every record to every other record. The algorithm therefore uses blocking strategies to limit comparisons to plausible candidate pairs. Records are grouped into overlapping blocks based on combinations of key attributes (such as name and surname fragments, year of birth, sex, or facility). This ensures high sensitivity by allowing records to appear in multiple blocks, while dramatically reducing the number of pairwise comparisons required.

Within each block, candidate record pairs are compared using a set of string similarity metrics and exact or near-exact matches across identifying variables. For example, names are compared using approximate string matching algorithms, while sex and date-of-birth fields contribute agreement or disagreement weights. These comparisons are combined into an overall similarity score, reflecting the probability that two records belong to the same individual. Rather than applying a single hard threshold to determine whether two records match, similarity scores are used to construct weighted edges between records, preserving information about varying degrees of match certainty.

In the final step, records are represented as nodes in a graph, with weighted edges connecting records that are sufficiently similar. The algorithm identifies clusters (i.e., connected components) within this graph, where each cluster represents a likely unique individual. This graph-based approach allows the algorithm to resolve complex linkage scenarios, for example, where record A closely matches B, and B closely matches C, even if A and C do not directly match well. Additionally, this approach provides a principled approach to identify clusters that are too large to represent individual patients and to break them up into smaller clusters.

This method is particularly powerful in the presence of missing or inconsistent identifiers and avoids fragmentation of patient histories that would occur with pairwise-only linkage.