Αλγόριθμοι κατασκευής Ball trees για προσπέλαση πολυδιάστατων αντικειμένων και ερωτήματα κοντινότερων γειτόνων σε βάσεις δεδομένων

Abstract

Το θέμα της πτυχιακής εργασίας είναι: “ Αλγόριθμοι κατασκευής Ball trees για αποδοτική προσπέλαση πολυδιάστατων αντικειμένων και ερωτήματα κοντινότερων γειτόνων σε βάσεις δεδομένων ” Ένα Ball tree διαχωρίζει το χώρο των πολυδιάστατων δεδομένων των k διαστάσεων οργανώνοντας με αποτελεσματικό τρόπο τα σημεία, ώστε να είναι γρήγορες οι αναζητήσεις που περιλαμβάνουν ένα πολυδιάστατο κλειδί αναζήτησης όπως αναζήτηση περιοχής ή αναζήτηση κοντινότερων γειτόνων. Η αποδοτική προσπέλαση πολυδιάστατων δεδομένων και η αποτελεσματική αναζήτηση κοντινότερων γειτόνων αποτελούν κρίσιμα εργαλεία για εφαρμογές ανάκτησης πληροφοριών, εξόρυξης γνώσης από δεδομένα, αναζήτηση εικόνων, αναγνώρισης προτύπων και πολλά απανταχού παρόντα προβλήματα τύπου N-body όπως Kernel density estimation, Nadaraya-Watson, locally-weighted regression/interpolation, Gaussian prediction. Έτσι πολλές ερευνητικές προσπάθειες επικεντρώθηκαν στη σχεδίαση των αποτελεσματικών δενδροειδών δομών διαμέρισης πολυδιάστατων χώρων όπως τα kD-trees, metric Ball trees, Bregman Ball trees, και vantage point trees που βελτιώνουν την αναζήτηση κοντινότερων γειτόνων μέσω της αξιοποίησης των ιδιοτήτων του χώρου. Σύμφωνα με νεότερες μελέτες οι δομές δεδομένων των Ball trees αποδεικνύονται κατάλληλες για πολλά προβλήματα, καθώς είναι πιο αποτελεσματικές σε χώρους υψηλών διαστάσεων, δουλεύουν με μη ευκλείδειες αποστάσεις (αρκεί να ικανοποιείται η τριγωνική ανισότητα σε μία μετρική), και έχουν επεκτάσεις. Τα Ball trees εκτείνουν την βασική μεθοδολογία των KD-trees σε μετρικούς χώρους χρησιμοποιώντας υποχώρους με μετρικές μπάλες αντί των υπερ-ορθογωνίων. Το πλεονέκτημα είναι ότι αυτές οι κοντινές σφαίρες μπορούν να επικαλύπτονται ενώ τα ορθογώνια μόνο συνορεύουν μεταξύ τους. Η επικάλυψη δεν αποτελεί πρόβλημα στον αλγόριθμο αναζήτησης κοντινών γειτόνων καθώς αυτός δεν βασίζεται σε πλήρως διαχωριζόμενους χώρους. Ο αλγόριθμος αναζήτησης κάνει χρήση της τριγωνικής ανισότητας ως κριτήριο αποκλεισμού υπο-χώρων αναζήτησης στους κόμβους του δένδρου. Τα Ball trees κτίζονται με πολλούς τρόπους, συνήθως διασπώντας αναδρομικά το χώρο (την κάθε μπάλα/σφαίρα) σε δύο μέρη. Στην πτυχιακή εργασία γίνεται μία βιβλιογραφική ανασκόπηση των κυριότερων μεθόδων και υλοποιούνται τα πρόσφατα Bregman Βall trees με μία αποτελεσματική διάσπαση του χώρου μέσω διαμεριστικής ομαδοποίησης 2-means, κρατώντας τα δύο μέσα κέντρα, σύμφωνα με την αντίστοιχη βιβλιογραφία