{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1321133"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1321133","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Implementing approximate voronoi diagrams for approximate nearest neighbor searching","abstract":"Η αναζήτηση πλησιέστερου γείτονα είναι ένα θεμελιώδες πρόβλημα στην Επιστήμη των Υπολογιστών. Ένα άπο τα κύρια θεωρητικά ζητήματα ειναι η εξισορρόπηση του χρόνου που απαιτείται για να απαντήσει η δομή σε ερωτήματα και η χωρική πολυπλοκότητά της: η πρόσφατη μελέτη στο Προσεγγιστικό Διάγραμμα Voronoi(AVD) οδηγεί σε βέλτιστο χρόνο ερωτήματος δίνοντας τη δυνατότητα στο χρήστη να επιλέξει μεταξύ λιγότερου χώρου ή γρηγορότερου χρόνου ερωτήματος. Η βασική ιδέα είναι να χωριστεί ο χώρος γύρω από τα σημεία εισόδου και να γίνει χρήση κουτιών διαφόρων μεγεθών για να καλυφθεί. Σε κάθε κουτί αποδίδουμε ένα υποσύνολο των σημείων εισόδου, τα οποία ειναι υποψήφιοι ε-προσεγγιστικοί πλησιέστεροι γείτονες για κάθε σημείο σε αυτό το κουτί. Η υλοποίηση του AVD είναι ένα δύσκολο έργο που δεν έχει υλοποιηθεί ώστε να δέχεται τη διάσταση d των σημείων ως είσοδο. Προσφέρουμε μια αποτελεσματική, παράλληλη εφαρμογή που κατασκευάζει το AVD, προσφέροντας ιδέες τροποποίησης του αλγορίθμου έτσι ώστε να καθίσταται η κατασκευή εφικτή. Στα πειραματικά μας αποτελέσματα δείχνουμε ότι τα η δομή μασ απαντά πιο γρήγορα και με μεγαλύτερη ακρίβεια σε σχέση με την καλυτερη υλοποίηση KD tree σε μικρές διαστάσεις.","abstract_html":"Η αναζήτηση πλησιέστερου γείτονα είναι ένα θεμελιώδες πρόβλημα στην Επιστήμη των Υπολογιστών. Ένα άπο τα κύρια θεωρητικά ζητήματα ειναι η εξισορρόπηση του χρόνου που απαιτείται για να απαντήσει η δομή σε ερωτήματα και η χωρική πολυπλοκότητά της: η πρόσφατη μελέτη στο Προσεγγιστικό Διάγραμμα Voronoi(AVD) οδηγεί σε βέλτιστο χρόνο ερωτήματος δίνοντας τη δυνατότητα στο χρήστη να επιλέξει μεταξύ λιγότερου χώρου ή γρηγορότερου χρόνου ερωτήματος. Η βασική ιδέα είναι να χωριστεί ο χώρος γύρω από τα σημεία εισόδου και να γίνει χρήση κουτιών διαφόρων μεγεθών για να καλυφθεί. Σε κάθε κουτί αποδίδουμε ένα υποσύνολο των σημείων εισόδου, τα οποία ειναι υποψήφιοι ε-προσεγγιστικοί πλησιέστεροι γείτονες για κάθε σημείο σε αυτό το κουτί. Η υλοποίηση του AVD είναι ένα δύσκολο έργο που δεν έχει υλοποιηθεί ώστε να δέχεται τη διάσταση d των σημείων ως είσοδο. Προσφέρουμε μια αποτελεσματική, παράλληλη εφαρμογή που κατασκευάζει το AVD, προσφέροντας ιδέες τροποποίησης του αλγορίθμου έτσι ώστε να καθίσταται η κατασκευή εφικτή. Στα πειραματικά μας αποτελέσματα δείχνουμε ότι τα η δομή μασ απαντά πιο γρήγορα και με μεγαλύτερη ακρίβεια σε σχέση με την καλυτερη υλοποίηση KD tree σε μικρές διαστάσεις.","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":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:1321133"],"render_values":[{"text":"uoadl:1321133","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321133","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321133","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%3A1321133","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:1321133","https://pergamos.lib.uoa.gr/uoa/dl/object/1321133"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η αναζήτηση πλησιέστερου γείτονα είναι ένα θεμελιώδες πρόβλημα στην Επιστήμη των Υπολογιστών. Ένα άπο τα κύρια θεωρητικά ζητήματα ειναι η εξισορρόπηση του χρόνου που απαιτείται για να απαντήσει η δομή σε ερωτήματα και η χωρική πολυπλοκότητά της: η πρόσφατη μελέτη στο Προσεγγιστικό Διάγραμμα Voronoi(AVD) οδηγεί σε βέλτιστο χρόνο ερωτήματος δίνοντας τη δυνατότητα στο χρήστη να επιλέξει μεταξύ λιγότερου χώρου ή γρηγορότερου χρόνου ερωτήματος. Η βασική ιδέα είναι να χωριστεί ο χώρος γύρω από τα σημεία εισόδου και να γίνει χρήση κουτιών διαφόρων μεγεθών για να καλυφθεί. Σε κάθε κουτί αποδίδουμε ένα υποσύνολο των σημείων εισόδου, τα οποία ειναι υποψήφιοι ε-προσεγγιστικοί πλησιέστεροι γείτονες για κάθε σημείο σε αυτό το κουτί. Η υλοποίηση του AVD είναι ένα δύσκολο έργο που δεν έχει υλοποιηθεί ώστε να δέχεται τη διάσταση d των σημείων ως είσοδο. Προσφέρουμε μια αποτελεσματική, παράλληλη εφαρμογή που κατασκευάζει το AVD, προσφέροντας ιδέες τροποποίησης του αλγορίθμου έτσι ώστε να καθίσταται η κατασκευή εφικτή. Στα πειραματικά μας αποτελέσματα δείχνουμε ότι τα η δομή μασ απαντά πιο γρήγορα και με μεγαλύτερη ακρίβεια σε σχέση με την καλυτερη υλοποίηση KD tree σε μικρές διαστάσεις.","Nearest neighbor searching is a fundamental problem in computer science. One of the main theoretical issues is to balance query time and space complexity: the recent Approximate Voronoi Diagram (AVD) leads to optimal query time while making the tradeoff with space usage explicit. The key idea is to cluster the space around the input points and use boxes of varying size to cover it. Each cluster is assigned a subset of the points, which are candidate ε-approximate nearest neighbors to every point in that cluster. However, the implementation of AVD has been a daunting task and was never completed. We offer the first, efficient, parallel implementation of the AVD which accepts dimension as input and introduce certain ideas and modifications that make the construction feasible. In our experimental results, we show that our data structure is much faster and more accurate than a standard KD-tree in low dimensions."]},{"key":"dc:title","label":"Title","values":["Implementing approximate voronoi diagrams for approximate nearest neighbor searching"]}]}],"canonical_facts":{"dc:creator":["Κωνσταντινάκης-Κάρμης Αλέξανδρος"],"dc:date":["2012"],"dc:description":["Η αναζήτηση πλησιέστερου γείτονα είναι ένα θεμελιώδες πρόβλημα στην Επιστήμη των Υπολογιστών. Ένα άπο τα κύρια θεωρητικά ζητήματα ειναι η εξισορρόπηση του χρόνου που απαιτείται για να απαντήσει η δομή σε ερωτήματα και η χωρική πολυπλοκότητά της: η πρόσφατη μελέτη στο Προσεγγιστικό Διάγραμμα Voronoi(AVD) οδηγεί σε βέλτιστο χρόνο ερωτήματος δίνοντας τη δυνατότητα στο χρήστη να επιλέξει μεταξύ λιγότερου χώρου ή γρηγορότερου χρόνου ερωτήματος. Η βασική ιδέα είναι να χωριστεί ο χώρος γύρω από τα σημεία εισόδου και να γίνει χρήση κουτιών διαφόρων μεγεθών για να καλυφθεί. Σε κάθε κουτί αποδίδουμε ένα υποσύνολο των σημείων εισόδου, τα οποία ειναι υποψήφιοι ε-προσεγγιστικοί πλησιέστεροι γείτονες για κάθε σημείο σε αυτό το κουτί. Η υλοποίηση του AVD είναι ένα δύσκολο έργο που δεν έχει υλοποιηθεί ώστε να δέχεται τη διάσταση d των σημείων ως είσοδο. Προσφέρουμε μια αποτελεσματική, παράλληλη εφαρμογή που κατασκευάζει το AVD, προσφέροντας ιδέες τροποποίησης του αλγορίθμου έτσι ώστε να καθίσταται η κατασκευή εφικτή. Στα πειραματικά μας αποτελέσματα δείχνουμε ότι τα η δομή μασ απαντά πιο γρήγορα και με μεγαλύτερη ακρίβεια σε σχέση με την καλυτερη υλοποίηση KD tree σε μικρές διαστάσεις.","Nearest neighbor searching is a fundamental problem in computer science. One of the main theoretical issues is to balance query time and space complexity: the recent Approximate Voronoi Diagram (AVD) leads to optimal query time while making the tradeoff with space usage explicit. The key idea is to cluster the space around the input points and use boxes of varying size to cover it. Each cluster is assigned a subset of the points, which are candidate ε-approximate nearest neighbors to every point in that cluster. However, the implementation of AVD has been a daunting task and was never completed. We offer the first, efficient, parallel implementation of the AVD which accepts dimension as input and introduce certain ideas and modifications that make the construction feasible. In our experimental results, we show that our data structure is much faster and more accurate than a standard KD-tree in low dimensions."],"dc:identifier":["uoadl:1321133","https://pergamos.lib.uoa.gr/uoa/dl/object/1321133"],"dc:language":["English"],"dc:title":["Implementing approximate voronoi diagrams for approximate nearest neighbor searching"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:38Z"}