Approximate linkage of duplicate records, data matching and privacy
Authors: Καρακασίδης Αλέξανδρος 
Published: August 2021

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