Record linkage

Record linkage (also known as data matching, data linkage, entity resolution, and many other terms) is the task of finding records in a data set that refer to the same entity across different data sources (e.g., data files, books, websites, and databases). Record linkage is necessary when joining different data sets based on entities that may or may not share a common identifier (e.g., database key, URI, National identification number), which may be due to differences in record shape, storage location, or curator style or preference. A data set that has undergone RL-oriented reconciliation may be referred to as being cross-linked.

Naming conventions

"Record linkage" is the term used by statisticians, epidemiologists, and historians, among others, to describe the process of joining records from one data source with another that describe the same entity. However, many other terms are used for this process. Unfortunately, this profusion of terminology has led to few cross-references between these research communities.

Computer scientists often refer to it as "data matching" or as the "object identity problem". Commercial mail and database applications refer to it as "merge/purge processing" or "list washing". Other names used to describe the same concept include: "coreference/entity/identity/name/record resolution", "entity disambiguation/linking", "fuzzy matching", "duplicate detection", "deduplication", "record matching", "(reference) reconciliation", "object identification", "data/information integration" and "conflation".

While they share similar names, record linkage and linked data are two separate approaches to processing and structuring data. Although both involve identifying matching entities across different data sets, record linkage standardly equates "entities" with human individuals; by contrast, Linked Data is based on the possibility of interlinking any web resource across data sets, using a correspondingly broader concept of identifier, namely a URI.

History

The initial idea of record linkage goes back to Halbert L. Dunn in his 1946 article titled "Record Linkage" published in the American Journal of Public Health.

Howard B. Newcombe then laid the probabilistic foundations of modern record linkage theory in a 1959 article in Science, giving greater weight to agreements on less frequent values. These ideas were formalized in 1969 by Ivan Fellegi and Alan Sunter in "A Theory for Record Linkage". They showed that a rule comparing a likelihood ratio with upper and lower thresholds, with pairs in between sent to clerical review, minimizes the number of pairs needing review for chosen limits on the rates of false matches and missed matches. This is a frequentist formulation, stated in terms of error rates rather than the prior probability of a match. Bayes' theorem gives a related interpretation: combining the likelihood ratio with the prior odds gives the posterior odds that two records match. Fellegi and Sunter also gave methods for estimating the required probabilities from the data being linked. The Fellegi–Sunter model remains the mathematical foundation for many record linkage applications.

Methods

Data preprocessing

Record linkage is highly sensitive to the quality of the data being linked, so all data sets under consideration (particularly their key identifier fields) should ideally undergo a data quality assessment before record linkage. Many key identifiers for the same entity can be presented quite differently between (and even within) data sets, which can greatly complicate record linkage unless understood ahead of time. For example, key identifiers for a man named William J. Smith might appear in three different data sets as follows:

Data set	Name	Date of birth	City of residence
Data set 1	William J. Smith	1/2/73	Berkeley, California
Data set 2	Smith, W. J.	1973.1.2	Berkeley, CA
Data set 3	Bill Smith	Jan 2, 1973	Berkeley, Calif.

In this example, the different formatting styles lead to records that look different but in fact all refer to the same entity with the same logical identifier values. Most, if not all, record linkage strategies would result in more accurate linkage if these values were first normalized or standardized into a consistent format (e.g., all names are "Surname, Given name", and all dates are "YYYY/MM/DD"). Standardization can be accomplished through simple rule-based data transformations or more complex procedures such as lexicon-based tokenization and probabilistic hidden Markov models. Several of the packages listed in the Software Implementations section provide some of these features to simplify the process of data standardization.

Entity resolution

Entity resolution is an operational intelligence process, typically powered by an entity resolution engine or middleware, whereby organizations can connect disparate data sources with a view to understand possible entity matches and non-obvious relationships across multiple data silos. It analyzes all of the information relating to individuals and/or entities from multiple sources of data, and then applies likelihood and probability scoring to determine which identities are a match and what, if any, non-obvious relationships exist between those identities.

Entity resolution engines are typically used to uncover risk, fraud, and conflicts of interest, but are also useful tools for use within customer data integration (CDI) and master data management (MDM) requirements. Typical uses for entity resolution engines include terrorist screening, insurance fraud detection, USA Patriot Act compliance, organized retail crime ring detection and applicant screening.

