{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1321343"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1321343","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Randomly-oriented RKD-trees","abstract":"Έστω ένα σύνολο σημείων 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 του αρχικού, όπου s2. Δείχνουμε πως τα δεδομένα μπορούν να επεξεργαστούν στη δοσμένη δομή σε χρόνο 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 πακέτο της βιβλιοθήκης. Τα πειραματικά αποτελέσματα δείχνουν ότι ο προτεινόμενος αλγόριθμος προσφέρει μια υψηλής ποιότητας προσεγγιστική λύση στο πρόβλημα του κοντινότερου γείτονα, όταν τα δεδομένα υψηλής διάστασης μπορούν να εκφραστούν μέσο ενός εγγενή υποχώρου χαμηλής διαστάσης.","abstract_html":"Έστω ένα σύνολο σημείων S σε D-διαστάσεων χώρο R^D , όπου οι αποστάσεις ορίζονται χρησιμοποιώντας την συνάρτηση  : R^D R^D &gt; R (Ευκλείδεια μετρική). Η εύρεση του κοντινότερου γείτονα είναι ένα πρόβλημα βελτιστοποίησης στο οποίο στόχος είναι να βρεθούν τα πλησιέστερα σημεία εντός συνόλου S σε ένα δοσμένο σημείο q  R^D . Για κάποιο πραγματικό ε&gt;0 έχουμε σημείο p  S το οποίο είναι (1+ε)-προσεγγιστικό κοντινότερο γείτονα για κάποιο σημείο εύρεσης q  R^D εάν dist(q, p)  (1 + ε)dist(q, pnn ) όπου p_nn  S είναι ο πραγματικός κοντινότερος γείτονας του σημείου q. Εάν τα δεδομένα τα οποία εκφράζονται σε υψηλής διάστασης χώρο RD εκφράζετε καλύτερα σε έναν ενσωματωμένο χώρο M διάστασης d, όπου d&lt;&lt;D, τότε, δείχνουμε πως υπάρχει τρόπος επεξεργασίας των δεδομένων εντός της δομής Randomly-oriented RKD-trees για την οποία παρέχουμε ένα σχεδόν βέλτιστο όριο του αριθμού των επιπέδων που χρειάζονται ο περιορισμός του μεγέθους των κελιών στο πολύ το 1/s του αρχικού, όπου s2. Δείχνουμε πως τα δεδομένα μπορούν να επεξεργαστούν στη δοσμένη δομή σε χρόνο O(D · N · log N) και χώρο O(D · N), έτσι ώστε για κάποιο σημείο q  R^D και ε&gt;0, ο (1+ε) -προσεγγιστικά κοντινότερος γείτονας του σημείου q μπορεί να αναφερθεί σε O( (D/ε)^O(d log (d) log (d D/ε)) · log N) χρόνο. Επίσης, δείχνουμε ότι οι μέθοδοι που παρουσιάζονται προσφέρουν μια ιδιαίτερα αποτελεσματική εφαρμογή σε μεγάλων διαστάσεων αναζήτηση προσεγγιστικού κοντινότερου γείτονα. Η εφαρμογή μας επεκτείνεται την βιβλιοθήκη Computational Geometry Algorithms Library (CGAL), και πιο συγκεκριμένα spatial searching πακέτο της βιβλιοθήκης. Τα πειραματικά αποτελέσματα δείχνουν ότι ο προτεινόμενος αλγόριθμος προσφέρει μια υψηλής ποιότητας προσεγγιστική λύση στο πρόβλημα του κοντινότερου γείτονα, όταν τα δεδομένα υψηλής διάστασης μπορούν να εκφραστούν μέσο ενός εγγενή υποχώρου χαμηλής διαστάσης.","abstract_has_math":false,"creators":["Νικολόπουλος Δημήτριος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014","date_published":"2014","updated_at":"2026-11-19T05:26:41Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321343"],"render_values":[{"text":"uoadl:1321343","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321343","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321343","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1321343","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Νικολόπουλος Δημήτριος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321343","https://pergamos.lib.uoa.gr/uoa/dl/object/1321343"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Έστω ένα σύνολο σημείων 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 του αρχικού, όπου s2. Δείχνουμε πως τα δεδομένα μπορούν να επεξεργαστούν στη δοσμένη δομή σε χρόνο 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 πακέτο της βιβλιοθήκης. Τα πειραματικά αποτελέσματα δείχνουν ότι ο προτεινόμενος αλγόριθμος προσφέρει μια υψηλής ποιότητας προσεγγιστική λύση στο πρόβλημα του κοντινότερου γείτονα, όταν τα δεδομένα υψηλής διάστασης μπορούν να εκφραστούν μέσο ενός εγγενή υποχώρου χαμηλής διαστάσης.","Consider a set S of points in a real D-dimensional space R^D, where distances are defined using function  : R^D  R^D > R (the Euclidean metric). Nearest neighbor search is an optimization problem for finding the closest points in S to a given query point q  R^D . Given a positive real ε>0, then a point p  S is a (1 + ε)-approximate nearest neighbor of the query point q  R^D if dist(q, p)  (1 + ε)dist(q, p_nn) where p_nnS is the true nearest neighbor to q. If the data that is expressed in high-dimensional space R^D lies closer to an embedded manifold M of dimension d, where d<<D, then, we show the data may be preprocessed into the Randomly-oriented RKD-trees structure and we provide a near optimal bound on the number of levels required to reduce the size of its cells by a factor s2. We show the data may be preprocessed into the structure in O(D · N · log N) time and O(D · N) space, so that given a query point qR^D and ε>0, a (1+ ε)-approximate nearest neighbor of q may be reported in O((D/ε) ^O(d log (d) log (d D/ε)) · log N) time. Following the theoretical results, we show that the methods presented offer a highly efficient implementation in high-dimensional ANN search. Our implementation extends the Computational Geometry Algorithms Library (CGAL) and more specifically the spatial searching package of the library. The experimental results show that the proposed algorithm offers a state of the art ANN search algorithm when searching among high-dimensional data and high-dimensional data with an underlying low-intrinsic dimensional subspace."]},{"key":"dc:title","label":"Title","values":["Randomly-oriented RKD-trees"]}]}],"canonical_facts":{"dc:creator":["Νικολόπουλος Δημήτριος"],"dc:date":["2014"],"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 του αρχικού, όπου s2. Δείχνουμε πως τα δεδομένα μπορούν να επεξεργαστούν στη δοσμένη δομή σε χρόνο 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 πακέτο της βιβλιοθήκης. Τα πειραματικά αποτελέσματα δείχνουν ότι ο προτεινόμενος αλγόριθμος προσφέρει μια υψηλής ποιότητας προσεγγιστική λύση στο πρόβλημα του κοντινότερου γείτονα, όταν τα δεδομένα υψηλής διάστασης μπορούν να εκφραστούν μέσο ενός εγγενή υποχώρου χαμηλής διαστάσης.","Consider a set S of points in a real D-dimensional space R^D, where distances are defined using function  : R^D  R^D > R (the Euclidean metric). Nearest neighbor search is an optimization problem for finding the closest points in S to a given query point q  R^D . Given a positive real ε>0, then a point p  S is a (1 + ε)-approximate nearest neighbor of the query point q  R^D if dist(q, p)  (1 + ε)dist(q, p_nn) where p_nnS is the true nearest neighbor to q. If the data that is expressed in high-dimensional space R^D lies closer to an embedded manifold M of dimension d, where d<<D, then, we show the data may be preprocessed into the Randomly-oriented RKD-trees structure and we provide a near optimal bound on the number of levels required to reduce the size of its cells by a factor s2. We show the data may be preprocessed into the structure in O(D · N · log N) time and O(D · N) space, so that given a query point qR^D and ε>0, a (1+ ε)-approximate nearest neighbor of q may be reported in O((D/ε) ^O(d log (d) log (d D/ε)) · log N) time. Following the theoretical results, we show that the methods presented offer a highly efficient implementation in high-dimensional ANN search. Our implementation extends the Computational Geometry Algorithms Library (CGAL) and more specifically the spatial searching package of the library. The experimental results show that the proposed algorithm offers a state of the art ANN search algorithm when searching among high-dimensional data and high-dimensional data with an underlying low-intrinsic dimensional subspace."],"dc:identifier":["uoadl:1321343","https://pergamos.lib.uoa.gr/uoa/dl/object/1321343"],"dc:language":["English"],"dc:title":["Randomly-oriented RKD-trees"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:41Z"}