Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2012-08-03
Συγγραφέας:
Θάνος Φίλης Αριστοτέλης Εμμανουήλ
Στοιχεία επιβλεπόντων καθηγητών:
Καθηγητής Ιωάννης Εμίρης
Πρωτότυπος Τίτλος:
Exploiting the structure of the data in approximate nearest neighbor search
Γλώσσες εργασίας:
Αγγλικά
Περίληψη:
Η εύρεση του πλησιέστερου γείτονα είναι ένα καίριο πρόβλημα με πολλές
σημαντικές εφαρμογές.
Για να επιταχύνουμε το χρόνο εύρεσης του κοντινότερου γείτονα εκμεταλλευόμαστε
το ότι πολλές φορές τα δεδομένα ακολουθούν μη τυχαία πρότυπα.
Συγκεκριμένα, υποθέτουμε ότι τα σημεία που δεχόμαστε ως είσοδο βρίσκονται πάνω
σε $\log^t n$ άγνωστες ευθείες σε κάποιο χώρο σταθερής διάστασης $d$,
όπου $n$ είναι ο αριθμός των σημείων και $t$ είναι μια σταθερά. Οι ευθείες
είναι κατανεμημένες ομοιόμορφα σε μια περιορισμένη μπάλα και τα σημεία
είναι ομοιόμορφα κατανεμημένα πάνω σε κάθε ευθεία. Δεχόμαστε ότι κάθε ευθεία θα
έχει από $\Omega (\log^t n)$ έως $O(n)$ σημεία.
Η εύρεση ενός κατά προσέγγιση πλησιέστερου γείτονα χρειάζεται $O( \log \log n /
\epsilon^{O(d^2)})$ αναμενόμενο χρόνο, ο οποίος είναι εκθετικά μικρότερος από το
χρόνο που θα χρειαζόταν αν δεν εκμεταλλευόμασταν τη δομή των σημείων. Για κάθε
δοσμένο $\epsilon>0$ ο αλγόριθμος επιστρέφει ένα $(1+\epsilon)$-κατά προσέγγιση
πλησιέστερο γείτονα,
χρησιμοποιώντας βέλτιστο χώρο $O(n)$. Αν αγνοήσουμε την εύρεση του πλησιέστερου
γείτονα ανάμεσα σε σημεία που βρίσκονται πάνω σε μία ευθεία, ο αλγόριθμος
χρειάζεται χρόνο $O( \log^2 \log n / \epsilon^{O(d^2)})$ με μεγάλη πιθανότητα.
Το βασικό βήμα στον αλγόριθμο είναι η εφαρμογή μιάς αναγωγής από την εύρεση
κοντινότερης ευθείας, στην εύρεση πλησιέστερου σημείου.
Λέξεις-κλειδιά:
Κοντινότερη ευθεία, Ευθυγραμμισμένα σημεία, Δομημένα δεδομένα, Εκθετική βελτίωση, Βέλτιστος χώρος
Αρ. σελίδων ευρετηρίου:
0
Αρ. βιβλιογραφικών αναφορών:
26
