Back to search

National and Kapodistrian University of Athens

Randomly-oriented RKD-trees

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Νικολόπουλος Δημήτριος. Randomly-oriented RKD-trees. 2014. https://pergamos.lib.uoa.gr/uoa/dl/object/1321343