Record or data linkage is a technique frequently used in diverse domains to aggregate data stored in different sources that presumably pertain to the same real world entity. Deterministic (key-based) or probabilistic (rulebased) linkage methods can be used to implement data linkage, being the second approach suitable when no common link attributes exist amongst the data sources involved. Depending on the volume of data being linked, indexing (or blocking) techniques should be used to reduce the number of pairwise comparisons that need to be executed to decide if a given pair of records match or not. In this paper, we discuss a new indexing scheme, based on term-frequency counts, deployed in our data linkage tool (AtyImo). We present our algorithm design and some metrics related to accuracy and efficiency (reduction ratio achieved during blocking construction), as well a comparative analysis with a predicatebased technique also used in AtyImo. Our results shows a very high level of accuracy and reduction in terms of pairwise comparison tasks.
In Public Health, this technique is frequently used to aggregate data from different
electronic health records (EHR) usually managed by governmental bodies within the
public health system. Throughout his life, an individual (or patient) has access to a diversity
of EHR systems that store specific data on clinical care episodes, symptoms and diseases,
prescribed medication and treatments, and associated outcomes. Being able to aggregate
these data is a crucial step to build the patient’s history, as well support different types
of studies, such as quasi-experimental analysis, clinical trials and longitudinal
(cohortbased) evaluations [
The scope of our work comprises the usage of term frequency-based indexing
to improve the accuracy and the scalability of our probabilistic data linkage tool —
AtyImo [
AtyImo is a Python-based data linkage tool implemented over Spark and CUDA able to explore highly distributed and hybrid (multicore CPUs + multi-GPU) parallel architectures, respectively. It is used at CIDACS to support data linkage tasks involving a huge population-based cohort (the 100 million cohort) and public health databases, as well the setup of a live birth cohort (around 80 million records) comprised by children diagnosed with microcephaly due to Zika infection. It is also used at UFBA to aggregate data from different sources within the Brazilian malaria ecosystem to support the design and validation of forecasting models applied to malaria epidemics.
AtyImo is structured as a 4-step pipelining implementing data quality assessment,
data pre-processing, record linkage (pairwise comparison) and accuracy assessment. The
data pre-processing step is responsible for data cleansing and harmonization, block
construction and anonymization. Blocking is a mandatory approach to reduce the number of
comparisons, specially in scenarios involving huge databases (cohorts) as ours. The basic
idea is to define some criteria to group records into blocks and perform comparisons only
among blocks presumably similar. Measuring the relative reduction of comparisons may
evidence the effectiveness of a blocking solution [
Besides scaling record linkage solutions over huge data sources by reducing
comparisons, another issue concerns the capacity of keeping a good accuracy level. To comply
with this requisite, a good indexing solution must apply criteria that increase pair
completeness, i.e. which records should be included in each block to keep comparisons and
increase accuracy [
In this work, we discuss a term frequency-based indexing technique implemented in our Spark-based version of AtyImo. We rely on this technique as an alternative to the existing approach based on predicates. Building a ranking of records with most terms in common can result in fewer and better comparisons than the predicates-based solution. We calculated reduction ratio and accuracy measures to compare the efficiency of our proposal with other indexing algorithms. The results show that term frequency indexing outperforms other existing solutions, decreasing the number of pairwise comparisons and the execution tume, while preserving good accuracy levels.
This paper is structured as follows: Section 2 briefly describe some existing tech1This work was supported by CNPq, FINEP, FAPESB, Bill and Melinda Gates Foundation (OPP1161996), The Royal Society (NF160879), National Institute for Health Research (RP-PG040710314) and also supported by the Wellcome Trust (086091/Z/08/Z) niques used for indexing. Section 3 presents our term-frequency indexing implementation and compare it with the predicates-based method used by the production version of AtyImo. Section 4 discuss some experimental results. Some related works are metioned in Section 5. Finally, section 6 brings some conclusions and current work directions.
There are several solutions to scale up record linkage by reducing unnecessary
comparisons [
Traditional blocking techniques are generally based on a blocking key which is created using attributes like first name, last name and date of birth, or some combination of them to split the data into buckets. Records that exactly match with the blocking key on each database are compared assuming their potential to be a true link. The reduction ratio of this approach depends on the discriminative power of the attributes used to build the blocking key.
However, this method can be very biased due to the nature of these attributes and imputation errors that can prevent true matches to be compared. To soften this, phonetic codes can be applied to nominal data and some normalization can be done on numerical data. The low complexity and the easy implementation make this strategy very useful in most situations.
This method is presented as multi-pass sorted neighborhood alternative and consists of building some predicate from fields or portions of them. Finally, a function uses this predicate to make a junction of disjunctions.
To illustrate, we can suppose a patient record including attributes like name, mother name, date of birth and gender. Some predicates can use the first name, birth year and gender. A second may contains the last name, first mother’s name and date of birth. So every record that agrees with the expression pf irstname ^ birthyear ^ genderq _ plastname ^ mothersf irstname ^ birthdateq will be part of the same block.
The use of predicate-based indexing can prevent input errors to separate true
matches from right blocks, thus increasing pair completeness. Other variants can learn the
best predicates to use [
The current version of AtyImo implements indexing through a predicate-based approach. This implementation comprises two predicates: pr1 “ pf irstname ^ pbirthday _ birthmonth _ birthyearqq _ plastname ^ pbirthday _ birthmonth _ birthyearqq and the second as pr2 “ ppf irstname ^ f irstmothersnameq ^ pbirthday_birthmonth_birthyearqq_pplastname^lastmothersnameq^pbirthday_ birthmonth _ birthyearqq.
Figura 1. Predicate-based blocking.
Let consider Bi a database with a finite set o X objects, described by attributes r “ x1, ..., xn. This solution inserted three new steps into AtyImo’s pipeline: indexing, exploration, and ranking procedures, as illustrated on Figure 2:
Figura 2. Term frequency-based approach used in AtyImo.
The indexing step intend to build a key´value structure by visiting every X P B1
(larger database) and collecting all terms as keys. The values correspond to every record’s
primary key (x1) whose contains the term. To cluster the terms with the same phonetics,
we use a custom implementation of Metaphone algorithm [
To every term extracted from an X P B2 (smaller database this time), we search the respective JSON file and concatenate their values into a vector of indexes vt. Very popular terms can make this phase too onerous, in order to meet this issue, we submit the processing of these JSON files to a distributed processing supported by pySpark, the Algorithm 1.
fpt,vtq
The term frequency is calculated by ∞ tPvt fpt1,vtq . After that, we sort vt to find the most
frequent B1’s primary keys to set up a ranking with the best N candidates to be compared
to some B2’s record. This approach aims to eliminate the variance of the comparisons
amount even to records which contain very popular terms. This work scope is limited to
indexing the data, search the best candidates and provide a comparison structure for the
further phases of AtyImo (well explained in [
Result: json files indexed initialization; while not at end of this document do read current; for current.split(;) to l do term– metaPTBR(l); createJsonFile(term) end end Algorithm 1: indexing step
Result: terms ranking initialization; while not at end of this document do read current; for current.split(;) to l do result– searchJsonFile(l); ranking.append(result) end end mostFrequencyTerms(ranking) Algorithm 2: exploration step
To evaluate our term frequency-based implementation, we have used samples from two
Brazilian governmental databases: SIM (mortality data, presented as the smaller
database) and SINASC (live births data, presented as the larger database), as summarized in
Table 1. These data are used as “gold standard” to validate our linkage and deduplication
routines, since they share a common key which refers to a death certificate. We expect
to retrieve 3.030 true match pairs among these databases after around 84 million pairwise
comparisons. Regarding the known true matches numbers, we understand it is a
realworld dataset with some impure data, which limits the identification of all true matches
without a specificity and sensitivity trade-off. Without blocking, AtyImo retrieves 3018
true matches. Further discussion on AtyImo’s accuracy is found in [
Tabela 1. Gold standard data set used for validation.
SIM 6,458 records SINASC 13,046 records Total of comparisons 84,251,068 records
Expected true positives 3,030 records
We use reduction ratio and pair completeness as the main measures to evaluate the
quality of our proposed indexing technique [
BLcs BLtm
RR “ 1 ´ T rs (1) P C “ T tm (2)
We have compared the predicate-based approach used by AtyImo (in its production version) against the new term frequency-based approach proposed in this work. Table 2 presents the distribution of blocks sizes for each indexing method. The predicate1 achieve smaller blocks due the discriminative power of attributes used. This result reinforce the need of well choose which portions of data will be submitted to the indexing technique. In spite of predicates steady improvement, the results of term frequency approach outperforms all the other compared solution. Since we have used N “ 100 to define how much pairwise comparisons will be made to every record on smaller database, the size of blocks became homogeneous.
Tabela 2. Size of generated blocks for each indexing technique method predicate 1 predicate 2 term frequecy database sb lb sb lb sb lb min 1 1 1 1 1 100 med 24 51 2 2 1 100 mean 43 88.38 8.289 11.57 1 100 max 1855 41528 87 611 1 100
Table 3 summarizes the results obtained for each method. The predicate1 got poor results of reduction ratio by performing almost half of all pairwise comparisons. Even with higher average block size, predicate1 execution only retrieve 2,382 from the 3,030 expected, which decrease it pair completeness to 0.786. Better results has been made by predicate2, which manage to get 0.996 of pair completeness with more discriminative and smaller blocks. The predicate2 achieved 3,018 true matches and 0,654 of reductions ratio. The best metrics were achieved by our indexing techinique based on phonetic encoded term frequency. Despite the major number of blocks, this approach obtained 3,020 true matches doing less comparisons. These results reflected on reduction ratio and pair completeness, getting 0.992 and 0.996, respectively.
Tabela 3. Results of each indexing techinique used.
predicate 1 predicate 2 term frequency true matches retrieved 2,382 3,018 3,020
number of blocks 5,806 6,432 6,458 number of comparisons 44,406,049 29,111,755 645,800 reduction ratio 0.472 0,654 0,992 pair completness 0.786 0.996 0.996
Our proposal of phonetic encoded term frequency to establish the best candidade pairs for linkage comparisons revealed efficient in terms of accuracy and runtime execution. Another major contribution of this work refers to perform indexing while allow the comparison methods to encode or encript the blocks, considering the privacy-preserving concern of AtyImo tool.
Record linkage tools frequently offer a set of methods to reduce the amount of
pairwise comparisons potentially appearing in big data scenarios. Most popular
tools [
Several indexing techniques usually employed to decrease record linkage
complexity were described and compared on [
Traditional blocking techniques, as well locality-based ones are discussed and
compared in [
Python provides the recordlinkage library that implements a full index approach based on the MultiIndex object provided in the Pandas library. This approch returns all pairwise combinations (product of the records present in both data sets). It is possible to provide a blocking key (column name) in order to reduce the number of blocks generated. The library also implements a sorted neighborhood approach.
In order to meet the requisites imposed by big data scenarios, AtyImo runs over
the pySpark library and offer two predicate-based indexing approaches to split the data
into blocks. These predicates put in the same block those records which agree with some
rules, like first name and birth date, or last name and mother’s name. Experiments show
a good accuracy level using this approaches [
Record linkage is a technique widely used in data mining and data warehousing applications to allow for the aggregation of data coming from disparate data sources. Big data scenarios impose significant challenges for data linkage tools. The growth of data sources and the need for increasing levels of accuracy open room to the development of novel solutions and the improvement of classical tools.
This work presented an extension of a cluster-based record linkage tool for indexing data using phonetic enconded term frequency. Results for accuracy and pairwise comparison are promising and outperforms existing, concurrent solutions. As future work, we plan to develop other techniques such as TF-IDF and unsupervised machine learning approaches.