In modern database construction, there are many scenarios in which multiple institutions work together to provide as much information as possible for each data point.  For example, a patient may receive a blood test at one hospital system and imaging data at another hospital system; similar issues may arise in a variety of other fields as well, including government, finance, and education.  In order to build a database that can utilize both the blood test data and imaging data in a more complete manner, we need methods that can identify when data from these multiple institutions belongs to the same individual or entity.  This is called record linkage.   

Traditionally, this can be done simply by linking certain data characteristics that, when combined, are likely to be unique.  Examples include a name, date of birth, or address, among others.  However, there are more complicated scenarios that can arise, such as if a person’s name was misspelled in one system or if there are rules that limit the amount of information that can be shared between institutions.  Because of this, there are many different categories and types of record linkage that are important to consider, including deterministic vs. probabilistic linkage, centralized vs. distributed systems, and privacy-preserving linkage (the main focus of this material).  In this learning module, we aim to provide learning materials that can help readers understand fundamental aspects of record linkage, provide technical foundations, and ultimately serve as a guide for a practical implementation of privacy-preserving record linkage. 

Acronyms and key definitions in this section: 

Record linkage –  

Before we dive into record linkage and the main topic of this module, privacy-preserving record linkage, we first need to demonstrate why there is a need for more complicated linkage techniques than directly comparing common identifying variables.  In general, these can be broadly categorized between practical considerations and regulatory or ethical reasons, both of which are discussed in more detail in this section. 

Practical considerations

While there are many realistic aspects of record linkage that can cause problems, one of the most fundamental is noisy data.  Noisy data refers to information that is, for some reason, not entirely accurate or consistent.  For example, suppose “John Smith” has to have both a blood test at Hospital A and a chest X-ray at Hospital B.  But when he checked in at Hospital A, there was a spelling mistake when his name was saved in the record system and is stored as “Jon Smith.” This would be a noisy data point caused by human error.  In addition to human error, there are a variety of other causes for noisy data, including changes to a person’s identity over time (e.g., moved addresses, changed last name), missing or incomplete data (e.g., one institution includes a middle initial, one does not), or inconsistent formatting (saving dates as MM/DD/YYYY vs. DD/MM/YYYY).  While these could potentially all be corrected on a small scale, in large-scale databases across multiple institutions, the only solution is to utilize techniques that can account for noisy data. 

The existence of increasingly large databases in modern times actually causes additional practical issues related to scalability.  Specifically, a direct comparison between every record in one database with every record of another database is very computationally expensive.  For example, if two databases each have 10 million records each (which is quite reasonable in modern standards), then comparing all of the records between the 2 would be  

10,000,000 𝑥 10,000,000=100,000,000,000,000=100 𝑄𝑢𝑎𝑑𝑟𝑖𝑙𝑙𝑖𝑜𝑛10,000,000 x 10,000,000=100,000,000,000,000=100 Quadrillion

Comparisons.  Including any additional databases would quickly make direct comparison too time-consuming to be practical.  Thus, on top of needing to account for noisy data, any record linkage solutions need to be able to be applied effectively at large scales.   

Finally, while direct comparison can be effective for well-structured data such as name, date of birth, and age, among others, there are more complex forms of data that need to be considered in modern computing.  One key example of this is imaging data, where we want to identify if an image (e.g., a CT scan) belongs to a certain person in the record system, but any direct comparison with an image record requires novel, unique considerations that direct comparison cannot achieve.   

While the practical considerations listed here are not exhaustive, they are only part of the reason why we need more advanced record linkage techniques.  The other primary motivation is regulatory concerns regarding the ethical handling of data, which often need to be addressed simultaneously with the other practical restrictions. 

Regulatory and ethical considerations

In recent years, many laws and regulations have been formulated regarding the appropriate use and management of potentially sensitive information.  In healthcare, a key example of this is the management of personally identifiable information (PII), which is restricted in the U.S.A. by the Health Insurance Portability and Accountability Act (HIPAA) or by the General Data Protection Regulation (GDPR) in Europe.   These laws provide guidance on when and how certain forms of data can be shared and what level of consent or justification is needed prior to transferring data between institutions.  

This is applicable to record linkage in that many variables that would be useful in matching data from multiple institutions fall into the PII category (e.g., names), and while it may be possible to match data without using PII, it will often be significantly more difficult and inconsistent.  Thus, we need to develop techniques that disguise data such that it no longer contains sensitive information and can legally be transferred while maintaining the ability to match records between institutions under systematic constraints.   

Acronyms and key definitions in this section: 

HIPAA –  

GDPR –  

Noisy data –  

PII–