BLC-RFANN : B+ tree with Lazy Caching for RFANN

Abstract

Η παρακάτω Μεταπτυχιακή Διπλωματική Εργασία (Μ.Δ.Ε.) εξετάζει τον αλγόριθμο BLC-RFANN (B+ tree with Lazy Caching for RFANN ή Β+ δέντρο με “νωθρή” προσωρινή μνήμη για το RFANN), μία νέα μέθοδο η οποία εκτελεί ερωτήματα Προσεγγιστικής Εύρεσης Κοντινότερων Γειτόνων με Περιορισμό Εύρους (η οποία είναι γνωστή με το αγγλικό της ακρωνύμιο RFANN). Οι υπάρχουσες μέθοδοι είναι σχεδιασμένες να λειτουργούν με στατικά σύνολα δεδομένων (δηλαδή σύνολα δεδομένων όπου τα δεδομένα παραμένουν τα ίδια σε βάθος χρόνου), ενώ δεν έχουν κάποιον ιδιαίτερο μηχανισμό κρυφής μνήμης για την βελτίωση της ταχύτητας εκτέλεσης. Τα δύο βασικά στοιχεία της μεθόδου μας (δηλαδή το Β+ δέντρο και ο μηχανισμός κρύφης μνήμης) προσπαθούν να αντιμετωπίσουν αυτούς τους περιορισμούς.

Δοθέντος ενός συνόλου δεδομένων (στο οποίο κάθε δεδομένο αποτελείται από ένα διάνυσμα και μία αριθμητική τιμή) και ενός διανύσματος-εισόδου συνοδευόμενου από ένα εύρος τιμών, ο στόχος μας είναι να βρούμε τους κοντινότερους γείτονες του διανύσματος-εισόδου, των οποίων οι αριθμητικές τιμές ανήκουν στο προαναφερθέν εύρος. Είναι ένα ερώτημα το οποίο παρουσιάζει πλήθος εφαρμογών.

Η παραπάνω μέθοδος βασίζεται στο Β+ δέντρο, μία (ήδη υπάρχουσα) παραλλαγή του Β-δέντρου όπου τα δεδομένα αποθηκεύονται μόνο στα φύλλα του δέντρου (και όχι σε κάποιον άλλο εσωτερικό κόμβο) και έναν σύνθετο μηχανισμό κρυφής μνήμης (cache) ο οποίος κατασκευάστηκε για να μειώσει τον χρόνο απάντησης των ερωτημάτων.

Ο στόχος μας σε αυτήν την εργασία είναι να συγκρίνουμε την επίδοση της με άλλους μοντέρνους αλγορίθμους που χρησιμοποιούνται για ερωτήματα RFANN σε διάφορες μετρικές, όπως τον χρόνο δημιουργίας των ευρετηρίων τα οποία παράγουν οι μέθοδοι, το μέγεθος χώρου που χρειάζεται για να αποθηκευτούν στην μνήμη τα εν λόγω ευρετήρια, τον αριθμό ερωτημάτων ο οποίος εκτελείται ανά δευτερόλεπτο, καθώς και την ανάκληση (ή recall, δηλαδή τον αριθμό των ανακληθέντων σωστών αποτελεσμάτων ως προς τον αριθμό των αληθινών αποτελεσμάτων), η οποία είναι η πιο συνήθης μετρική για να μετρήσουμε την ορθότητα των απαντήσεων ενός αλγορίθμου.

Τα πειράματα τα οποία εκτελέσαμε δείχνουν ότι ο BLC-RFANN χτίζει το ευρετήριό του πιο γρήγορα και χρειάζεται (κατά μέσο όρο) λιγότερο χώρο αποθήκευσης σε σχέση με τους ανταγωνιστές του, καθώς επίσης ότι έχει ένα πολύ υψηλό επίπεδο ανάκλησης (με συγκεκριμένες ρυθμίσεις μπορεί να φτάσει το 100%), αν και προφανώς με ένα μικρότερο ρυθμό εκτέλεσης ερωτημάτων.

Παρόλα αυτά, λειτουργίες όπως ο μηχανισμός μας κρυφής μνήμης κατάφεραν να αυξήσουν τον ρυθμό εκτέλεσης ερωτημάτων, ενώ σε κάποια συγκεκριμένα σενάρια (όπως για ερωτήματα όπου το εύρος τιμών είναι σχετικά μικρό, ή όταν το σύνολο δεδομένων είναι μεγάλο ως προς τους διαθέσιμους υπολογιστικούς πόρους) ο BLC-RFANN μπορεί να εκτελέσει ερωτήματα με την ίδια ταχύτητα που έχουν οι μοντέρνες μέθοδοι RFANN.