German English

Privacy Preserving Record Linkage (PPRL)

Overview

Record linkage aims at linking records that refer to the same real-world entity, such as persons. Typically there is a lack of global identifiers, therefore the linkage can only be achieved by comparing available quasi-identifiers, such as name, address or date of birth. However, in many cases, data owners are only willing or allowed to provide their data for such data integration if there is sufficient protection of sensitive information to ensure the privacy of persons, such as patients or customers. For example, in medical research data of several sources (e. g., hospitals) has to be matched to investigate possible correlations between some diseases of the same patients without revealing the identity of patients.

Privacy Preserving Record Linkage (PPRL) addresses this problem by providing techniques to match records while preserving their privacy allowing the combination of data from different sources for improved data analysis and research. For this purpose, the linkage of person-related records is based on encoded values of the quasi-identifiers and the data needed for analysis (e. g., health data) is separated from these quasi-identifiers. The relevant data can be provided to a researcher without the identifying data. Those PPRL approaches can be applied in many areas, such as public health surveillance, demographical studies and marketing analysis. PPRL is confronted with several challenges needing to be solved to ensure its practical applicability. In particular, a high degree of privacy has to be ensured by suitable encoding of sensitive data and organizational structures, such as the use of a trusted linkage unit. PPRL must achieve a high linkage quality by avoiding false or missing matches. Furthermore, a high efficiency with fast linkage time and scalability to large data volumes are needed. A main problem for performance is the inherent quadratic complexity of the linkage problem when every record of the first source is compared with every record of the second source. For better efficiency, the number of comparisons can be reduced by adopting blocking or filtering approaches. Furthermore, the matching can be performed in parallel on multiple processing nodes.

Research Results

In the last few years, we concentrated on improving the performance and scalability of our PPRL methods. As the records are represented as bit vectors (using Bloom filter for encoding), we used metric space similarity measures for filtering. In particular, the pivot-based approach for metric spaces utilizing the triangle inequality to reduce the search space showed significant improvement of performance compared to previous filter techniques. One data source is indexed by determining some records as pivots and assigning the leftover records to them. We can save many similarity computations by comparing the records of the second source with only the pivots first and exclude most records as possible matches.

Recently, we parallelized this approach utilizing the modern framework Apache Flink, which supports efficient distributed in- memory processing. We developed parallel algorithms for both determining the pivots and the pivot-based matching process for different strategies to select the pivots. The distributed implementation outperforms the centralized version for large dataset and improves the scalability of this approach.

Additionally, we investigated locality sensitive hashing (LSH) as blocking method and also developed a distributed algorithm using Apache Flink. LSH enables probabilistic blocking by applying hash functions on bit vectors (Bloom filters). LSH-based blocking supports a flexible configuration and can be applied on encoded data. An extensive evaluation has shown that LSH-based blocking can achieve high quality and high scalability up to millions of records. In contrast, phonetic blocking approaches based on Soundex are susceptible to cryptanalysis and more sensitive with respect to data quality problems. Moreover, phonetic blocking based on a single attribute is not feasible for large datasets due to the low number of blocks and data skew effect introduced by frequent names.

Furthermore, we analyzed methods for multiparty PPRL considering applications, where more than two data holder are involved in the process of privacy preserving record linkage. The most challenging case of multiparty PPRL is to find subset matches, i. e. sets of matching records that are not in all sources, but in subsets of them. The intuitive way is to link the sources sequentially using for example the metric space as a growing index structure. In each iteration a new source is linked with the other already matched sources, then indexed. At the end of this process resulting clusters need to be cleaned if we consider that the sources are deduplicated (only one records from each source). Solutions to this problem are still a research topic.

Research Goals

For future work we plan to bring those PPRL approaches in practical applications. Therefore the used protocols might be rethought and further aspects like postprocessing have to be considered. We are currently developing a toolbox to bring together our developed methods. This involves in particular the encoding of records on the client side and the matching of the encoded records (using LSH or metric space in a central or distributed version). As part of the Medical Informatics Initiative within the SMITH consortium we need to develop applications for this concrete practical scenario.

Project Members

Related Publications

PDF

Google Scholar
Gladbach, Marcel; Sehili, Ziad; Kudraß, Thomas; Christen, Peter; Rahm, Erhard
Distributed Privacy-Preserving Record Linkage using Pivot-based Filter Techniques
Proceedings of the 2018 IEEE 34th International Conference on Data Engineering Workshops (ICDEW), pp. 33-38, 2018
2018-04
PDF

Google Scholar
Franke, Martin; Sehili, Ziad; Rahm, Erhard
Parallel Privacy-Preserving Record Linkage using LSH-based blocking
Proceedings of the 3rd International Conference on Internet of Things, Big Data and Security (IoTBDS), pp. 195-203, 2018
2018-03
PDF

Google Scholar
Vatsalan, Dinusha; Sehili, Ziad; Peter Christen, Peter; Rahm, Erhard
Privacy-Preserving Record Linkage for Big Data: Current Approaches and Research Challenges
In: Handbook of Big Data Technologies (eds.: A. Zomaya, S. Sakr) , Springer 2017, to appear
2017-02
PDF

Google Scholar
Vatsalan, D.; Christen, P.; Rahm, E.
Scalable privacy-preserving linking of multiple databases using Counting Bloom filters
Proc ICDM workshop on Privacy and Discrimination in Data Mining (PDDM)
2016-12
PDF
further information
Google Scholar
Sehili, Ziad; Rahm, Erhard
Speeding up Privacy Preserving Record Linkage for Metric Space Similarity Measures
Datenbankspektrum 16, pp. 227-236
2016-11
PDF

Google Scholar
Sehili, Z.; Kolb, L.; Borgs, C.; Schnell, R.; Rahm, E.
Privacy Preserving Record Linkage with PPJoin
Proc. of 16. GI-Fachtagung für Datenbanksysteme in Business, Technologie und Web (BTW), 2015
2015-03