Back to search

National and Kapodistrian University of Athens

Algorithms, Hashing, Parallel processing, and the Nearest Neighbor problem in High Dimensions

Abstract

dc:description

Το πρόβλημα απόφασης του Κοντινού Γείτονα (Νear neighbor) μελετάται είτε αυτόνομα είτε διότι σε αυτό ανάγεται αποδοτικά το πρόβλημα βελτιστοποίησης του Πλησιέστερου Γείτονα (Nearest neighbor). Λόγω της κατάρας της διαστασιμότητας, οι παραδοσιακοί αλγόριθμοι δεν μπορούν να αποδώσουν σε υψηλές διαστάσεις, πράγμα που έκανε την επιστημονική κοινότητα να στραφεί προς προσεγγιστικούς αλγορίθμους, όπου κανείς θυσιάζει ακρίβεια για ταχύτητα. Το προσεγγιστικό πρόβλημα απόφασης στις υψηλές διαστάσεις έχει κατά κύριο λόγο προσεγγιστεί με Locality Sensitive Hashing (LSH). Για πρακτικές εφαρμογές είναι σημαντικό να εξασφαλιστεί γραμμικότητα στην χρήση μνήμης. Προτείνουμε μία νέα, απλή δομή δεδομένων, η οποία χρησιμοποιεί γραμμικό χώρο και υπογραμμικό χρόνο επερώτησης ως προς το πλήθος δεδομένων, για κάθε προσέγγιση c > 1, με γραμμική εξάρτηση στη διάσταση: με δεδομένη μία οικογένεια LSH συναρτήσεων για κάποιο μετρικό χώρο, αναθέτουμε τυχαία ένα δυφίο σε κάθε κουβά που ορίζεται από κάθε συνάρτηση, προσδιορίζοντας έτσι μία προβολή των σημείων στις κορυφές ενός 0/1 υπερκύβου, διάστασης lg n, όπου n το πλήθος των σημείων. Ο αλγόριθμος αναζήτησης προβάλλει την επερώτηση σε μια κορυφή και έπειτα ελέγχει τα σημεία που αντιστιχούν σε κοντινές κορυφές στον υπερκύβο. Ο αλγόριθμος μας μπορεί να διασπαστεί σε μικρότερους υποαλγορίθμους (υποπροβλήματα). Εξετάζουμε το καθένα ενδελεχώς και προσπαθούμε να βελτιστοποιήσουμε εκείνα που εκτελούνται αρκετά συχνά ώστε να επηρεάζουν τη συνολική απόδοση του αλγορίθμου, προσέχοντας παράλληλα να μην πέσουμε θύμα της πρόωρης βελτιστοποίησης. Για την ακρίβεια, εξετάζουμε αναδρομικές και επαναληπτικές προσεγγίσεις για το ίδιο υποπρόβλημα και τις συγκρίνουμε, τόσο θεωρητικά, όσο και πρακτικά. Ο αλγόριθμος μας επιτρέπει την εκτενή χρήση παραλληλίας. Τα δεδομένα στα οποία εστιάζουμε είναι αρκετά μεγάλα για να επιτρέψουν στη παραλληλία να δώσει μία σημαντική επιτάχυνση στο χρόνο εκτέλεσης. Ο κατακερματισμός είναι στη καρδιά της υλοποίησης μας, πράγμα που μας κάνει να τον εξετάζουμε προσεχτικά. Για την ακρίβεια, εξετάζουμε μια πληθώρα προσεγγίσεων για το πώς θα αναπαραστίσουμε τα δεδομένα και τον τύπο τους, τις οποίες και συγκρίνουμε πειραματικά, σε συνδυασμό με δικές μας υλοποιήσεις διάφορων συναρτήσεων ή υλοποιήσεων της πρότυπης βιβλιοθήκης της C++. Παρά τη μεγάλη προσπάθεια για επίτευξη καλύτερης απόδοσης, ο κώδικας μας έχει διατηρήσει την αναγνωσιμότητα του, το οποίο συνάδει με τη δημοτικότητα που έχει η υλοποίηση μας στο GitHub. Αξίζει να σημειωθεί πως η υλοποίηση μας αποτελείται από μόνο 716 γραμμές κώδικα. Αναφέρουμε ένα σύνολο πειραμάτων σε συνθετικά και πραγματικά δεδομένα, διάστασης μέχρι 1024 και n < 10^6. Το λογισμικό μας είναι ταχύτερο από την γραμμική μέθοδο κατά αρκετές τάξεις μεγέθους. Επίσης το συγκρίνουμε με τη τελευταίας τεχνολογίας βιβλιοθήκη FALCONN που βασίζεται στο LSH: ο αλγόριθμος και η υλοποίηση μας είναι σημαντικά απλούστεροι, ενώ η απόδοση του λογισμικού μας είναι συγκρίσιμη, όσον αναφορά τον χρόνο επερώτησης και την κατανάλωση μνήμης.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Σαμαράς Γεώργιος
  • Samaras Georgios

Subjects

dc:subject × 2

Rights

Language dc:language
Ελληνικά, English, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:1331181

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
citation

Σαμαράς Γεώργιος; Samaras Georgios. Algorithms, Hashing, Parallel processing, and the Nearest Neighbor problem in High Dimensions. 2017. https://pergamos.lib.uoa.gr/uoa/dl/object/1331181