Συγκριτική μελέτη αλγόριθμων ανίχνευσης διπλότυπων εγγραφών

Abstract

Δεδομένου ότι ο κόσμος γίνεται όλο και περισσότερο αυτοματοποιημένος, οι βάσεις δεδομένων που αποθηκεύουν πληροφορίες έχουν γίνει πολύ σημαντικές. Πολλές κυβερνήσεις καθώς επίσης και πολλές εταιρίες μεμονωμένα κάνουν εκτενή χρήση της τεχνολογίας των βάσεων δεδομένων. Παραδείγματος χάριν, οι βάσεις δεδομένων χρησιμοποιούνται για να αποθηκεύουν ιατρικά δεδομένα, οικονομικές και τραπεζικές πληροφορίες, αριθμούς τηλεφώνου και διευθύνσεις, και πολλές άλλες πληροφορίες. Μερικές βάσεις δεδομένων είναι τεράστιες. Η διατήρηση των μεγάλων βάσεων δεδομένων μπορεί να είναι δύσκολη, χρονοβόρα και ακριβή. Ένα σημαντικό πρόβλημα που παρατηρείται συχνά σε μεγάλου μεγέθους βάσεις δεδομένων είναι η ύπαρξη των διπλότυπων (duplicates) εγγραφών. Αν υποθέσουμε ότι όταν ένας πελάτης που ονομάζεται «Joseph Smith» ξεκινά να συνεργάζεται με μια επιχείρηση, το όνομά του εισάγεται αρχικά στη βάση δεδομένων ως «Joe Smith». Την επόμενη φορά που γίνεται μια παραγγελία από το ίδιο πρόσωπο, ο υπάλληλος πωλήσεων αποτυγχάνει να παρατηρήσει ή να αναγνωρίσει ότι είναι ο ίδιος «Joe Smith» που είναι ήδη στη βάση δεδομένων, και δημιουργεί μια νέα εγγραφή με το όνομα «Joseph Smith». Μια επιπλέον συναλλαγή μπορεί να δημιουργήσει μια νέα εγγραφή «J. Smith». Όταν η επιχείρηση στείλει ένα μήνυμα αλληλογραφίας σε όλους τους πελάτες της, ο κος Smith θα λάβει τρία αντίγραφα ένα προς τον «Joe Smith», άλλο που απευθύνεται στον «Joseph Smith», και ένα τρίτο στον «J. Smith». Είναι δυνατό να προγραμματιστεί ένας υπολογιστής ώστε να αναγνωρίζει τις εγγραφές που είναι ακριβή αντίγραφα και να τις απορρίπτει. Εντούτοις, στο παραπάνω παράδειγμα, οι εγγραφές δεν είναι ακριβή αντίγραφα, αλλά άντ αυτού διαφέρουν σε κάποια σημεία. Είναι δύσκολο για τον υπολογιστή αυτόματα να καθορίσει εάν οι εγγραφές είναι πράγματι διπλότυπες. Παραδείγματος χάριν, η εγγραφή «J Smith» μπορεί να αντιστοιχεί σε Joe Smith, ή να αντιστοιχεί στην έφηβη κόρη του, Jane Smith Joe, που ζει στην ίδια διεύθυνση. Η Jane Smith δεν θα πάρει ποτέ το αντίγραφο του μηνύματος εάν ο υπολογιστής είναι προγραμματισμένος να διαγράψει όλα τα αντίγραφα εκτός από ένα «J_Smith». Τα λάθη εισαγωγής δεδομένων, όπως για παράδειγμα τα ορθογραφικά, μπορούν να προκαλέσουν ακόμα χειρότερα προβλήματα ανίχνευσης διπλοτύπων. Υπάρχουν καταστάσεις στις οποίες διαφορετικές εγγραφές πρέπει να συνδεθούν ή να ταιριάζουν. Παραδείγματος χάριν, υποθέστε ότι ο κος Smith έχει ένα αυτοκινητιστικό ατύχημα και αποθηκεύεται στη βάση δεδομένων μια ασφαλιστική διεκδίκηση με το πλήρες όνομά του «Joseph Smith». Ας υποθέσουμε ότι αρχειοθετείται αργότερα μια δεύτερη διεκδίκηση για ένα άλλο ατύχημα με το όνομα «J. Ρ. Smith». Θα ήταν χρήσιμο ένας υπολογιστής να μπορούσε αυτόματα να ταιριάζει τις δύο διαφορετικές εγγραφές διεκδίκησης εξασφαλίζοντας ότι ο κος Smith δεν προσπαθεί ψευδώς να πάρει διπλή αποζημίωση για το ίδιο ατύχημα. Η διαδικασία της διασύνδεσης εγγραφών (record linkage) είναι μια επίπονη διαδικασία για μεγάλες βάσεις δεδομένων. Ένας τρόπος να βελτιωθεί αυτή η διαδικασία όσον αφορά το ταίριασμα (matching) των εγγραφών είναι το αποκαλούμενο «blocking» βήμα. To blocking βήμα αναφέρεται γενικά σε έναν γρήγορο αλγόριθμο ταιριάσματος εγγραφών που χρησιμοποιείται ως ένα βήμα προ-επεξεργασίας της διασύνδεσης εγγραφών. Ο στόχος του blocking βήματος είναι να βρεθούν όλες οι πιθανές αντιστοιχίες μιας εγγραφής χωρίς να δίνεται μεγάλη σημασία στον καθορισμό της σωστής αντιστοιχίας. Αυτές οι εγγραφές μπορούν έπειτα να εξεταστούν από τον άνθρωπο για την εύρεση της σωστής αντιστοιχίας, ή μπορούν να δηλωθούν αυτόματα ως διπλότυπες, εάν ο χρήστης δεν απαιτεί μεγάλη ακρίβεια.