Back to search

Hellenic Open University

Approximate linkage of duplicate records, data matching and privacy

Abstract

dc:description

In 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 × 10

Rights

dc:rights
Statement dc:rights
  • BY_NC
Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/36507

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Karakasidis, Alexandros; Καρακασίδης, Αλέξανδρος. Approximate linkage of duplicate records, data matching and privacy. Hellenic Open University, 2015. http://hdl.handle.net/10442/hedi/36507