Abstract
dc:descriptionΈστω ένα σύνολο σημείων S σε D-διαστάσεων χώρο R^D , όπου οι αποστάσεις ορίζονται χρησιμοποιώντας την συνάρτηση : R^D R^D > R (Ευκλείδεια μετρική). Η εύρεση του κοντινότερου γείτονα είναι ένα πρόβλημα βελτιστοποίησης στο οποίο στόχος είναι να βρεθούν τα πλησιέστερα σημεία εντός συνόλου S σε ένα δοσμένο σημείο q R^D . Για κάποιο πραγματικό ε>0 έχουμε σημείο p S το οποίο είναι (1+ε)-προσεγγιστικό κοντινότερο γείτονα για κάποιο σημείο εύρεσης q R^D εάν dist(q, p) (1 + ε)dist(q, pnn ) όπου p_nn S είναι ο πραγματικός κοντινότερος γείτονας του σημείου q. Εάν τα δεδομένα τα οποία εκφράζονται σε υψηλής διάστασης χώρο RD εκφράζετε καλύτερα σε έναν ενσωματωμένο χώρο M διάστασης d, όπου d<<D, τότε, δείχνουμε πως υπάρχει τρόπος επεξεργασίας των δεδομένων εντός της δομής Randomly-oriented RKD-trees για την οποία παρέχουμε ένα σχεδόν βέλτιστο όριο του αριθμού των επιπέδων που χρειάζονται ο περιορισμός του μεγέθους των κελιών στο πολύ το 1/s του αρχικού, όπου s2. Δείχνουμε πως τα δεδομένα μπορούν να επεξεργαστούν στη δοσμένη δομή σε χρόνο O(D · N · log N) και χώρο O(D · N), έτσι ώστε για κάποιο σημείο q R^D και ε>0, ο (1+ε) -προσεγγιστικά κοντινότερος γείτονας του σημείου q μπορεί να αναφερθεί σε O( (D/ε)^O(d log (d) log (d D/ε)) · log N) χρόνο. Επίσης, δείχνουμε ότι οι μέθοδοι που παρουσιάζονται προσφέρουν μια ιδιαίτερα αποτελεσματική εφαρμογή σε μεγάλων διαστάσεων αναζήτηση προσεγγιστικού κοντινότερου γείτονα. Η εφαρμογή μας επεκτείνεται την βιβλιοθήκη Computational Geometry Algorithms Library (CGAL), και πιο συγκεκριμένα spatial searching πακέτο της βιβλιοθήκης. Τα πειραματικά αποτελέσματα δείχνουν ότι ο προτεινόμενος αλγόριθμος προσφέρει μια υψηλής ποιότητας προσεγγιστική λύση στο πρόβλημα του κοντινότερου γείτονα, όταν τα δεδομένα υψηλής διάστασης μπορούν να εκφραστούν μέσο ενός εγγενή υποχώρου χαμηλής διαστάσης.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Νικολόπουλος Δημήτριος
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1321343