Private medical record linkage with approximate matching.

Elizabeth Durham, Yuan Xue, Murat Kantarcıoğlu, Bradley MalinPubMed 2010

TL;DR

This paper tackles the challenge of accurately linking patient medical records while preserving privacy. They introduce a novel approach that combines approximate string matching using Bloom filters with a probabilistic record linkage algorithm, significantly improving accuracy over existing methods on real-world medical data.

What Problem Does This Paper Address?

Healthcare systems are inherently decentralized, leading to fragmented patient medical data spread across different institutions. To enable comprehensive patient care and unbiased research, these records need to be linked. However, regulations like HIPAA require patient data to be de-identified before sharing, which complicates record linkage. Traditional record linkage methods often rely on exact matches of identifiers, which are brittle and fail when data contains errors or variations. This paper addresses the critical need for a privacy-preserving record linkage method that can handle these imperfections and accurately identify matching records in de-identified datasets.

Methods

The core of this research is the development of an Approximate Private Record Linkage (APPROX-PROB) method. This approach builds upon the established Fellegi-Sunter probabilistic record linkage framework but introduces two key innovations:

  1. Approximate Field Comparison: Instead of requiring exact matches for fields (like names or addresses), this method uses an approximate string comparison technique. They specifically leverage Bloom filters to represent the bigrams (pairs of adjacent characters) within a string. This allows for a measure of similarity between strings even if they aren't identical. The similarity is then quantified using the Dice coefficient.
  2. Integration with Probabilistic Linkage: The approximate similarity scores generated by the Bloom filters are then fed into the Fellegi-Sunter model. This model calculates a linkage score for each record pair based on the probabilities of agreement for each field, given whether the pair is a match or not. The APPROX-PROB method adapts this by using continuous similarity scores instead of binary agreement/disagreement.

For comparison, they also implemented and evaluated two baseline methods:

  • BIN-DET (Binary Deterministic): A rule-based approach requiring exact matches on a few key fields.
  • BIN-PROB (Binary Probabilistic): The standard Fellegi-Sunter model using exact field comparisons.

Datasets

The study utilized a dataset of 100,000 patient identifiers and demographics from the Vanderbilt University Medical Center's StarChart electronic medical record system. To simulate real-world data imperfections, they created corrupted versions of these records by introducing errors such as optical character recognition errors, phonetic errors, and typographic errors. They generated 100 pairs of datasets (Aᵢ and Bᵢ), each containing 1,000 records, where Bᵢ was a corrupted version of Aᵢ. This resulted in a total of over 100,000 records and approximately 100 million record pairs for evaluation.

Key Insights and Ideas

  • Approximate matching is crucial for real-world data: The paper strongly demonstrates that relying on exact matches for patient identifiers is insufficient due to common data errors and variations. Approximate matching, even in a privacy-preserving context, is essential for accurate record linkage.
  • Bloom filters offer a privacy-preserving similarity measure: The use of Bloom filters for string comparison is a clever way to enable approximate matching without revealing the actual string content. This is a significant step towards private record linkage.
  • Probabilistic linkage benefits from approximate comparisons: By integrating approximate similarity scores into a probabilistic framework, the authors show that the linkage algorithm can better handle noisy data and achieve higher accuracy.
  • Trade-offs exist but are manageable: While the approximate method incurs slightly higher computational costs, the authors argue that these are reasonable given the privacy guarantees and the significant improvement in accuracy.

Key Results

The APPROX-PROB method demonstrated a statistically significant improvement in record linkage performance:

  • Sensitivity: The APPROX-PROB method achieved an average sensitivity of 1 ± 0, meaning it correctly identified virtually all true matches. This was a substantial improvement over BIN-DET (0.14 ± 0.01) and slightly better than BIN-PROB (0.97 ± 0.007).
  • Specificity: All methods achieved high specificity (correctly identifying non-matches), with APPROX-PROB at 1 ± 1-6 and BIN-PROB at 1 ± 6-6.
  • Improved handling of misclassifications: APPROX-PROB was able to correctly classify about 30 out of 37 record pairs that BIN-PROB misclassified as false negatives.
  • Runtime: The field comparison for APPROX-PROB was slightly longer (808 ± 141 seconds) compared to BIN-PROB (644 ± 9 seconds), but the authors deemed it reasonable for a privacy-preserving method.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Parameter Tuning: The current study used a "best-case scenario" where true match statuses were known, allowing for exact calculation of conditional probabilities for the Fellegi-Sunter algorithm. In real-world applications without this knowledge, investigating the accuracy of parameter estimation (e.g., using the Expectation Maximization algorithm) is crucial.
  • Handling Nicknames and Name Changes: The current approach does not explicitly address variations like nicknames or last name changes due to marriage, which are common in medical data.
  • Blocking for Large Datasets: For very large datasets, record linkage is typically preceded by a "blocking" step to reduce the number of comparisons. The integration of blocking into a private record linkage method is identified as an open research question.
  • Bloom Filter Parameter Optimization: The authors suggest that tuning Bloom filter parameters (vector length, number of hash functions) based on field characteristics could further enhance performance.

Summary updated

Abstract

Federal regulations require patient data to be shared for reuse in a de-identified manner. However, disparate providers often share data on overlapping populations, such that a patient's record may be duplicated or fragmented in the de-identified repository. To perform unbiased statistical analysis in a de-identified setting, it is crucial to integrate records that correspond to the same patient. Private record linkage techniques have been developed, but most methods are based on encryption and preclude the ability to determine similarity, decreasing the accuracy of record linkage. The goal of this research is to integrate a private string comparison method that uses Bloom filters to provide an approximate match, with a medical record linkage algorithm. We evaluate the approach with 100,000 patients' identifiers and demographics from the Vanderbilt University Medical Center. We demonstrate that the private approximation method achieves sensitivity that is, on average, 3% higher than previous methods.
BibTeX
@inproceedings{durham2010private,
  author = {Elizabeth Durham and Yuan Xue and Murat Kantarcıoğlu and Bradley Malin},
  title = {{Private medical record linkage with approximate matching.}},
  booktitle = {PubMed},
  year = {2010},
}

Loading related content...

Figure