National and Kapodistrian University of Athens
Geometric Proximity Problems in High Dimensions
Abstract
dc:descriptionΤα γεωμετρικά προβλήματα εγγύτητας είναι μια κλάση προβλημάτων στην υπολογιστική γεωμετρία που περιλαμβάνει την εκτίμηση αποστάσεων μεταξύ γεωμετρικών αντικειμένων. Σε αυτή την εργασία, εστιάζουμε σε δύο συγκεκριμένα προβλήματα της κλάσης αυτής, τον υπολογισμό των ρ-δικτύων και το πρόβλημα απόφασης του κοντινότερου γείτονα σε χώρους υψηλών διαστάσεων υπό την Ευκλείδεια απόσταση, τα οποία αποτελούν ισχυρά εργαλεία στην υπολογιστική και τη μετρική γεωμετρία. Συγκεκριμένα, παρουσιάζουμε έναν νέο πιθανοτικό αλγόριθμο που υπολογίζει αποδοτικά προσεγγιστικά ρ-δίκτυα ως προς την Ευκλείδια απόσταση. Για οποιοδήποτε σταθερό ε>0, ο προσεγγιστικός παράγοντας είναι 1+ε και η πολυπλοκότητα πολυωνυμική στη διάσταση και υποτετραγωνική στο πλήθος των σημείων. Ο αλγόριθμος επιτυγχάνει με μεγάλη πιθανότητα. Βελτιώνουμε ως προς την πολυπλοκότητα την προηγούμενη καλύτερη γνωστή κατασκευή του Eppstein που βασιζόταν στο LSH, μειώνοντας την εξάρτηση από το ε δεδομένου ότι το ε είναι επαρκώς μικρό. Η μέθοδός μας δεν χρησιμοποιεί το LSH, αλλά αντί αυτού ακολουθεί την προσέγγιση του Valiant, σχεδιάζοντας μια σειρά από αναγωγές του προβλήματός μας σε άλλα προβλήματα σε διαφορετικούς χώρους, υπό την Ευκλείδεια απόσταση ή το εσωτερικό γινόμενο, για τα οποία τα ρ-δίκτυα υπολογίζονται αποδοτικά και το σφάλμα μπορεί να ελεγχθεί. Το αποτέλεσμά μας άμεσα συνεπάγεται αποδοτικές λύσεις σε ένα πλήθος γεωμετρικών προβλημάτων σε υψηλές διαστάσεις, όπως η εύρεση της απόστασης του (1+ε)-προσεγγιστικού κ-κοντινότερου γείτονα σε χρόνο υποτετραγωνικό στο μέγεθος της εισόδου. Επιπλέον, προτείνουμε μια νέα και απλή στην κατασκευή βάση δεδομένων για το πρόβλημα απόφασης του δ-προσεγγιστικού κοντινότερου γείτονα σε χώρους υψηλών διαστάσεων, χρησιμοποιώντας γραμμικό χώρο και υπογραμμικό χρόνο ερώτησης για οποιοδήποτε δ>1: δεδομένης μιας οικογένειας LSH συναρτήσεων για έναν μετρικό χώρο, προβάλουμε τυχαία τα σημεία σε κόμβους του κύβου Hamming διάστασης ≤ logν, όπου ν είναι ο αριθμός των σημείων εισόδου. Ο προβαλλόμενος χώρος περιέχει συμβολοσειρές που λειτουργούν ως κλειδιά για τους «κουβάδες» που περιέχουν τα σημεία της εισόδου. Ο αλγόριθμος ερώτησης απλά προβάλει το σημείο-ερώτηση κι έπειτα εξετάζει τα σημεία που έχουν αντιστοιχηθεί στον ίδιο ή διπλανό κόμβο του κύβου Hamming. Αναλύουμε λεπτομερώς τη χρονική πολυπλοκότητα της ερώτησης για κάποιες βασικές οικογένειες LSH.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Αβαρικιώτη Γεωργία
- Avarikioti Georgia
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1708336