Approximate linkage of duplicate records, data matching and privacy

Abstract

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.

Σε πολλούς τομείς της σύγχρονης ζωής, από την εκπαίδευση και την υγεία έως την οικονομία και την εθνική ασφάλεια, η ανταλλαγή πληροφοριών μεταξύ εταιριών και κυβερνητικών οργανισμών αποτελεί συνήθη πρακτική. Πολλές φορές απαιτείται, μεταξύ άλλων, η αντιστοίχιση δεδομένων αποθηκευμένων σε βάσεις δεδομένων, τα οποία περιγράφουν το ίδιο άτομο. Η αντιστοίχιση αυτή, όμως, δεν αποτελεί απλή διαδικασία. Οι εγγραφές στις βάσεις δεδομένων των οργανισμών που εμπλέκονται σε τέτοιου είδους ανταλλαγές δεδομένων δεν διαθέτουν κοινά μοναδικά αναγνωριστικά, γεγονός που καθιστά επιβεβλημένη τη χρήση πεδίων από τις εγγραφές αυτές, όπως ονόματα, διευθύνσεις κ.ο.κ., τα οποία όμως συνήθως εμφανίζουν χαμηλή ποιότητα, λόγω της ύπαρξης ορθογραφικών λαθών και ελλείψεων. Το πρόβλημα περιπλέκεται ακόμη περισσότερο, όταν πρέπει να συνυπολογιστεί και η διασφάλιση της ιδιωτικότητας, κάτι που δεν είναι δυνατόν να επιτευχθεί μέσω μίας απλής ανταλλαγής δεδομένων μεταξύ των εμπλεκομένων οργανισμών. Αυτό που μόλις περιγράψαμε αποτελεί το πρόβλημα της προσεγγιστικής διασύνδεσης εγγραφών με διατήρηση της ιδιωτικότητας. Πρόκειται για ένα νέο και ανοιχτό πεδίο έρευνας, τα αποτελέσματά του οποίου μπορούν να είναι χρήσιμα τόσο σε ερευνητικές, όσο και σε εμπορικές εφαρμογές. Σε αυτή τη διατριβή παρουσιάζουμε τη συνεισφορά μας στην επίλυση του συγκεκριμένου προβλήματος. Γενικότερα, μπορούμε να πούμε ότι το πρόβλημα της προσεγγιστικής διασύνδεσης εγγραφών με διατήρηση της ιδιωτικότητας αποτελείται από δύο επιμέρους υποπροβλήματα, το ταίριασμα των εγγραφών και την ομαδοποίηση των εγγραφών. Συγκεκριμένα, κατά το ταίριασμα, που είναι η κύρια φάση της διαδικασίας, πραγματοποιείται λεπτομερής και ακριβής αντιστοίχιση μεταξύ των εγγραφών. Καθώς το ταίριασμα είναι ιδιαίτερα χρονοβόρο, αναπτύχθηκαν μέθοδοι ομαδοποίησης των εγγραφών πριν από το ταίριασμα, ώστε να επιταχυνθεί η όλη διαδικασία. Οι μέθοδοι αυτές οργανώνουν τις εγγραφές σε ομάδες με βάση την ομοιότητά τους. Παράλληλα, είναι απαραίτητη η διατήρηση της ιδιωτικότητας τόσο κατά το ταίριασμα όσο και κατά την ομαδοποίηση. Σε αυτή τη διατριβή, παρουσιάζουμε τις μεθόδους που αναπτύξαμε τόσο για το ταίριασμα με διατήρηση της ιδιωτικότητας, όσο και για την ομαδοποίηση με διατήρηση της ιδιωτικότητας. Επίσης, παρουσιάζουμε τη μετα-ομαδοποίηση με διατήρηση της ιδιωτικότητας, η οποία παρεμβάλλεται μεταξύ της ομαδοποίησης και του ταιριάσματος και αποσκοπεί στην περαιτέρω μείωση των υπολογιστικών πόρων που απαιτούνται για την πραγματοποίηση της προσεγγιστικής διασύνδεσης εγγραφών με διατήρηση της ιδιωτικότητας. Ολοκληρώνουμε αυτή τη διατριβή παρουσιάζοντας το PRIVATEER, ένα εργαλείο αξιολόγησης αλγορίθμων προσεγγιστικής διασύνδεσης εγγραφών με διατήρηση της ιδιωτικότητας. Για την επίλυση του υποπροβλήματος του προσεγγιστικού ταιριάσματος εγγραφών με διατήρηση της ιδιωτικότητας, προτείνουμε δύο προσεγγίσεις. Αρχικά, επιλύουμε το πρόβλημα με τη χρήση φωνητικών αλγορίθμων, οι οποίοι παράγουν κώδικες βάσει της προφοράς των λέξεων που λαμβάνουν ως είσοδο. Καθώς οι φωνητικοί αλγόριθμοι έχουν εγγενείς ιδιότητες απώλειας πληροφορίας, οι κώδικες που δημιουργούν δεν αποτελούν ένα προς ένα απεικονίσεις του αρχικού κειμένου στο οποίο εφαρμόζονται. Προτείνουμε ένα πρωτόκολλο βασισμένο σε φωνητικούς κώδικες, όπου, εκτός από τους συμμετέχοντες που επιθυμούν να διασυνδέσουν τις βάσεις δεδομένων τους, χρησιμοποιείται και ένας τρίτος στη διαδικασία, με σκοπό να αυξήσει την παρεχόμενη από τους φωνητικούς κώδικες ιδιωτικότητα. Τα χαρακτηριστικά ιδιωτικότητας βελτιώνονται περαιτέρω μέσω της εισαγωγής θορύβου στα δεδομένα με την παραγωγή ψευδών απεικονίσεων. Αντιμετωπίζουμε επίσης το ίδιο πρόβλημα και από μία άλλη οπτική γωνία. Προτείνουμε μία ασφαλή μέθοδο για τον υπολογισμό της απόστασης επεξεργασίας μεταξύ συμβολοσειρών. Η συγκεκριμένη μέθοδος εκμεταλλεύεται τη θέση των χαρακτήρων εντός των συμβολοσειρών και δημιουργεί απεικονίσεις σε δυαδικά διανύσματα χρησιμοποιώντας ασφαλείς συναρτήσεις κατακερματισμού. Ένα από τα κύρια χαρακτηριστικά αυτής της μεθόδου είναι ότι δεν απαιτεί τη χρήση τρίτου συμμετέχοντα για τη διασφάλιση της ιδιωτικότητας. Με στόχο τη μείωση της πολυπλοκότητας της διαδικασίας προσεγγιστικής διασύνδεσης εγγραφών με διατήρηση της ιδιωτικότητας, προτείνουμε μία σειρά αλγορίθμων ομαδοποίησης. Αυτές οι μέθοδοι στοχεύουν στην απαλοιφή υποψηφίων ζευγών εγγραφών με μικρές πιθανότητες ταιριάσματος, δημιουργώντας ομάδες αποτελούμενες από εγγραφές με ομοιότητες. Στη συνέχεια, το ταίριασμα πραγματοποιείται μεταξύ των εγγραφών της καθεμίας ομάδας. Βάσει αυτών προτείνουμε μία μέθοδο ομαδοποίησης με διατήρηση της ιδιωτικότητας, που στηρίζεται σε φωνητικούς κώδικες, και τη συνδυάζουμε με τον αλγόριθμο ασφαλούς υπολογισμού αποστάσεων επεξεργασίας που αναπτύξαμε. Επιπροσθέτως, προτείνουμε μία διάταξη που αναπτύξαμε για να διερευνήσουμε τη χρήση των πινάκων αναφοράς στην ομαδοποίηση με διατήρηση της ιδιωτικότητας. Οι πίνακες αναφοράς είναι δημοσίως διαθέσιμες βάσεις δεδομένων που μπορούν να χρησιμοποιηθούν ως ενδιάμεσα σημεία αναφοράς προς αποφυγή της απευθείας σύγκρισης των δεδομένων. Χρησιμοποιώντας την εν λόγω διάταξη, πειραματιστήκαμε με μία σειρά μεθόδων ομαδοποίησης με διατήρηση της ιδιωτικότητας, οι οποίες είναι ασφαλείς, αποτελεσματικές από άποψης χρόνου και με υψηλές επιδόσεις ως προς το ταίριασμα των εγγραφών. Επιπλέον, υλοποιήθηκε ένας αλγόριθμος μετά-ομαδοποίησης με διατήρηση της ιδιωτικότητας, ο οποίος επιταχύνει ακόμη περισσότερο τη διαδικασία ταιριάσματος. Αυτή η εξέλιξη μας οδήγησε στο πιο σημαντικό μας επίτευγμα, αυτό της μείωσης της πολυπλοκότητας του προβλήματος της διασύνδεσης εγγραφών με διατήρηση της ιδιωτικότητας από τετραγωνική σε γραμμική ως προς το μέγεθος των δεδομένων, διατηρώντας παράλληλα υψηλά επίπεδα ποιότητας ταιριάσματος των εγγραφών. Για να συγκρίνουμε τις μεθόδους που αναπτύξαμε με άλλες αντίστοιχες που εμφανίζονται στη βιβλιογραφία, δημιουργήσαμε το PRIVATEER. Το PRIVATEER έχει ως στόχο να βοηθήσει ερευνητές και άλλους εμπλεκόμενους στο πρόβλημα που εξετάζουμε, στη σύγκριση και στην αξιολόγηση διαφόρων αλγορίθμων, ώστε να μπορούν να επιλέξουν τον πλέον κατάλληλο για την εκάστοτε εφαρμογή. Το εργαλείο αυτό, που βασίζεται σε έναν προσομοιωτή, σχεδιάστηκε ώστε να είναι προσαρμόσιμο και επεκτάσιμο, επιτρέποντας στο χρήστη να συνδυάσει αλγορίθμους ομαδοποίησης και ταιριάσματος με διάφορα μέτρα διαφοράς και ομοιότητας χρησιμοποιώντας ετερογενείς πηγές δεδομένων.