The main idea of matching is to check every possible pair of records
and decide wheter or not they match each other. This means that for a set of
records one gets
pairs to process.
There are three main parts of this process that can and need to be configured:
- blocking indexes method,
- attribute comparison method,
- score classification method.
Blocking indexes divide the whole dataset into subsets where
one or more blocking attributes have the same value, e.g. subsets with
the same postal code, the same last name and age or the same birth
month. Processing subsets saves much time in comparison to processing
the whole set as a one block, e.g. when the data is divided into blocks
with the same birth month, as a result one gets 12 smaller blocks.
Finding all the pairs inside these block results in approximately
which equals to
which is about 12 times less than for one huge undivided block.
Blocking indexes should be based on columns that are not likely to change over time (like birth date or first name) and that have no or little missing values and errors. It is common practice to define two or more blocking indexes and to look for matching pairs using different blocking index in consecutive passes.
Generally, it is a good idea to keep the block size moderate - when it is too big the number of pairs being processed will be too large. On the other hand, when the block size is too small some true matching pairs may be missed. The trade-off between the data set size (tightly connected with the computation time) and the accuracy of results has to be considered.
The second step of deduplication/linkage process is attribute comparison among the pairs specified in the previous step. Basically, it means deciding wheter two values are similar - which might be expressed as a fraction from the (0, 1) range, usually taken with some tolerance.
The m probability is defined as:
This value has to be estimated by an expert or based on the expected quality of the data. This can also be a function of the attribute's value if the probability distribution for the given attribute is not uniform.
The second value, the u probability, is defined as follows:
This is a measure of accidental data equality which can be estimated as
where 
is the number of different (distinct) values.
More information concerning these probabilities can be found in the Fellegi and Sunter, 1969.
From the m and u values the agreement and disagreement weights can be calculated. The agreement weight is defined as:
and the disagreement weight:
Assuming that the m probability is greater than the u probability, the agreement weight is greater than zero and the disagreement weight is less than zero.
After the m and u probabilites are estimated the similarity of attributes among the processed pairs is evaluated. There are many different methods which often depend on the attribute class/category, e.g. string, date, time, numerical. A number of string comparison methods are available, including: strict (wheter the strings are identical) or approximate (e.g. jaro, winkler, levenshtein).
A comparison method should measure the similarity of two values and return a value from the (0,1) range, where 0 means "completely different" and 1 means "identical". Some of the methods, such as strict string comparison, may return only 0 and 1 without any intermediate values.
The last part is creating a vector of similarity measure values. For every attribute there is a corresponding value in the vector. When the comparison method returns only 0 and 1 the disagreement and agreement weights are put into the vector, respectively. When the comparison method returns a real number from the (0,1) range, the final value may be computed as follows:
where the similarity is the similarity measure value of the attribute.
The last step is the classification of records which is done based on the weight vectors. There can be many methods of aggregating the vector values into a decision score. The classical one proposed by Fellegi and Sunter (see Fellegi & Sunter) is a simple sum of the values which can be interpretated as something close to the logarithm of probability that the given records are a true match.
The final score is then compared with two cutoffs:
and
.
If the given final value is greater than or equal to
then the records are considered to be a match. If the value is less than
or equal to
then then records are considered to be a non-match. All the pairs with
the final classification value between these two thresholds have to be
reviewed by a human operator.