Back to search

National and Kapodistrian University of Athens

Exploiting the structure of the data in approximate nearest neighbor search

Abstract

dc:description

Η εύρεση του πλησιέστερου γείτονα είναι ένα καίριο πρόβλημα με πολλές σημαντικές εφαρμογές. Για να επιταχύνουμε το χρόνο εύρεσης του κοντινότερου γείτονα εκμεταλλευόμαστε το ότι πολλές φορές τα δεδομένα ακολουθούν μη τυχαία πρότυπα. Συγκεκριμένα, υποθέτουμε ότι τα σημεία που δεχόμαστε ως είσοδο βρίσκονται πάνω σε \logt n άγνωστες ευθείες σε κάποιο χώρο σταθερής διάστασης $d$, όπου $n$ είναι ο αριθμός των σημείων και $t$ είναι μια σταθερά. Οι ευθείες είναι κατανεμημένες ομοιόμορφα σε μια περιορισμένη μπάλα και τα σημεία είναι ομοιόμορφα κατανεμημένα πάνω σε κάθε ευθεία. Δεχόμαστε ότι κάθε ευθεία θα έχει από \Omega (\logt n) έως $O(n)$ σημεία. Η εύρεση ενός κατά προσέγγιση πλησιέστερου γείτονα χρειάζεται O( \log \log n / εO(d2)) αναμενόμενο χρόνο, ο οποίος είναι εκθετικά μικρότερος από το χρόνο που θα χρειαζόταν αν δεν εκμεταλλευόμασταν τη δομή των σημείων. Για κάθε δοσμένο ε>0 ο αλγόριθμος επιστρέφει ένα (1+ε)-κατά προσέγγιση πλησιέστερο γείτονα, χρησιμοποιώντας βέλτιστο χώρο $O(n)$. Αν αγνοήσουμε την εύρεση του πλησιέστερου γείτονα ανάμεσα σε σημεία που βρίσκονται πάνω σε μία ευθεία, ο αλγόριθμος χρειάζεται χρόνο O( \log2 \log n / εO(d2)) με μεγάλη πιθανότητα. Το βασικό βήμα στον αλγόριθμο είναι η εφαρμογή μιάς αναγωγής από την εύρεση κοντινότερης ευθείας, στην εύρεση πλησιέστερου σημείου.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Θάνος Φίλης Αριστοτέλης Εμμανουήλ

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:1321064

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

Θάνος Φίλης Αριστοτέλης Εμμανουήλ. Exploiting the structure of the data in approximate nearest neighbor search. 2012. https://pergamos.lib.uoa.gr/uoa/dl/object/1321064