Hellenic Open University
Approximate linkage of duplicate records, data matching and privacy
Abstract
dc:descriptionIn many aspects of everyday life, from education to health care and from economics to homeland security, information exchange involving companies or government agencies has become a common practice. Linking data stored in these databases, belonging to the same person, is one of the problems that may arise in such transactions. This, however, is not a trivial task. The records held in databases of distinct organizations do not share common unique identifiers. As such, record fields usually holding data of low quality, such as misspellings, should be used. This situation becomes even more complicated when privacy restrictions apply, since privacy cannot be assured by simply transferring data between organizations. We have just described the parameters of the privacy preserving record linkage problem, an emerging field of research, the results of which are applicable for both academic and business purposes. In this thesis we present our contributions for solving the privacy preserving record linkage problem. Privacy preserving record linkage mainly consists of two subproblems. Privacy preserving matching and privacy preserving blocking. In privacy preserving matching, which is the main phase of the linkage process, elaborate and accurate matching between records takes place. However, this procedure is time consuming and resource demanding. Privacy preserving blocking, which precedes privacy preserving matching, aims at speeding up the more elaborate and computationally expensive matching process, by organizing similar records into block. Then, only records within the same block are matched. In this dissertation we present methods we have developed for privacy preserving matching and privacy preserving blocking. We also introduce privacy preserving meta-blocking, which is applied after privacy preserving blocking and aims at reducing matching costs even further. We conclude this thesis with PRIVATEER, a toolkit for evaluating different combinations of privacy preserving record linkage algorithms. For privacy preserving matching, we propose the use of phonetic codes, which are summaries of words based on their pronunciation. Phonetic codes have an interesting feature which can be exploited for providing privacy. They have inherent information suppression properties, thus the mappings produced during the production of a phonetic code do not exhibit the one-to-one property. We propose a protocol for using phonetic codes for matching using a third party to facilitate operations and enhance its privacy. Privacy is further enhanced by noise generation through fake codes injection. We also address privacy preserving matching from a different point of view. We propose a secure method for calculating edit distances between strings which exploits positional information of characters within strings and provides string mappings to bit vectors using secure hash functions. One of the main characteristics of this method is that it does not require the use of a third party to assure privacy. In order to reduce the complexity associated with privacy preserving matching algorithms, we propose a series of blocking algorithms. These techniques aim at pruning out unlikely to match candidate pairs by organizing similar records into blocks. Then, matching occurs only within each of these blocks. In this context, we propose a secure blocking method based on phonetic algorithms statistically enhanced to improve security. We combine this approach with the secure edit distance algorithm we have developed. Next, we propose a framework we have developed, in order to explore the use of reference tables for privacy preserving blocking. Reference tables are publicly available databases which may be used as an intermediate point of reference to avoid directly comparing data. Using this framework, we have developed and experimented with a range of alternatives aiming at the development of privacy preserving blocking methods which would be secure, time efficient and would yield high recall in terms of matching performance. To fulfill these goals, we have developed a meta-blocking algorithm which speeds up matching even further by altering the way records are matched within blocks. This step led us to our major achievement of shifting the time complexity of the privacy preserving record linkage problem from quadratic to linear, as of the dataset size used, maintaining, at the same time, high recall. To be able to compare the methods we have developed with other state-of-the-art approaches appearing in the literature, we introduce PRIVATEER, a toolkit which aims at enabling practitioners to compare and evaluate various privacy preserving record linkage techniques and determine the best for each application. This toolkit is based on a simulator, designed to be highly configurable, modular and extensible, allowing the user to test different configurations by combining privacy preserving blocking and matching methods with corresponding distance and similarity measures using various data sources.
Degree
thesis:*- Grantor dc:publisher
- Hellenic Open University
- Year dc:date
- 2015
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Karakasidis, Alexandros
- Καρακασίδης, Αλέξανδρος
Subjects
dc:subject × 10Rights
dc:rights- Statement dc:rights
-
- BY_NC
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/36507