Dimensionality reduction for approximate near neighbor search in the Manhattan metric

Διπλωματική Εργασία uoadl:2868157 331 Αναγνώσεις

Μονάδα:
Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)
Πληροφορική
Ημερομηνία κατάθεσης:
2019-04-19
Έτος εκπόνησης:
2019
Συγγραφέας:
Μαργώνης Βασίλειος
Στοιχεία επιβλεπόντων καθηγητών:
Ιωάννης Εμίρης, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Πρωτότυπος Τίτλος:
Dimensionality reduction for approximate near neighbor search in the Manhattan metric
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Μείωση διάστασης για την αναζήτηση προσεγγιστικού κοντινού γείτονα στη μετρική Μανχάταν
Περίληψη:
Οι τυχαίες προβολές αποτελούν μια απο τις πιο διαδεδομένες μεθόδους για το χειρισμό δεδομένων μεγάλης διάστασης. Ξεκινώντας από το περίφημο Johnson-Lindenstrauss Lemma, τέτοιου είδους προβολές έχουν μελετηθεί αρκετά για την Ευκλείδια (L2) μετρική, και πολύ λιγότερο για τη μετρική Μανχάταν (L1). Σε αυτή την εργασία εστιάζουμε στο πρόβλημα του προσεγγιστικού κοντινότερου γείτονα στη μετρική Μανχάταν, εκμεταλλεύοντας την αποφαντική εκδοχή του προβλήματος, που λέγεται προσεγγιστικός κοντινός γείτονας και επιβάλει ένα (περίπου) λογαριθμικό κόστος.

Το 2007, οι Indyk και Naor εισήγαγαν την έννοια των εμβυθίσεων που διατηρούν τον κοντινότερο γείτονα (nearest neighbor-preserving embeddings). Οι εμβυθίσεις αυτές είναι τυχαιοκρατικές και εγγυόνται για την αλλοίωση μόνο N αποστάσεων (μεταξύ ενός σημείου-query και N σημείων), αντί για όλα τις δυνατές O(N^2). Τέτοιου είδους εμβυθίσεις υπάρχουν για τις μετρικές L2 και L1, καθώς και για διπλασιάζοντα (doubling) υποσύνολα της L2.

Σε αυτή την εργασία παρουσιάζουμε μια συνάρτηση εμβύθισης για την μείωση διάστασης, η οποία διατηρεί τον κοντινό γείτονα (near neighbor-preserving) για διπλασιάζοντα υποσύνολα της L1. Η τεχνική που εφαρμόζουμε είναι να προβάλουμε τυχαία όχι τα ίδια τα σημεία, αλλά ένα σύνολο αντιπροσώπων τους. Μελετούμε δύο είδη αντιπροσώπων, τα approximate nets και τα randomly shifted grids, και τα συγκρίνουμε ως προς την νέα διάσταση και το χρόνο υπολογισμού της συνάρτησης εμβύθισης.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
Προσεγγιστικός κοντινότερος γείτονας, μείωση διάστασης, μετρική Μανχάταν, τυχαίες προβολές
Ευρετήριο:
Ναι
Αρ. σελίδων ευρετηρίου:
1
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
39
Αριθμός σελίδων:
45