Privacy preserving record linkage (PPRL) is the process of integrating data across multiple heterogeneous data sources without compromising their privacy. While many techniques have been developed for PPRL, there has not been, up to now, a universally accepted method providing both performance and quality of results in all cases. To this end, we present PRIVATEER, a toolkit which aims at enabling practitioners to compare various techniques involved in the PPRL process and determine the best for their needs. The toolkit is based on a simulator, designed to be highly configurable, modular and extensible, allowing the user to test different configurations by combining a number of privacy preserving blocking and matching methods with corresponding distance and similarity measures on her own or sample data. We showcase the usability of our toolkit by presenting experimental results measuring both quality and performance of state-of-the-art PPRL methods.
Large volumes of data, describing individuals, are collected by public or private organizations. Being able to interconnect and analyze these independently stored data is beneficial for businesses, governments and research. For instance, being able to interconnect data of distinct health organizations, hospitals and physicians could prevent epidemic outbreaks or help us better understand the mechanisms behind certain diseases.
The task of linking such heterogeneous data, known as the record linkage
problem, is not trivial [
To privately link data with accuracy, Privacy Preserving Matching (PPM ) methods focus on elaborately matching data, while maintaining privacy. Though accurate, matching methods often incur high computational costs. To increase their scalability, PPM methods are combined with Privacy Preserving Blocking (PPB ) methods. PPB methods prune out unlikely to match candidate pairs of records, while also maintaining privacy. Even though they improve efficiency, PPB methods often compromise matching quality.
To the best of our knowledge, there is no single solution that successfully
addresses the privacy preserving record linkage problem to its full extent. In
particular, state-of-the-art PPB and PPM methods usually focus on a specific
type of data. For instance, there are PPM approaches appropriate for string
data [
To this end, we introduce PRIVATEER, a PRIVATE REcord linkage toolkit designed to assist practitioners in this selection process, and also serve as a comparison tool for different methods. PRIVATEER is a modular simulator, constantly under development, implementing a set of state-of-the-art PPRL methods. Considering the various tasks involved in PPRL, the aim of PRIVATEER is to accommodate all this functionality into a single toolkit. It consists of clearly separate modules, each of them performing a separate task, and uses different components implementing various privacy preserving matching and blocking methods, and auxiliary components that are deployed by matching and blocking methods, such as different distance measures used in approximate matching and reference set generators, where a reference set is used as an intermediate point of comparison. Highly composable, PRIVATEER allows all compatible PPB methods to be combined with compatible PPM ones, and with corresponding auxiliary methods, so as to form a complete PPRL solution.
PRIVATEER is also configurable enabling the user to fine tune each of the deployed methods and provides a variety of performance measures. While the toolkit is equipped with sample data, it also enables the use of a user’s own data. Towards extensibility, PRIVATEER’s clear and comprehensive design provides an API for extending its functionality. Through the Java paradigm the user is able to add its own modules and algorithms.
Similar toolkits, such as TAILOR [
The rest of this paper is organized as follows. In Section 2, we present the architectural design of PRIVATEER and briefly describe the PPM and PPB algorithms, distance measures, and reference set generation methods currently implemented in the toolkit. Section 3 provides experimental results derived from PRIVATEER and we conclude in Section 4. The primary goals of PRIVATEER’s design is composability and extensibility. We wanted PRIVATEER to easily enable the combination of different methods to compose a complete PPRL solution, and the incorporation of new ones as state-of-the-art PPM and PPB methods are constantly developed. To this end, an object-oriented design is appropriate, thus, we used Java to build the simulator comprising PRIVATEER. Also, Java has the property of Write Once Run Anywhere, providing machine independence, and there are many out-of-the-box libraries and data structures one can exploit.
We have made a particular effort to limit the assumptions when designing the architectural components of the simulator. In particular, we assume that all operations are executed sequentially. In many PPB and PPM algorithms, there are functions that require the parallel operation of the matching parties. PRIVATEER simulates this functionality by sequentially executing separate objects. Also, we only focus on the processing cost and do not examine communication costs and data propagation delays. We followed a modular design, separating data, execution functionality and implemented methods. This approach improves PRIVATEER’s extensibility, as it is very easy through its API to add new features and modules. Moreover, since data is retrieved in a transparent way, new data sources may be added as well.
Next, we present the architectural elements that comprise PRIVATEER. The Base Module. The base module holds PRIVATEER’s main functionality organizing the execution of each evaluation experiment. It coordinates the different modules and enables us to execute each experiment multiple times. As illustrated in Fig. 1(1), it hosts the configuration module, a PPB and a PPM module, the results processing and the visualization module.
The Configuration Module. The configuration module is invoked by the base module and is responsible for setting an experiment’s execution parameters. It consists of a GUI implemented in JavaFX which receives input from the user and a mechanism that maps user input to specific parameters. This mapping mechanism is important, since each of PRIVATEER’s modules has to be separately configured using separate parameters provided by the same user interface. The Nodes. The nodes implement the functionality of the data sources and a third party, when one is needed. While a data source node has direct access to its data, the third party neither holds nor has direct access to any data. Instead, it is fed with data by the source nodes. Nodes are deployed by the PPB or PPM module and implement their part of the respective algorithm (Fig. 1(2)). The Data Module. The data module is used to provide direct access to external data. It is invoked by each data source node. The used data may be stored in different databases and the configuration module enables the user to select her own input database, thanks to a transparent connectivity mechanism. Currently, MySQL and SQLite databases are supported.
The Measure Module. This module implements the distance or similarity measure to be used by the PPB and later PPM algorithm, in a transparent way. Thus, it allows us to deploy any compatible measure with any PPB and PPM method using the GUI. This way, the user has the ability to test the available algorithms and assess their behavior with different configurations. The Reference Set Generator Module. Similarly to the measure module, the reference set generator provides different methods that can be used interchangeably with our PPB and PPM methods.
The PPB and PPM Modules. The privacy preserving blocking (PPB) and the privacy preserving matching (PPM) modules implement the corresponding type of protocols. Depending on the type of the protocol, as shown in Fig. 1(1), each module initiates two nodes and, when necessary, a third party node. All these nodes implement the same algorithm, which is chosen through the GUI and provided to the corresponding module by the base module. For a PPB or PPM algorithm to operate, the PPB or PPM module load a measure module, which implements the measure used by the corresponding algorithm. If it is required by the implemented algorithm, a reference set generator module is also loaded.
PPRL protocols may vary regarding their implementation and the number of participating nodes. Generally, however, they are either based on some type of data transformation or they may exhibit a multiparty computational behavior. In both cases, a third party may be required and all options may be implemented in PRIVATEER. Moreover, to offer the ability of experimenting with a no blocking setup, a mockup No Blocking method has also been implemented.
Regarding its operation, the PPB passes on the parameters received from the configuration module to the respective modules it hosts and executes the selected PPB algorithm. When the execution concludes, it produces lists of blocks of record ids which are then used by the PPM module. The PPM module receives the blocks of record ids from the PPB module and applies the selected PPM algorithm on each of them. Upon the conclusion of the execution of the PPM module, a list with matching record ids is produced which is then passed to the results processing module for processing.
The Results Processing Module. The results processing module processes the matches list received from the PPM module and calculates the number of total matches, the number of true and false matches, precision, recall and the execution times of the PPM and PPB modules. If the input data have the same unique identifiers (i.e., corrupted versions of the same dataset), the module automatically calculates the measurements based on the common primary key. Otherwise, a matching csv file with the matches between different primary keys is used.
The Visualization Module. The role of the visualization module is to visualize the results of each experiment by collecting the statistics produced by the results processing module and produce plots and tables of these statistics. 2.2
Implemented Algorithms and Measures The modules of the architecture enable the selection of a method for each of the different tasks in the PPRL process. Thus, the PRIVATEER is equipped with a pool of implemented state-of-the-art approaches for each such task, i.e., PPB and PPM algorithms, distance and similarity measures and reference set generators (Tables 1-3).
The PPB algorithms currently implemented in PRIVATEER are illustrated in the upper part of Table 1. The first column holds the name of the algorithm, the second a short description, the third shows the type of data each algorithm is designed for and the forth indicates whether a third party node is required. Similarly, PPM algorithms are included in the lower part of Table 1.
Many of the PPRL algorithms that have been suggested, use a distance or
similarity measure [
Reference sets (RS) are used in PPRL as an intermediate point of
comparison to provide privacy. A reference set may be derived from a publicly available
database or be arbitrarily generated. Table 3 summarizes PRIVATEER’s
currently available methods for RS generation. All methods apart from Arbitrary
String Generation [
To illustrate PRIVATEER’s usability, we present sample experiments exploring alternative combinations of PPB and PPM methods, beyond their default setup, so as to assess their behavior and performance in different configurations.
All experiments are conducted using an Intel i3 PC with 8GB of RAM. We use a sample dataset, which originates from the North Carolina voters database3. We assume that the attributes: last name, first name, middle name, city of residence and precinct description comprise a candidate key, and use them for both matching and blocking. After deduplicating the dataset based on the selected candidate key, we generate two databases of 50 000 records each, so that the 25% of their records is common. Finally, we use the “master” table of Lahman’s baseball database4, as a source for reference set creation. Since we are interested 3 Available at ftp://alt.ncsbe.gov/data/ 4 Available at http://www.seanlahman.com
Name Description Datatype 3P
PPB Algorithms
Option when the use of blocking is not desired. Records to be B1 No Blocking linked are organized in a single block for each of the two data N/A sources.
SNEF is a meta-blocking algorithm specifically designed to B2 S[N1E3]F sphairfatditghme . STohrtisedalgNoeriigthhmbourhseosodrefaeprepnrcoeacshet [c8l]usttoeritnhge foPrPcRreL- NSutrminbgesr,s ✔ ating blocks.
A single attribute is utilized for blocking. Each data source creB3 T[P19P]B aTtheesna, sitepmaerragteesrietfserdeantcaewseitthfrtohme raefpeurebnliccelyseatvaainladblleexdicaotgarbaapshe-. Strings ically sorts the result.
Introduces hash signature transformations to securely repre
Simple sent TF/IDF weight vectors. Blocks consist of records which
B4 Blocking share common strings called tokens, with a token being an Strings ✔
[
signatures.
Phonetic Uses Soundex’s inherent privacy characteristics, which are
B5 Blocking pbahsoendetoicn etnhceocdoinmgmaolgnoirnitfhomrmsa.tRioencosrudpsparreessoirognanpirzoepderintybolofcaklsl Strings ✔
[
PPM Algorithms
Bloom Bigrams of strings are inserted into a Bloom Filter. Then, a
M1 Bigrams bitwise comparison is performed on Bloom Filters using the Strings ✔
[
Embedding Based on the edit distances between actual and reference set
M2 Spaces data, a transformation of the data, called embedding, is derived Strings ✔
[
Secure Edit Secures the use of edit distance through the use of Bloom filM3 Dis[1ta2n]ce taeprps.enEdaicnhg cihtsarpaocstietrioonf ianmthaetcshtirninggfi, eiltdisisinexsetrratecdteidnaandBlaofotemr Strings filter which is encrypted using a secure hash function.
Homomorphic Homomorphic encryption manages to calculate differences
seM4 Encryption curely based on the properties of specific cryptographic algo- Numbers
[
Soundex
M5 Matching hTerraennstfoirnmfosrmatattriiobnutseusppinrteossSioonunpdroexpecrotideesstoanpdroevxipdleoiptriivtasciyn.- Strings ✔
[
Calculates the TF/IDF weights of all words, called tokens,
Hash within all fields. Then, a hash function is used to create arrays
Signatures of these weights, one for each record. This method is not suit- Strings
[
Table 1. Supported PPB and PPM algorithms.
✔
in linking low quality data, we corrupt one of the two databases using the
corrupter described in [
In the second experiment, we combine a matching method with different
blocking methods. In particular, Bloom Bigrams is combined with Simple
Blocking [
Next, we evaluate three reference set generation methods with SNEF[
We have presented PRIVATEER, a modular, highly configurable privacy preserving record linkage toolkit that enables combining and comparing different PPRL solutions. We showed the usability of our toolkit by including evaluation results derived from experiments run by the PRIVATEER on sample data. Acknowledgment. Attendance to this conference was partially supported by the Hellenic Artificial Intelligence Society (EETN).