Πολυδιάστατα ευρετήρια για ερωτήσεις πλησιέστερων γειτόνων
Μεταπτυχιακή διπλωματική εργασία
Συγγραφέας
Λυκουρέντζος, Χρήστος
Ημερομηνία
2013-04Επιβλέπων
Βασιλάκης, ΚώσταςΘεματική επικεφαλίδα
Πληροφοριακά συστήματαΛέξεις κλειδιά
Μέθοδος δεικτοδότησης iDistance ; Μέθοδος δεικτοδότησης LSH ; Μέθοδος ευρετηρίου Medank ; Ευρετήρια ; Πλησιέστεροι γείτονεςΠερίληψη
Η αναζήτηση πλησιέστερων γειτόνων είναι ένα κλασικό πρόβλημα με πολλές
εφαρμογές σε τομείς όπως η τεχνητή νοημοσύνη, η αναγνώριση προτύπων, η ανάκτηση πληροφορίας και άλλα.
Η παρούσα πτυχιακή εργασία αποτελεί μια προσπάθεια παρουσίασης, βελτίωσης και επέκτασης διαφόρων τεχνικών πάνω στο πρόβλημα της αναζήτησης πλησιέστερων γειτόνων.
Παρουσιάζεται η μέθοδος iDistance, η οποία είναι μια μέθοδος δεικτοδότησης
για την αναζήτηση του Κ- πλησιέστερου γείτονα σε πολυδιάστατο μετρικό χώρο.
Η μέθοδος iDistance είναι βασισμένη σε ένα αποτελεσματικό δένδρο Β+. Στη συνέχεια έγινε επιλογή των σημείων αναφοράς και διαμέρισης του χώρου δεδομένων
και παρουσιάζονται διάφορα συμπεράσματα που προέκυψαν από τη μέθοδο αυτή.
Στη συνέχεια, μελετάμε μια άλλη μέθοδο για την αναζήτηση πλησιέστερων
γειτόνων, την LSH. Παρουσιάζονται και άλλες τεχνικές, όπως η μέθοδος Adhoc-
LSH, η Rigorous LSH που παρουσιάζουν, αναλύουν και προτείνουν λύσεις για το
εν λόγω πρόβλημα. Μελετούμε τη δομή Δένδρο LSB καθώς και τον αλγόριθμο ΝΝ,
παραθέτοντας μια ανάλυσή του καθώς και των επεκτάσεων που προκύπτουν.
Τέλος παρουσιάζεται και αναλύεται μια πρωτότυπη προσέγγιση για την αποδοτική αναζήτηση ομοιότητας και ταξινόμησης σε πολυδιάστατα δεδομένα, η μέθοδος ευρετηρίου MedRank. Στο οικείο κεφάλαιο παρουσιάζεται αναλυτικά η εν
λόγω μέθοδος και ο αλγόριθμος MedRank καθώς και διάφορες παραλλαγές του.
Περίληψη
The query for nearest neighbour is a well known, problem with many implementations
on different sectors, such as artificial intelligence, paern recognition and information
retrieval. The present diploma thesis is an effort to presentat, improve and expand
techniques coping with the problem of nearest neighbour query.
Method iDistance, which is an indexing method for K-nearest neighbour query in a
multi-dimensional metric space, was studied and is presented. iDistance is based on an
eficient B+ Tree structure. Reference points selection and data space partitioning were
made.
Afterwards, we study the LSH method, considering extensions such as Adhoc-LSH
and Rigorous LSH. These methods present, analyse and try to give a solution on the
existing problem, while details on hash functions are also given. The LSB Tree and the
NN algorithm are presented.
Finally, an analysis of a novel approach, tackling effective similarity search and
classification regarding multi-dimensional data, namely MedRank is presented. We
also consider its variations, OmedRank and L2TA.
Αριθμός σελίδων
60 σελ.Σχολή
Σχολή Θετικών Επιστημών και ΤεχνολογίαςΑκαδημαϊκό Τμήμα
Τμήμα Επιστήμης και Τεχνολογίας ΥπολογιστώνΤίτλος Προγράμματος Μεταπτυχιακών Σπουδών
Επιστήμη και Τεχνολογία ΥπολογιστώνΓλώσσα
ΕλληνικάΠεριγραφή
Μ.Δ.Ε. 30Οι παρακάτω άδειες σχετίζονται με αυτό το τεκμήριο: