Back to search

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

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

Κωνσταντινάκης-Κάρμης Αλέξανδρος. Implementing approximate voronoi diagrams for approximate nearest neighbor searching. 2012. https://pergamos.lib.uoa.gr/uoa/dl/object/1321133