For example, across different data silos – employee records, vendor data, watch lists, etc. – an organization may have several variations of an entity named ABC, which may or may not be the same individual. These entries may, in fact, appear as ABC1, ABC2, or ABC3 within those data sources. By comparing similarities between underlying attributes such as address, date of birth, or social security number, the user can eliminate some possible matches and confirm others as very likely matches.

Entity resolution engines then apply rules, based on common sense logic, to identify hidden relationships across the data. In the example above, perhaps ABC1 and ABC2 are not the same individual, but rather two distinct people who share common attributes such as address or phone number.

Data matching

While entity resolution solutions include data matching technology, many data matching offerings do not fit the definition of entity resolution. Here are four factors that distinguish entity resolution from data matching, according to John Talburt, director of the UALR Center for Advanced Research in Entity Resolution and Information Quality:

• Works with both structured and unstructured records, and it entails the process of extracting references when the sources are unstructured or semi-structured
• Uses elaborate business rules and concept models to deal with missing, conflicting, and corrupted information
• Utilizes non-matching, asserted linking (associate) information in addition to direct matching
• Uncovers non-obvious relationships and association networks (i.e. who's associated with whom)

In contrast to data quality products, more powerful identity resolution engines also include a rules engine and workflow process, which apply business intelligence to the resolved identities and their relationships. These advanced technologies make automated decisions and impact business processes in real time, limiting the need for human intervention.

Deterministic record linkage

The simplest kind of record linkage, called deterministic or rules-based record linkage, generates links based on the number of individual identifiers that match among the available data sets. Two records are said to match via a deterministic record linkage procedure if all or some identifiers (above a certain threshold) are identical. Deterministic record linkage is a good option when the entities in the data sets are identified by a common identifier, or when there are several representative identifiers (e.g., name, date of birth, and sex when identifying a person) whose quality of data is relatively high.

As an example, consider two standardized data sets, Set A and Set B, that contain different bits of information about patients in a hospital system. The two data sets identify patients using a variety of identifiers: Social Security Number (SSN), name, date of birth (DOB), sex, and ZIP code (ZIP). The records in two data sets (identified by the "#" column) are shown below:

Data Set	#	SSN	Name	DOB	Sex	ZIP
Set A	1	000956723	Smith, William	1973/01/02	Male	94701
	2	000956723	Smith, William	1973/01/02	Male	94703
	3	000005555	Jones, Robert	1942/08/14	Male	94701
	4	123001234	Sue, Mary	1972/11/19	Female	94109
Set B	1	000005555	Jones, Bob	1942/08/14
	2		Smith, Bill	1973/01/02	Male	94701

The most simple deterministic record linkage strategy would be to pick a single identifier that is assumed to be uniquely identifying, say SSN, and declare that records sharing the same value identify the same person while records not sharing the same value identify different people. In this example, deterministic linkage based on SSN would create entities based on A1 and A2; A3 and B1; and A4. While A1, A2, and B2 appear to represent the same entity, B2 would not be included in the match because it is missing a value for SSN.

Handling exceptions such as missing identifiers involves the creation of additional record linkage rules. One such rule in the case of a missing SSN might be to compare name, date of birth, sex, and ZIP code with other records in hopes of finding a match. In the above example, this rule would still not match A1/A2 with B2 because the names are still slightly different: standardization put the names into the proper (Surname, Given name) format but could not discern "Bill" as a nickname for "William". Running names through a phonetic algorithm such as Soundex, NYSIIS, or metaphone can help to resolve these types of problems. However, they may still stumble over surname changes as a result of marriage or divorce, but then B2 would be matched only with A1 since the ZIP code in A2 is different. Thus, another rule would need to be created to determine whether differences in particular identifiers are acceptable (such as ZIP code) and which are not (such as date of birth).

As this example demonstrates, even a small decrease in data quality or a small increase in the complexity of the data can result in a very large increase in the number of rules necessary to link records properly. Eventually, these linkage rules will become too numerous and interrelated to build without the aid of specialized software tools. In addition, linkage rules are often specific to the nature of the data sets they are designed to link together. One study was able to link the Social Security Death Master File with two hospital registries from the Midwestern United States using SSN, NYSIIS-encoded first name, birth month, and sex, but these rules may not work as well with data sets from other geographic regions or with data collected on younger populations. Thus, continuous maintenance testing of these rules is necessary to ensure they continue to function as expected as new data enter the system and need to be linked. New data that exhibit different characteristics than were initially expected could require a complete rebuilding of the record linkage rule set, which could be a very time-consuming and expensive endeavor.

Probabilistic record linkage

Probabilistic record linkage, sometimes called fuzzy matching, identifies records that refer to the same entity by weighing the evidence from multiple identifiers, such as names, dates of birth, and addresses. Each comparison is scored by how much more likely it is among true matches than among non-matches, a likelihood ratio. By Bayes' theorem, these ratios update the odds that two records match, so rare agreements (such as an uncommon surname) count for more than common ones.

Not all agreements provide the same evidence. Suppose, for illustration, that matching records have the same surname 90% of the time, allowing for typographical errors, spelling variants, name changes, missing values, and other differences. If an unrelated record has a 1% chance of also containing "Smith" but only a 1-in-100,000 chance of also containing "Lebowski", agreement on Smith is 90 times as likely among matching records as among unrelated records, while agreement on Lebowski is 90,000 times as likely:

${\frac {0.90}{0.01}}=90,\qquad {\frac {0.90}{0.00001}}=90{,}000.$

The Lebowski agreement therefore provides much stronger evidence of a match because it is far less likely to occur by chance.

This is an application of Bayes' theorem in odds form. If M denotes the hypothesis that the records match, U that they do not match, and E the observed evidence, then:

${\frac {P(M\mid E)}{P(U\mid E)}}={\frac {P(M)}{P(U)}}{\frac {P(E\mid M)}{P(E\mid U)}}.$

The odds that the records match before the evidence is considered are the prior odds, written $P(M)/P(U)$. The odds after considering the evidence are the posterior odds, written $P(M\mid E)/P(U\mid E)$. The likelihood ratio, $P(E\mid M)/P(E\mid U)$, describes how the evidence changes the odds. The factors of 90 and 90,000 in the surname example are likelihood ratios.

Following Fellegi and Sunter, the m-probability is the probability that an identifier agrees when the records match, $m=P(G\mid M)$, where G is agreement on that identifier. The u-probability is the probability that it agrees by chance when they do not, $u=P(G\mid U)$. The likelihood ratio for an agreement is $m/u$; for a disagreement, it is $(1-m)/(1-u)$. The logarithm of this ratio is called a linkage weight. For example, if surnames agree in 90% of matching pairs and 1% of non-matching pairs, disagreement has a likelihood ratio of $0.10/0.99\approx 0.10$, reducing the odds of a match about tenfold. The u-probability can also be refined for particular values. In the surname example, $m=0.90$, while the value-specific u-probabilities are 0.01 for Smith and 0.00001 for Lebowski, so the less common surname provides stronger evidence of a match. Both probabilities can be estimated from known matches or from the data being linked, often using the expectation–maximization algorithm.

Approximate string matches can be handled in the same framework. For example, "Smith" and "Smyth" have a Levenshtein edit distance of 1. If an edit distance of exactly 1 occurs in 5% of matching surname pairs but only 0.05% of non-matching pairs, that degree of similarity is 100 times more likely for a match. Its likelihood ratio is therefore $0.05/0.0005=100$, so it multiplies the odds of a match by 100. Other string comparators, such as Jaro–Winkler, can be used in the same way.

The prior odds reflect how rare true matches are among the pairs being compared. For example, if two files of 1,000 records each describe the same 1,000 people, then of the 1,000,000 possible record pairs, 1,000 are matches and 999,000 are not, so the prior odds that a randomly chosen pair matches are 1 to 999. Continuing the surname example, agreement on Smith has a likelihood ratio of 90. If the records also agree on birth month, and matching pairs agree on birth month with probability 0.95 while non-matching pairs do so with probability 1/12, the birth-month likelihood ratio is 11.4. Assuming conditional independence (see below), the combined likelihood ratio is $90\times 11.4=1026$. Applying that evidence to the prior odds gives

${\frac {1}{999}}\times 1026\approx 1.03.$

Thus the posterior odds are approximately 1.03 to 1, corresponding to a posterior match probability of about 0.51. Although the observed evidence strongly favors a match, it only slightly outweighs the very low prior odds. Had the records instead agreed on Lebowski, the combined likelihood ratio would be $90{,}000\times 11.4=1{,}026{,}000$, giving posterior odds of about 1,027 to 1, a match probability of about 0.999.

Multiplying the likelihood ratios in this way assumes that the comparison outcomes are conditionally independent given whether the records match. This is the simplifying assumption used by a naive Bayes classifier. Under this assumption, likelihood ratios can be multiplied, or equivalently their logarithmic weights can be added. However, the assumption may be inaccurate when identifiers are associated—for example, when first and last names are correlated with one another, or when names are associated with birth year. Models that estimate probabilities jointly for combinations of identifiers can relax this assumption.

The combined linkage score is then compared with decision thresholds. Record pairs with scores above an upper threshold are classified as matches, those below a lower threshold as non-matches, and those between the thresholds as possible matches that may require manual review. Raising the upper threshold produces fewer false links but misses more true matches; widening the gap between the thresholds reduces both errors at the cost of more manual review.

Blocking

Comparing every record in one file with every record in another quickly becomes computationally infeasible: two files of one million records each yield 10¹² candidate pairs. Blocking reduces this cost by comparing only pairs that agree on one or more selected identifiers, called blocking keys. Blocking is used with both deterministic and probabilistic linkage. Its cost is that true matches that disagree on a blocking key are never compared. Because the excluded pairs are mostly non-matches, true matches make up a larger share of the pairs that are compared, so the prior odds of a match are higher.

For example, blocking on a phonetically coded surname and ZIP code greatly reduces the number of comparisons but misses people whose surname or ZIP code has changed, such as through marriage or relocation. Blocking on birth month is more stable but creates only twelve groups, cutting comparisons only about twelvefold, which for very large files may still leave too many pairs. Systems therefore often use several blocking passes with different keys, so that a match missed by one pass can be found by another.

Machine learning

In recent years, a variety of machine learning techniques have been used in record linkage. Under the conditional independence assumption described above, field-by-field Fellegi–Sunter scoring has the same factorized form as a naive Bayes classifier. When labeled training data is available, other supervised methods can be used, such as a single-layer perceptron, random forests, and SVMs; some studies have reported higher accuracy for such supervised methods.

Human-machine hybrid record linkage

High quality record linkage often requires a human–machine hybrid system to safely manage uncertainty in the ever changing streams of chaotic big data. Recognizing that linkage errors propagate into the linked data and its analysis, interactive record linkage systems have been proposed. Interactive record linkage is defined as people iteratively fine-tuning the results from the automated methods and managing the uncertainty and its propagation to subsequent analyses. The main objectives of interactive record linkage systems is to manually resolve uncertain linkages and validate the results until it is at acceptable levels for the given application. Variations of interactive record linkage that enhance privacy during the human interaction steps have also been proposed.

Privacy-preserving record linkage

Record linkage is increasingly required across databases held by different organisations, where the complementary data held by these organisations can, for example, help to identify patients who are susceptible to certain adverse drug reactions (linking hospital, doctor, and pharmacy databases). In many such applications, however, the databases to be linked contain sensitive information about people which cannot be shared between the organisations.

Privacy-preserving record linkage (PPRL) methods have been developed to link databases without the need to share the original sensitive values between the organisations that participate in a linkage. In PPRL, generally the attribute values of records to be compared are encoded or encrypted in some form. A popular such encoding technique used are Bloom filter, which allows approximate similarities to be calculated between encoded values without the need for sharing the corresponding sensitive plain-text values. At the end of the PPRL process only limited information about the record pairs classified as matches is revealed to the organisations that participate in the linkage process. The techniques used in PPRL must guarantee that no participating organisation, nor any external adversary, can compromise the privacy of the entities that are represented by records in the databases being linked.

Mathematical model

Following Fellegi and Sunter, let A and B be two populations of entities that may overlap, with elements a and b. Let $\alpha (a)$ and $\beta (b)$ denote the records of those entities in two files, each with $K$ characteristics. The set of pairs that represent the same entity is defined by

$M=\left\{(a,b);a=b;a\in A;b\in B\right\}$

and its complement, the set $U$ of pairs representing different entities, is

$U=\{(a,b);a\neq b;a\in A;b\in B\}$.

A vector, $\gamma$ is defined that contains the coded agreements and disagreements on each characteristic:

$\gamma \left[\alpha (a),\beta (b)\right]=\{\gamma ^{1}\left[\alpha (a),\beta (b)\right],...,\gamma ^{K}\left[\alpha (a),\beta (b)\right]\}$

where $K$ is a subscript for the characteristics (sex, age, marital status, etc.) in the files. The conditional probabilities of observing a specific vector $\gamma$ given $(a,b)\in M$, $(a,b)\in U$ are defined as

$m(\gamma )=P\left\{\gamma \left[\alpha (a),\beta (b)\right]|(a,b)\in M\right\}=\sum _{(a,b)\in M}P\left\{\gamma \left[\alpha (a),\beta (b)\right]\right\}\cdot P\left[(a,b)|M\right]$

and

$u(\gamma )=P\left\{\gamma \left[\alpha (a),\beta (b)\right]|(a,b)\in U\right\}=\sum _{(a,b)\in U}P\left\{\gamma \left[\alpha (a),\beta (b)\right]\right\}\cdot P\left[(a,b)|U\right],$ respectively.

Fellegi and Sunter showed that the optimal decision rule compares the likelihood ratio $m(\gamma )/u(\gamma )$ with an upper and a lower threshold. When the components of $\gamma$ are conditionally independent, this ratio is the product of the single-identifier likelihood ratios described in § Probabilistic record linkage.

Applications

Master data management

Most Master data management (MDM) products use a record linkage process to identify records from different sources representing the same real-world entity. This linkage is used to create a "golden master record" containing the cleaned, reconciled data about the entity. The techniques used in MDM are the same as for record linkage generally. MDM expands this matching not only to create a "golden master record" but also to infer relationships. (i.e. a person has the same/similar surname and same/similar address, this might imply they share a household relationship).

Data warehousing and business intelligence

Record linkage plays a key role in data warehousing and business intelligence. Data warehouses serve to combine data from many different operational source systems into one logical data model, which can then be subsequently fed into a business intelligence system for reporting and analytics. Each operational source system may have its own method of identifying the same entities used in the logical data model, so record linkage between the different sources becomes necessary to ensure that the information about a particular entity in one source system can be seamlessly compared with information about the same entity from another source system. Data standardization and subsequent record linkage often occur in the "transform" portion of the extract, transform, load (ETL) process.

Historical research

Record linkage is important to social history research since most data sets, such as census records and parish registers were recorded long before the invention of National identification numbers. When old sources are digitized, linking of data sets is a prerequisite for longitudinal study. This process is often further complicated by a lack of standard spelling of names, family names that change according to place of dwelling, changing of administrative boundaries, and problems of checking the data against other sources. Record linkage was among the most prominent themes in the History and computing field in the 1980s, but has since been subject to less attention in research.

Medical practice and research

Record linkage is an important tool in creating data required for examining the health of the public and of the health care system itself. It can be used to improve data holdings, data collection, quality assessment, and the dissemination of information. Data sources can be examined to eliminate duplicate records, to identify under-reporting and missing cases (e.g., census population counts), to create person-oriented health statistics, and to generate disease registries and health surveillance systems. Some cancer registries link various data sources (e.g., hospital admissions, pathology and clinical reports, and death registrations) to generate their registries. Record linkage is also used to create health indicators. For example, fetal and infant mortality is a general indicator of a country's socioeconomic development, public health, and maternal and child services. If infant death records are matched to birth records, it is possible to use birth variables, such as birth weight and gestational age, along with mortality data, such as cause of death, in analyzing the data. Linkages can help in follow-up studies of cohorts or other groups to determine factors such as vital status, residential status, or health outcomes. Tracing is often needed for follow-up of industrial cohorts, clinical trials, and longitudinal surveys to obtain the cause of death and/or cancer. An example of a successful and long-standing record linkage system allowing for population-based medical research is the Rochester Epidemiology Project based in Rochester, Minnesota.

Criticism of existing software implementations

The main reasons cited are:

• Project costs: costs typically in the hundreds of thousands of dollars
• Time: lack of enough time to deal with large-scale data cleansing software
• Security: concerns over sharing information, giving an application access across systems, and effects on legacy systems
• Scalability: Due to the absence of unique identifiers in records, record linkage is computationally expensive and difficult to scale.
• Accuracy: Changing business data and capturing all rules for linking is a tough and extensive exercise

See also

• Capacity optimization
• Content-addressable storage
• Data deduplication
• Delta encoding
• Entity linking
• Entity–attribute–value model
• Identity resolution
• Linked data
• Named-entity recognition
• Open data
• Schema matching
• Single-instance storage
• Author Name Disambiguation

External links

• Data Linkage Project at Penn State, USA
• Stanford Entity Resolution Framework
• Dedoop - Deduplication with Hadoop Archived 2016-08-06 at the Wayback Machine
• Privacy Enhanced Interactive Record Linkage at Texas A&M University