Αποδοτικά Ευρετήρια Για Ερωτήματα Ομοιότητας Σε Υποχώρους Πολυδιάστατων Δεδομένων

Abstract

Ο σκοπός της διπλωματικής είναι η ανάπτυξη μίας δομής ευρετηρίων, που θα αναφέρεται σε πολυδιάστατα δεδομένα, και θα επιτρέπει την κατά το δυνατόν πιο γρήγορη απάντηση ερωτημάτων ομοιότητας σε τυχαίους υποχώρους.Για να βρούμε αυτή τη δομή, αποφασίσαμε να κατατμήσουμε τα δεδομένα μας κάθετα και να αναθέσουμε τις διάφορες διαστάσεις τους σε μία γνωστή δομή ευρετηρίου (συγκεκριμένα είτε σε ένα R*-δέντρο είτε σε ένα B+-δέντρο). Μετά, αφού έχουμε τα δεδομένα μας κατατμημένα σε διάφορες υπάρχουσες δομές ευρετηρίων και χρησιμοποιώντας τον Threshold Algorithm, έναν αλγόριθμο που απαντά σε ερωτήματα που επιστρέφουν τα κορυφαία δεδομένα ως προς κάποιο κριτήριο, μπορούμε να απαντήσουμε σε ερωτήματα ομοιότητας, πραγματοποιώντας ένα συγκεκριμένο πλήθος από ανακλήσεις δεδομένων, τον οποίο και καταμετρούμε.Σύμφωνα με αυτή τη δομή που περιγράψαμε, προσπαθήσαμε να βρούμε πως πρέπει να τοποθετηθούν τα R*-δέντρα και τα B+-δέντρα στις διαστάσεις των δεδομένων μας, ώστε να έχουμε τις λιγότερες δυνατές ανακλήσεις δεδομένων από το δίσκο, καθώς αυτές καθορίζουν το κόστος της απάντησης ενός ερωτήματος ομοιότητας. Έτσι, αφού πρώτα πραγματοποιήσαμε αρκετές μετρήσεις με διάφορους συνδυασμούς από R*-δέντρα και B+-δέντρα, εξήγαμε διάφορα συμπεράσματα και σχεδιάσαμε έναν αλγόριθμο κατανομής των διαστάσεων της βάσης μας στις προαναφερθείσες δομές ευρετηρίων, ο οποίος δίνει καλές λύσεις.