Geometric Proximity Problems in High Dimensions

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

Μονάδα:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2017-07-06
Έτος εκπόνησης:
2017
Συγγραφέας:
Αβαρικιώτη Γεωργία
Στοιχεία επιβλεπόντων καθηγητών:
Ιωάννης Ζ. Εμίρης, Καθηγητής, Τμήμα Πληροφορικής & Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Πρωτότυπος Τίτλος:
Geometric Proximity Problems in High Dimensions
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Γεωμετρικά Προβλήματα Εγγύτητας σε Υψηλές Διαστάσεις
Περίληψη:
Τα γεωμετρικά προβλήματα εγγύτητας είναι μια κλάση προβλημάτων στην υπολογιστική γεωμετρία που περιλαμβάνει την εκτίμηση αποστάσεων μεταξύ γεωμετρικών αντικειμένων. Σε αυτή την εργασία, εστιάζουμε σε δύο συγκεκριμένα προβλήματα της κλάσης αυτής, τον υπολογισμό των ρ-δικτύων και το πρόβλημα απόφασης του κοντινότερου γείτονα σε χώρους υψηλών διαστάσεων υπό την Ευκλείδεια απόσταση, τα οποία αποτελούν ισχυρά εργαλεία στην υπολογιστική και τη μετρική γεωμετρία. Συγκεκριμένα, παρουσιάζουμε έναν νέο πιθανοτικό αλγόριθμο που υπολογίζει αποδοτικά προσεγγιστικά ρ-δίκτυα ως προς την Ευκλείδια απόσταση. Για οποιοδήποτε σταθερό ε>0, ο προσεγγιστικός παράγοντας είναι 1+ε και η πολυπλοκότητα πολυωνυμική στη διάσταση και υποτετραγωνική στο πλήθος των σημείων. Ο αλγόριθμος επιτυγχάνει με μεγάλη πιθανότητα. Βελτιώνουμε ως προς την πολυπλοκότητα την προηγούμενη καλύτερη γνωστή κατασκευή του Eppstein που βασιζόταν στο LSH, μειώνοντας την εξάρτηση από το ε δεδομένου ότι το ε είναι επαρκώς μικρό. Η μέθοδός μας δεν χρησιμοποιεί το LSH, αλλά αντί αυτού ακολουθεί την προσέγγιση του Valiant, σχεδιάζοντας μια σειρά από αναγωγές του προβλήματός μας σε άλλα προβλήματα σε διαφορετικούς χώρους, υπό την Ευκλείδεια απόσταση ή το εσωτερικό γινόμενο, για τα οποία τα ρ-δίκτυα υπολογίζονται αποδοτικά και το σφάλμα μπορεί να ελεγχθεί. Το αποτέλεσμά μας άμεσα συνεπάγεται αποδοτικές λύσεις σε ένα πλήθος γεωμετρικών προβλημάτων σε υψηλές διαστάσεις, όπως η εύρεση της απόστασης του (1+ε)-προσεγγιστικού κ-κοντινότερου γείτονα σε χρόνο υποτετραγωνικό στο μέγεθος της εισόδου. Επιπλέον, προτείνουμε μια νέα και απλή στην κατασκευή βάση δεδομένων για το πρόβλημα απόφασης του δ-προσεγγιστικού κοντινότερου γείτονα σε χώρους υψηλών διαστάσεων, χρησιμοποιώντας γραμμικό χώρο και υπογραμμικό χρόνο ερώτησης για οποιοδήποτε δ>1: δεδομένης μιας οικογένειας LSH συναρτήσεων για έναν μετρικό χώρο, προβάλουμε τυχαία τα σημεία σε κόμβους του κύβου Hamming διάστασης ≤ logν, όπου ν είναι ο αριθμός των σημείων εισόδου. Ο προβαλλόμενος χώρος περιέχει συμβολοσειρές που λειτουργούν ως κλειδιά για τους «κουβάδες» που περιέχουν τα σημεία της εισόδου. Ο αλγόριθμος ερώτησης απλά προβάλει το σημείο-ερώτηση κι έπειτα εξετάζει τα σημεία που έχουν αντιστοιχηθεί στον ίδιο ή διπλανό κόμβο του κύβου Hamming. Αναλύουμε λεπτομερώς τη χρονική πολυπλοκότητα της ερώτησης για κάποιες βασικές οικογένειες LSH.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λοιπές θεματικές κατηγορίες:
Αλγόριθμοι υπολογιστών
Λέξεις-κλειδιά:
υπολογιστική γεωμετρία, γεωμετρικοί αλγόριθμοι, μετρική γεωμετρία, προσεγγιστικοί αλγόριθμοι, ρ-δίκτυα, γραμμικός χώρος, κοντινότερος γείτονας
Ευρετήριο:
Ναι
Αρ. σελίδων ευρετηρίου:
2
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
34
Αριθμός σελίδων:
68