National and Kapodistrian University of Athens
Exploiting the structure of the data in approximate nearest neighbor search
Abstract
dc:descriptionΗ εύρεση του πλησιέστερου γείτονα είναι ένα καίριο πρόβλημα με πολλές σημαντικές εφαρμογές. Για να επιταχύνουμε το χρόνο εύρεσης του κοντινότερου γείτονα εκμεταλλευόμαστε το ότι πολλές φορές τα δεδομένα ακολουθούν μη τυχαία πρότυπα. Συγκεκριμένα, υποθέτουμε ότι τα σημεία που δεχόμαστε ως είσοδο βρίσκονται πάνω σε \logt n άγνωστες ευθείες σε κάποιο χώρο σταθερής διάστασης $d$, όπου $n$ είναι ο αριθμός των σημείων και $t$ είναι μια σταθερά. Οι ευθείες είναι κατανεμημένες ομοιόμορφα σε μια περιορισμένη μπάλα και τα σημεία είναι ομοιόμορφα κατανεμημένα πάνω σε κάθε ευθεία. Δεχόμαστε ότι κάθε ευθεία θα έχει από \Omega (\logt n) έως $O(n)$ σημεία. Η εύρεση ενός κατά προσέγγιση πλησιέστερου γείτονα χρειάζεται O( \log \log n / εO(d2)) αναμενόμενο χρόνο, ο οποίος είναι εκθετικά μικρότερος από το χρόνο που θα χρειαζόταν αν δεν εκμεταλλευόμασταν τη δομή των σημείων. Για κάθε δοσμένο ε>0 ο αλγόριθμος επιστρέφει ένα (1+ε)-κατά προσέγγιση πλησιέστερο γείτονα, χρησιμοποιώντας βέλτιστο χώρο $O(n)$. Αν αγνοήσουμε την εύρεση του πλησιέστερου γείτονα ανάμεσα σε σημεία που βρίσκονται πάνω σε μία ευθεία, ο αλγόριθμος χρειάζεται χρόνο O( \log2 \log n / εO(d2)) με μεγάλη πιθανότητα. Το βασικό βήμα στον αλγόριθμο είναι η εφαρμογή μιάς αναγωγής από την εύρεση κοντινότερης ευθείας, στην εύρεση πλησιέστερου σημείου.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Θάνος Φίλης Αριστοτέλης Εμμανουήλ
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1321064