Πολυδιάστατα ευρετήρια για ερωτήσεις πλησιέστερων γειτόνων

Abstract

Η αναζήτηση πλησιέστερων γειτόνων είναι ένα κλασικό πρόβλημα με πολλές εφαρμογές σε τομείς όπως η τεχνητή νοημοσύνη, η αναγνώριση προτύπων, η ανάκτηση πληροφορίας και άλλα. Η παρούσα πτυχιακή εργασία αποτελεί μια προσπάθεια παρουσίασης, βελτίωσης και επέκτασης διαφόρων τεχνικών πάνω στο πρόβλημα της αναζήτησης πλησιέστερων γειτόνων. Παρουσιάζεται η μέθοδος iDistance, η οποία είναι μια μέθοδος δεικτοδότησης για την αναζήτηση του Κ- πλησιέστερου γείτονα σε πολυδιάστατο μετρικό χώρο. Η μέθοδος iDistance είναι βασισμένη σε ένα αποτελεσματικό δένδρο Β+. Στη συνέχεια έγινε επιλογή των σημείων αναφοράς και διαμέρισης του χώρου δεδομένων και παρουσιάζονται διάφορα συμπεράσματα που προέκυψαν από τη μέθοδο αυτή. Στη συνέχεια, μελετάμε μια άλλη μέθοδο για την αναζήτηση πλησιέστερων γειτόνων, την LSH. Παρουσιάζονται και άλλες τεχνικές, όπως η μέθοδος Adhoc- LSH, η Rigorous LSH που παρουσιάζουν, αναλύουν και προτείνουν λύσεις για το εν λόγω πρόβλημα. Μελετούμε τη δομή Δένδρο LSB καθώς και τον αλγόριθμο ΝΝ, παραθέτοντας μια ανάλυσή του καθώς και των επεκτάσεων που προκύπτουν. Τέλος παρουσιάζεται και αναλύεται μια πρωτότυπη προσέγγιση για την αποδοτική αναζήτηση ομοιότητας και ταξινόμησης σε πολυδιάστατα δεδομένα, η μέθοδος ευρετηρίου MedRank. Στο οικείο κεφάλαιο παρουσιάζεται αναλυτικά η εν λόγω μέθοδος και ο αλγόριθμος MedRank καθώς και διάφορες παραλλαγές του.