{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1321064"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1321064","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Exploiting the structure of the data in approximate nearest neighbor search","abstract":"Η εύρεση του πλησιέστερου γείτονα είναι ένα καίριο πρόβλημα με πολλές σημαντικές εφαρμογές. Για να επιταχύνουμε το χρόνο εύρεσης του κοντινότερου γείτονα εκμεταλλευόμαστε το ότι πολλές φορές τα δεδομένα ακολουθούν μη τυχαία πρότυπα. Συγκεκριμένα, υποθέτουμε ότι τα σημεία που δεχόμαστε ως είσοδο βρίσκονται πάνω σε $\\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)})$ με μεγάλη πιθανότητα. Το βασικό βήμα στον αλγόριθμο είναι η εφαρμογή μιάς αναγωγής από την εύρεση κοντινότερης ευθείας, στην εύρεση πλησιέστερου σημείου.","abstract_html":"Η εύρεση του πλησιέστερου γείτονα είναι ένα καίριο πρόβλημα με πολλές σημαντικές εφαρμογές. Για να επιταχύνουμε το χρόνο εύρεσης του κοντινότερου γείτονα εκμεταλλευόμαστε το ότι πολλές φορές τα δεδομένα ακολουθούν μη τυχαία πρότυπα. Συγκεκριμένα, υποθέτουμε ότι τα σημεία που δεχόμαστε ως είσοδο βρίσκονται πάνω σε <span class=\"etd-inline-math\">\\log<sup>t</sup> n</span> άγνωστες ευθείες σε κάποιο χώρο σταθερής διάστασης $d$, όπου $n$ είναι ο αριθμός των σημείων και $t$ είναι μια σταθερά. Οι ευθείες είναι κατανεμημένες ομοιόμορφα σε μια περιορισμένη μπάλα και τα σημεία είναι ομοιόμορφα κατανεμημένα πάνω σε κάθε ευθεία. Δεχόμαστε ότι κάθε ευθεία θα έχει από <span class=\"etd-inline-math\">\\Omega (\\log<sup>t</sup> n)</span> έως $O(n)$ σημεία. Η εύρεση ενός κατά προσέγγιση πλησιέστερου γείτονα χρειάζεται <span class=\"etd-inline-math\">O( \\log \\log n / &epsilon;<sup>O(d<sup>2</sup>)</sup>)</span> αναμενόμενο χρόνο, ο οποίος είναι εκθετικά μικρότερος από το χρόνο που θα χρειαζόταν αν δεν εκμεταλλευόμασταν τη δομή των σημείων. Για κάθε δοσμένο <span class=\"etd-inline-math\">&epsilon;&gt;0</span> ο αλγόριθμος επιστρέφει ένα <span class=\"etd-inline-math\">(1+&epsilon;)</span>-κατά προσέγγιση πλησιέστερο γείτονα, χρησιμοποιώντας βέλτιστο χώρο $O(n)$. Αν αγνοήσουμε την εύρεση του πλησιέστερου γείτονα ανάμεσα σε σημεία που βρίσκονται πάνω σε μία ευθεία, ο αλγόριθμος χρειάζεται χρόνο <span class=\"etd-inline-math\">O( \\log<sup>2</sup> \\log n / &epsilon;<sup>O(d<sup>2</sup>)</sup>)</span> με μεγάλη πιθανότητα. Το βασικό βήμα στον αλγόριθμο είναι η εφαρμογή μιάς αναγωγής από την εύρεση κοντινότερης ευθείας, στην εύρεση πλησιέστερου σημείου.","abstract_has_math":true,"creators":["Θάνος Φίλης Αριστοτέλης Εμμανουήλ"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012","date_published":"2012","updated_at":"2026-11-19T05:26:38Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321064"],"render_values":[{"text":"uoadl:1321064","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321064","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321064","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%3A1321064","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":["2012"]},{"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:1321064","https://pergamos.lib.uoa.gr/uoa/dl/object/1321064"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η εύρεση του πλησιέστερου γείτονα είναι ένα καίριο πρόβλημα με πολλές σημαντικές εφαρμογές. Για να επιταχύνουμε το χρόνο εύρεσης του κοντινότερου γείτονα εκμεταλλευόμαστε το ότι πολλές φορές τα δεδομένα ακολουθούν μη τυχαία πρότυπα. Συγκεκριμένα, υποθέτουμε ότι τα σημεία που δεχόμαστε ως είσοδο βρίσκονται πάνω σε $\\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)})$ με μεγάλη πιθανότητα. Το βασικό βήμα στον αλγόριθμο είναι η εφαρμογή μιάς αναγωγής από την εύρεση κοντινότερης ευθείας, στην εύρεση πλησιέστερου σημείου.","Nearest neighbor searching (NNS) is a fundamental problem with several important applications. To accelerate the queries, we exploit the fact that data often exhibits highly nonrandom spatial patterns. We consider input points almost lying on about $\\log^t n$ unknown lines in a space of constant dimension $d$, where $n$ is the number of points and $t$ constant. The lines are distributed uniformly in a bounding sphere, the points are distributed uniformly on each line, and their number per line varies from $\\Omega (\\log^t n)$ to $O(n)$. Queries take $O( \\log \\log n / \\epsilon^{O(d^2)})$ expected time, which is exponentially faster than without structure, using optimal space $O(n)$, and return a $(1+\\epsilon)$-approximate nearest neighbor, for any given $\\epsilon>0$. Ignoring the step of NNS on a line, queries take $O( \\log^2 \\log n / \\epsilon^{O(d^2)})$ with high probability. Our key step is to employ a reduction of determining the nearest line to NNS among points."]},{"key":"dc:title","label":"Title","values":["Exploiting the structure of the data in approximate nearest neighbor search"]}]}],"canonical_facts":{"dc:creator":["Θάνος Φίλης Αριστοτέλης Εμμανουήλ"],"dc:date":["2012"],"dc:description":["Η εύρεση του πλησιέστερου γείτονα είναι ένα καίριο πρόβλημα με πολλές σημαντικές εφαρμογές. Για να επιταχύνουμε το χρόνο εύρεσης του κοντινότερου γείτονα εκμεταλλευόμαστε το ότι πολλές φορές τα δεδομένα ακολουθούν μη τυχαία πρότυπα. Συγκεκριμένα, υποθέτουμε ότι τα σημεία που δεχόμαστε ως είσοδο βρίσκονται πάνω σε $\\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)})$ με μεγάλη πιθανότητα. Το βασικό βήμα στον αλγόριθμο είναι η εφαρμογή μιάς αναγωγής από την εύρεση κοντινότερης ευθείας, στην εύρεση πλησιέστερου σημείου.","Nearest neighbor searching (NNS) is a fundamental problem with several important applications. To accelerate the queries, we exploit the fact that data often exhibits highly nonrandom spatial patterns. We consider input points almost lying on about $\\log^t n$ unknown lines in a space of constant dimension $d$, where $n$ is the number of points and $t$ constant. The lines are distributed uniformly in a bounding sphere, the points are distributed uniformly on each line, and their number per line varies from $\\Omega (\\log^t n)$ to $O(n)$. Queries take $O( \\log \\log n / \\epsilon^{O(d^2)})$ expected time, which is exponentially faster than without structure, using optimal space $O(n)$, and return a $(1+\\epsilon)$-approximate nearest neighbor, for any given $\\epsilon>0$. Ignoring the step of NNS on a line, queries take $O( \\log^2 \\log n / \\epsilon^{O(d^2)})$ with high probability. Our key step is to employ a reduction of determining the nearest line to NNS among points."],"dc:identifier":["uoadl:1321064","https://pergamos.lib.uoa.gr/uoa/dl/object/1321064"],"dc:language":["English"],"dc:title":["Exploiting the structure of the data in approximate nearest neighbor search"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:38Z"}