National and Kapodistrian University of Athens
High dimensional Approximate r-nets with emphasis on vectors on a unit hypercube
Abstract
dc:descriptionΣε αυτή τη διπλωματική, παρουσιάζουμε έναν αλγόριθμο για την κατασκευή προσεγγιστικών $r$-nets σε Ευκλείδιο χώρο υψηλής διάστασης. Δεδομένου ενός μετρικού χώρου $X,|X|=n$, ένα $r$-net είναι ένα υποσύνολο $Ν$ των αρχικών σημείων, τέτοιο ώστε τα σημεία που ανήκουν στο $Ν$ έχουν απόσταση τουλάχιστον $r$, και όλα τα υπόλοιπα σημεία του σημειοσυνόλου απέχουν απόσταση από τα σημεία του $Ν$ το πολύ $r.$ Για την κατασκευή $r$-net, έχουν προταθεί διάφοροι αλγόριθμοι, οι οποίοι έχουν χρόνο τερματισμού τετραγωνικό στο πλήθος του σημειοσυνόλου ή εκθετικό στη διάσταση του μετρικού χώρου, με ανάλυση χειρότερης περίπτωσης. Οι τεχνικές που χρησιμοποιούνται συχνότερα είναι αυτή της άπληστης μεθόδου, καθώς και της δημιουργίας πλεγμάτων σε συνδυασμό με κατακερματισμό και κουβάδιασμα. Τέτοιοι αλγόριθμοι δεν μπορούν να θεωρηθούν αποδοτικοί σε περιπτώσεις μεγάλου πλήθους σημείων και σε περιπτώσεις μετρικών χώρων με υψηλή διάσταση. Μια αποδοτική προσέγγιση για το πρόβλημα της κατασκευής $r$-net σε υψηλή διάσταση είναι ο αλγόριθμος των \cite{EHS15}, οποίος βασίζεται στο LSH (Locality Sensitive Hashing). Ο αλγόριθμός τους είναι πιθανοκρατικός και υπολογίζει προσεγγιστικά $r$-net, με μεγάλη πιθανότητα. O προσεγγιστικός λόγος είναι 1+ε, για κάθε ε>0, και η χρονική πολυπλοκότητα είναι \tilde{O}(dn2-\Theta({ε})), για κατάλληλα μικρά ε, όπου το $\tilde{O}$ κρύβει πολυλογαριθμικούς παράγοντες. Ο αλγόριθμος που αναπτύσσουμε για την κατασκευή $r$-nets βελτιώνει το αποτέλεσμα των \cite{EHS15} όσο αφορά την εξάρτηση από το ε, για κατάλληλα μικρά ε. Συγκεκριμένα, η πολυπλοκλότητα του αλγορίθμου είναι \tilde{O}(dn2-\Theta(\sqrt{ε})) και υπολογίζει (1+ε)r-nets με μεγάλη πιθανότητα. Επιπλέον, η μέθοδος που χρησιμοποιούμε δεν βασίζεται στο LSH, αντιθέτως εκμεταλλεύεται φαινόμενα που εμφανίζονται σε υψηλές διαστάσεις. Η προσέγγισή μας ακολουθεί αυτή του Valiant \cite{Val15}, για την επίλυση του προβλήματος του προσεγγιστικά κοντινότερου γείτονα. Αρχικά ανάγουμε το πρόβλημά του υπολογισμολού του $r$-net για αυθαίρετα διανύσματα με Ευκλείδια απόσταση στο ίδιο πρόβλημα για μοναδιαία διανύσματα και ακολουθούν διάφορες μετατροπές του προβλήματος όπως μετασχηματισμοί των μοναδιαίων διανυσμάτων σε διανύσματα με στοιχεία 1 ή -1, μετάφραση της Ευκλείδιας απόστασης σε εσωτερικό γινόμενο, και εμβάπτιση του σημειοσυνόλου έτσι ώστε να μπορούμε να ξεχωρίσουμε "μακρινά" και "κοντινά" σημεία. Όλες αυτές οι αναγωγές απαιτούν αποδείξεις ορθότητας, που εγγυώνται ότι θα έχουμε το επιθυμητό αποτέλεσμα, με μεγάλη πιθανότητα, και ότι το συσσωρευτικό σφάλμα, που προκύπτει από την ακολουθία των μετασχηματισμών, είναι στα επιτρεπτά όρια. Στο τελικό στάδιο του αλγορίθμου εκμεταλλευόμαστε γρήγορο πολλαπλασιασμό πινάκων. Ο αλγόριθμός μας μπορεί να χρησιμoποιηθεί σαν υπορουτίνα στο πλαίσιο Net and Prune και να επιλύσει αποδοτικά σε χώρο υψηλής διάστάσης προβλήματα, όπως το $k$-center και $k$-th nearest neighbor distance.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Κάβουρας Λουκάς
- Kavouras Loukas
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, English, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:1325624