Research in the social sciences is increasingly based on large and complex data collections, where individual data sets from different domains need to be linked to allow advanced analytics. A popular type of data used in such a context are historical registries containing birth, death, and marriage certificates. Individually, such data sets however limit the types of studies that can be conducted.

Specifically, it is impossible to track individuals, families, or households over time. Once such data sets are linked and family trees are available it is possible to, for example, investigate how education, health, mobility, and employment influence the lives of people over two or even more generations.

Historical record linkage involves the linkage of records from historical censuses, as well as birth, death, and marriage certificates, to construct longitudinal data sets about a population. This problem has been studied in the past two decades by researchers working in different domains.

The linkage of historical records is challenging because of data quality issues and because often there are no ground truth data available. Unsupervised techniques need to be employed, which generally are based on similarity graphs generated by comparing individual records.

This page is dedicated to presenting the novel research conducted by us, to address the many challenges and limitations in the area of historical record linkage and record linkage in general.

We proposed two graph based clustering algorithms for record linkage, which incorporate constraints implied by time differences (known as temporal constraints). For example, when we attempt to find groups of siblings in a dataset, we would refrain from linking two records with a five month difference between birth dates, because we know that biologically it is impossible for the same mother to have two children five months apart. In previous work related to record linkage, such constraints were not considered. We have shown with our experiemnts that superior linkage results can be achieved with our proposed temporal clustering approaches.
The clustering algorithms we proposed are as follows:

Star clustering first aims to find the nodes that best represent a cluster, where these are the nodes that have the highest average similarity to their neighbouring nodes and also the highest number of neighbours in a similarity graph G. Cluster centers are identified iteratively, such that an unassigned node becomes a cluster center, and all its neighbours are assigned to the corresponding cluster. This process can result in overlapping clusters which are resolved by assigning a node to the cluster where it has the highest average similarity to other nodes in the cluster.
The following paper outlines the star clustering algorithm in detail:

Robust graph-based clustering is based on the categorisation of pairwise links according to their strength; strong, normal and weak-high (Saeedi et al. 2018). Initially, connected components are created using a subset of link strengths, which are referred to as base clusters. Subsequently, these base clusters are iteratively merged, where the pairwise cluster similarity needs to be greater than a user defined threshold.
The following paper outlines the robust graph-based clustering algorithm in detail:

We have also implemented a baseline connected component clustering algorithm for comparison purposes.

Connected component clustering considers all the pairwise links in graph G with a similarity greater than a user defined similarity threshold, and then finds the connected components in the resulting graph. A connected component is a set of nodes in G that are directly or indirectly connected via edges.

Our clustering approaches can be run with or without temporal constraints. However, our experimental evaluation has indicated that the linkage results improve when temporal constraints are applied.

The robustness of record linkage evaluation measures is of high importance, since linkage techniques are assessed based on these. Linkage quality is traditionally evaluated based on the classified versus the true matching links using measures such as precision and recall. Both these measures however are based on the evaluation of links between individual records (record pairs) rather than clusters of records.

However, in a group linkage context these traditional evaluation measures are not suitable for evaluating groups of linked records because they evaluate the quality of individually linked record pairs rather than the quality of records grouped into clusters.

Novel evaluation measure for group record linkage
To address the problem of the lack of suitable linkage evaluation measures for group based record linkage, we propose a novel method for evaluating the quality of the clusters generated in a record linkage process, which classifies records (rather than links) according to how correctly they have been generated when compared to the ground truth clusters.

In our evaluation approach, we classify each record in a database into one of seven categories, based on how they have been clustered by an algorithm, with respect to the ground truth. The seven categories are described below.

Our proposed linkage evaluation method provides unambiguous results while providing insight to how the records themselves were classified; not the links between records.

Further, it provides more detailed information regarding which aspects of a clustering algorithm is better or worse (such as whether they are more suited for predicting singletons or groups correctly).

Isle of Skye dataset
We used a Scottish dataset that covers the population of the Isle of Skye over the period from 1861 to 1901 for conducting experimental evaluation. This dataset consists of 17,613 birth certificates, each containing personal details about a baby and its parents such as their names, addresses, occupations, and the birth date of the baby. This dataset has been linked semi-manually by demographers using Microsoft Excel and Access programmes to assist with sorting, searching, and querying records, and therefore ground truth is available for conducting linkage quality evaluation. The ground truth clusters were validated by demographers using census, marriage, and death certificates.

For more information regarding the Isle of Skye dataset, please refer to the following paper:

We have provided the pairwise record similarity for the Isle of Skye dataset used in our experiments. We generated six variations of the similarity graph G by using different attribute combinations for the similarity calculation, with and without attribute weighting.