National and Kapodistrian University of Athens
Implementing approximate voronoi diagrams for approximate nearest neighbor searching
Abstract
dc:descriptionΗ αναζήτηση πλησιέστερου γείτονα είναι ένα θεμελιώδες πρόβλημα στην Επιστήμη των Υπολογιστών. Ένα άπο τα κύρια θεωρητικά ζητήματα ειναι η εξισορρόπηση του χρόνου που απαιτείται για να απαντήσει η δομή σε ερωτήματα και η χωρική πολυπλοκότητά της: η πρόσφατη μελέτη στο Προσεγγιστικό Διάγραμμα Voronoi(AVD) οδηγεί σε βέλτιστο χρόνο ερωτήματος δίνοντας τη δυνατότητα στο χρήστη να επιλέξει μεταξύ λιγότερου χώρου ή γρηγορότερου χρόνου ερωτήματος. Η βασική ιδέα είναι να χωριστεί ο χώρος γύρω από τα σημεία εισόδου και να γίνει χρήση κουτιών διαφόρων μεγεθών για να καλυφθεί. Σε κάθε κουτί αποδίδουμε ένα υποσύνολο των σημείων εισόδου, τα οποία ειναι υποψήφιοι ε-προσεγγιστικοί πλησιέστεροι γείτονες για κάθε σημείο σε αυτό το κουτί. Η υλοποίηση του AVD είναι ένα δύσκολο έργο που δεν έχει υλοποιηθεί ώστε να δέχεται τη διάσταση d των σημείων ως είσοδο. Προσφέρουμε μια αποτελεσματική, παράλληλη εφαρμογή που κατασκευάζει το AVD, προσφέροντας ιδέες τροποποίησης του αλγορίθμου έτσι ώστε να καθίσταται η κατασκευή εφικτή. Στα πειραματικά μας αποτελέσματα δείχνουμε ότι τα η δομή μασ απαντά πιο γρήγορα και με μεγαλύτερη ακρίβεια σε σχέση με την καλυτερη υλοποίηση KD tree σε μικρές διαστάσεις.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Κωνσταντινάκης-Κάρμης Αλέξανδρος
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1321133