Privacy-preserving record linkage for high linkage quality

Abstract

Organisations such as healthcare and financial service providers collect vast amounts of data with varying levels of data quality. Such data often need to be integrated across databases owned by different organisations to facilitate effective and efficient data analysis. Record linkage is one of the processes in data integration that aims to link records in different databases which refer to the same entities. However, much of the data collected by organisations such as research institutes, healthcare, and financial service providers is about individuals. Therefore, privacy-preserving record linkage (PPRL) is required to link records between these databases, while preserving the sensitive information of the individuals in such databases.

In the last two decades, various PPRL techniques have been developed, where the most widely used techniques are based on Bloom filter encoding. However, the Bloom filter technique is vulnerable to various privacy attacks. Therefore, harden- ing techniques have been proposed to improve the privacy of Bloom filter encoding. Hardening techniques result in lower linkage quality and some have higher compu- tational complexities. Developing effective PPRL techniques, especially in the Big data era, is still an open challenge because (1) the linking of large amounts (volume), diverse data (variety), and data of different qualities (veracity) requires fast linkage processing (velocity), (2) the privacy requirements of sensitive information, and (3) the linkage process should provide high linkage quality to allow data scientists to analyse data accurately.

In this thesis, we develop PPRL techniques to provide high linkage quality where the scalability and privacy of the linking process are also of high importance. We first propose a hardened Bloom filter based PPRL technique to improve the privacy and linkage quality of the original Bloom filter encoding. We then propose a novel PPRL technique to link databases that contain missing values, because missing data can lead to low linkage quality and it has seen limited attention in the record linkage and PPRL contexts. Next, we propose two PPRL techniques that consider positional information of sub-strings to provide efficient and accurate string matching results. Finally, we propose two PPRL techniques to improve the time complexity of the linkage process while providing high linkage quality of string matching results.

We comparatively evaluated our proposed PPRL techniques with various baseline techniques on both real-world and synthetic databases. We assessed our techniques in terms of linkage quality, scalability, and privacy. The experimental results obtained illustrate that all of our proposed PPRL techniques provide higher linkage quality and privacy compared to the baselines. Our string matching techniques provide accurate linkage results and outperform some baselines with regard to scalability for linking larger databases.