Στοιχεία επιβλεπόντων καθηγητών:
Ιωάννης Ζ. Εμίρης , Καθηγητής , Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Δημήτριος Φωτάκης , Επίκουρος Καθηγητής, Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ
Άρης Παγουρτζής , Αναπληρωτής Καθηγητής, Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ
Περίληψη:
Σε αυτή τη διπλωματική, παρουσιάζουμε έναν αλγόριθμο για την κατασκευή προσεγγιστικών $r$-nets
σε Ευκλείδιο χώρο υψηλής διάστασης. Δεδομένου ενός μετρικού χώρου $X,|X|=n$, ένα $r$-net είναι ένα υποσύνολο $Ν$ των αρχικών σημείων,
τέτοιο ώστε τα σημεία που ανήκουν στο $Ν$ έχουν απόσταση τουλάχιστον $r$, και όλα τα υπόλοιπα σημεία του σημειοσυνόλου απέχουν απόσταση από τα σημεία του $Ν$ το πολύ $r.$ Για την κατασκευή $r$-net, έχουν προταθεί διάφοροι αλγόριθμοι, οι οποίοι έχουν χρόνο τερματισμού τετραγωνικό στο πλήθος του σημειοσυνόλου ή εκθετικό στη διάσταση του μετρικού χώρου, με ανάλυση χειρότερης περίπτωσης. Οι τεχνικές που χρησιμοποιούνται συχνότερα είναι αυτή της άπληστης μεθόδου, καθώς και της δημιουργίας πλεγμάτων σε συνδυασμό με κατακερματισμό και κουβάδιασμα.
Τέτοιοι αλγόριθμοι δεν μπορούν να θεωρηθούν αποδοτικοί σε
περιπτώσεις μεγάλου πλήθους σημείων και σε περιπτώσεις μετρικών χώρων με υψηλή διάσταση. Μια αποδοτική προσέγγιση για το πρόβλημα της κατασκευής $r$-net σε υψηλή διάσταση είναι ο αλγόριθμος των \cite{EHS15}, οποίος βασίζεται στο LSH (Locality Sensitive Hashing). Ο αλγόριθμός τους είναι πιθανοκρατικός και υπολογίζει προσεγγιστικά $r$-net, με μεγάλη πιθανότητα. O προσεγγιστικός λόγος είναι $1+\epsilon$, για κάθε $\epsilon>0$, και η χρονική πολυπλοκότητα είναι $\tilde{O}(dn^{2-\Theta({\epsilon})})$, για κατάλληλα μικρά $\epsilon$, όπου το $\tilde{O}$ κρύβει πολυλογαριθμικούς παράγοντες. Ο αλγόριθμος που αναπτύσσουμε για την κατασκευή $r$-nets βελτιώνει το αποτέλεσμα των \cite{EHS15} όσο αφορά την εξάρτηση από το $\epsilon$, για κατάλληλα μικρά $\epsilon$. Συγκεκριμένα, η πολυπλοκλότητα του αλγορίθμου είναι $\tilde{O}(dn^{2-\Theta(\sqrt{\epsilon})})$ και υπολογίζει $(1+\epsilon)r$-nets με μεγάλη πιθανότητα. Επιπλέον, η μέθοδος που
χρησιμοποιούμε δεν βασίζεται στο LSH, αντιθέτως εκμεταλλεύεται φαινόμενα που εμφανίζονται σε υψηλές διαστάσεις. Η προσέγγισή μας ακολουθεί αυτή του Valiant \cite{Val15}, για την επίλυση του προβλήματος του προσεγγιστικά κοντινότερου γείτονα. Αρχικά ανάγουμε το πρόβλημά του υπολογισμολού του $r$-net για αυθαίρετα διανύσματα με Ευκλείδια απόσταση στο ίδιο πρόβλημα για μοναδιαία διανύσματα και ακολουθούν διάφορες μετατροπές του προβλήματος όπως μετασχηματισμοί των μοναδιαίων διανυσμάτων σε διανύσματα με στοιχεία 1 ή -1, μετάφραση της Ευκλείδιας απόστασης σε εσωτερικό γινόμενο, και εμβάπτιση του σημειοσυνόλου έτσι ώστε να μπορούμε να ξεχωρίσουμε "μακρινά" και "κοντινά" σημεία. Όλες αυτές οι αναγωγές απαιτούν αποδείξεις ορθότητας, που εγγυώνται ότι θα έχουμε το επιθυμητό αποτέλεσμα, με μεγάλη πιθανότητα, και ότι το συσσωρευτικό σφάλμα, που προκύπτει από την ακολουθία των μετασχηματισμών, είναι στα επιτρεπτά όρια. Στο τελικό στάδιο του αλγορίθμου εκμεταλλευόμαστε γρήγορο πολλαπλασιασμό πινάκων. Ο αλγόριθμός μας μπορεί να χρησιμoποιηθεί σαν υπορουτίνα στο πλαίσιο Net and Prune και να επιλύσει αποδοτικά σε χώρο υψηλής διάστάσης προβλήματα, όπως το $k$-center και $k$-th nearest neighbor distance.
