{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1331181"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1331181","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Algorithms, Hashing, Parallel processing, and the Nearest Neighbor problem in High Dimensions","abstract":"Το πρόβλημα απόφασης του Κοντινού Γείτονα (Ν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: ο αλγόριθμος και η υλοποίηση μας είναι σημαντικά απλούστεροι, ενώ η απόδοση του λογισμικού μας είναι συγκρίσιμη, όσον αναφορά τον χρόνο επερώτησης και την κατανάλωση μνήμης.","abstract_html":"Το πρόβλημα απόφασης του Κοντινού Γείτονα (Νear neighbor) μελετάται είτε αυτόνομα είτε διότι σε αυτό ανάγεται αποδοτικά το πρόβλημα βελτιστοποίησης του Πλησιέστερου Γείτονα (Nearest neighbor). Λόγω της κατάρας της διαστασιμότητας, οι παραδοσιακοί αλγόριθμοι δεν μπορούν να αποδώσουν σε υψηλές διαστάσεις, πράγμα που έκανε την επιστημονική κοινότητα να στραφεί προς προσεγγιστικούς αλγορίθμους, όπου κανείς θυσιάζει ακρίβεια για ταχύτητα. Το προσεγγιστικό πρόβλημα απόφασης στις υψηλές διαστάσεις έχει κατά κύριο λόγο προσεγγιστεί με Locality Sensitive Hashing (LSH). Για πρακτικές εφαρμογές είναι σημαντικό να εξασφαλιστεί γραμμικότητα στην χρήση μνήμης. Προτείνουμε μία νέα, απλή δομή δεδομένων, η οποία χρησιμοποιεί γραμμικό χώρο και υπογραμμικό χρόνο επερώτησης ως προς το πλήθος δεδομένων, για κάθε προσέγγιση c &gt; 1, με γραμμική εξάρτηση στη διάσταση: με δεδομένη μία οικογένεια LSH συναρτήσεων για κάποιο μετρικό χώρο, αναθέτουμε τυχαία ένα δυφίο σε κάθε κουβά που ορίζεται από κάθε συνάρτηση, προσδιορίζοντας έτσι μία προβολή των σημείων στις κορυφές ενός 0/1 υπερκύβου, διάστασης lg n, όπου n το πλήθος των σημείων. Ο αλγόριθμος αναζήτησης προβάλλει την επερώτηση σε μια κορυφή και έπειτα ελέγχει τα σημεία που αντιστιχούν σε κοντινές κορυφές στον υπερκύβο. Ο αλγόριθμος μας μπορεί να διασπαστεί σε μικρότερους υποαλγορίθμους (υποπροβλήματα). Εξετάζουμε το καθένα ενδελεχώς και προσπαθούμε να βελτιστοποιήσουμε εκείνα που εκτελούνται αρκετά συχνά ώστε να επηρεάζουν τη συνολική απόδοση του αλγορίθμου, προσέχοντας παράλληλα να μην πέσουμε θύμα της πρόωρης βελτιστοποίησης. Για την ακρίβεια, εξετάζουμε αναδρομικές και επαναληπτικές προσεγγίσεις για το ίδιο υποπρόβλημα και τις συγκρίνουμε, τόσο θεωρητικά, όσο και πρακτικά. Ο αλγόριθμος μας επιτρέπει την εκτενή χρήση παραλληλίας. Τα δεδομένα στα οποία εστιάζουμε είναι αρκετά μεγάλα για να επιτρέψουν στη παραλληλία να δώσει μία σημαντική επιτάχυνση στο χρόνο εκτέλεσης. Ο κατακερματισμός είναι στη καρδιά της υλοποίησης μας, πράγμα που μας κάνει να τον εξετάζουμε προσεχτικά. Για την ακρίβεια, εξετάζουμε μια πληθώρα προσεγγίσεων για το πώς θα αναπαραστίσουμε τα δεδομένα και τον τύπο τους, τις οποίες και συγκρίνουμε πειραματικά, σε συνδυασμό με δικές μας υλοποιήσεις διάφορων συναρτήσεων ή υλοποιήσεων της πρότυπης βιβλιοθήκης της C++. Παρά τη μεγάλη προσπάθεια για επίτευξη καλύτερης απόδοσης, ο κώδικας μας έχει διατηρήσει την αναγνωσιμότητα του, το οποίο συνάδει με τη δημοτικότητα που έχει η υλοποίηση μας στο GitHub. Αξίζει να σημειωθεί πως η υλοποίηση μας αποτελείται από μόνο 716 γραμμές κώδικα. Αναφέρουμε ένα σύνολο πειραμάτων σε συνθετικά και πραγματικά δεδομένα, διάστασης μέχρι 1024 και n &lt; 10^6. Το λογισμικό μας είναι ταχύτερο από την γραμμική μέθοδο κατά αρκετές τάξεις μεγέθους. Επίσης το συγκρίνουμε με τη τελευταίας τεχνολογίας βιβλιοθήκη FALCONN που βασίζεται στο LSH: ο αλγόριθμος και η υλοποίηση μας είναι σημαντικά απλούστεροι, ενώ η απόδοση του λογισμικού μας είναι συγκρίσιμη, όσον αναφορά τον χρόνο επερώτησης και την κατανάλωση μνήμης.","abstract_has_math":false,"creators":["Σαμαράς Γεώργιος","Samaras Georgios"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017","date_published":"2017","updated_at":"2026-11-19T05:27:39Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["Ελληνικά","English","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1331181"],"render_values":[{"text":"uoadl:1331181","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1331181","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1331181","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%3A1331181","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Σαμαράς Γεώργιος","Samaras Georgios"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","English","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1331181","https://pergamos.lib.uoa.gr/uoa/dl/object/1331181"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Το πρόβλημα απόφασης του Κοντινού Γείτονα (Ν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: ο αλγόριθμος και η υλοποίηση μας είναι σημαντικά απλούστεροι, ενώ η απόδοση του λογισμικού μας είναι συγκρίσιμη, όσον αναφορά τον χρόνο επερώτησης και την κατανάλωση μνήμης.","Exact Near Neighbor in high dimensional spaces is a quite hard problem, because of the curse of dimensionality, where the spaces become so sparse that known algorithms in low dimensional spaces tend to be comparable with the brute force approach. For that reason, the community has focused on geometric approximate algorithms, where one trade offs accuracy for speed. Moreover, the Approximate Nearest Neighbor problem can be reduced to that problem, which strengthens the interest in Approximate Near Neighbor. The c-approximate Near Neighbor decision problem in high-dimensional spaces has been mainly addressed by Locality Sensitive Hashing (LSH). While, in practice, it is important to ensure linear space usage, most previous work in this regime focuses on the case that c exceeds 1 by a constant term. We present a new, simple data structure using linear space and sublinear query time for any c > 1: Given an LSH family of functions for some metric space, we randomly project points to vertices of the Hamming cube in dimension ≤ log n, where n is the number of input points. The search algorithm projects the query, then examines points which are assigned to nearby vertices on the cube. Our algorithm can be broken down to smaller, easier and more manageable subalgorithms (subproblems). We investigate every single subalgorithm further and try to optimize the ones that are going to execute frequently enough to affect the overall performance, while at the same avoiding becoming a victim of premature optimization. In particular, we ex- amine recursive and iterative approaches for the same subproblem and compare them, both theoretically and in practise. Due to the nature and simplicity of our algorithm, paral- lelization can be applied, both in the preprocessing stage, as well as in the query phase. The data we target are big enough to allow parallelization to give a significant boost in the execution time of our algorithm. Hashing is at the heart of our implementation, which prompts us to examine it gingerly. Namely, we examine a plethora of approaches regarding data representation and data type. We combine these approaches with custom-made simple, helper functions or func- tions provided by the standard library of C++, and compare them. Despite the huge effort in optimizing our code, we preserve its readability, which comes along with the popularity of our project in GitHub. Quite remarkable is the fact that our implementation amounts to only 716 lines of code, including the extensive documentation in every file. We report on several experiments with synthetic and real datasets in dimension ≤ 1024 and n ≤ 10^6. Our software is faster than brute force by several orders of magnitude. More- over, we compare it against the state-of-the-art LSH-based library FALCONN: our algorithm and implementation are significantly simpler, with comparable performance in terms of query time and storage for one of the LSH families used by FALCONN, whereas our code is orders of magnitude faster than brute force."]},{"key":"dc:title","label":"Title","values":["Algorithms, Hashing, Parallel processing, and the Nearest Neighbor problem in High Dimensions"]}]}],"canonical_facts":{"dc:creator":["Σαμαράς Γεώργιος","Samaras Georgios"],"dc:date":["2017"],"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: ο αλγόριθμος και η υλοποίηση μας είναι σημαντικά απλούστεροι, ενώ η απόδοση του λογισμικού μας είναι συγκρίσιμη, όσον αναφορά τον χρόνο επερώτησης και την κατανάλωση μνήμης.","Exact Near Neighbor in high dimensional spaces is a quite hard problem, because of the curse of dimensionality, where the spaces become so sparse that known algorithms in low dimensional spaces tend to be comparable with the brute force approach. For that reason, the community has focused on geometric approximate algorithms, where one trade offs accuracy for speed. Moreover, the Approximate Nearest Neighbor problem can be reduced to that problem, which strengthens the interest in Approximate Near Neighbor. The c-approximate Near Neighbor decision problem in high-dimensional spaces has been mainly addressed by Locality Sensitive Hashing (LSH). While, in practice, it is important to ensure linear space usage, most previous work in this regime focuses on the case that c exceeds 1 by a constant term. We present a new, simple data structure using linear space and sublinear query time for any c > 1: Given an LSH family of functions for some metric space, we randomly project points to vertices of the Hamming cube in dimension ≤ log n, where n is the number of input points. The search algorithm projects the query, then examines points which are assigned to nearby vertices on the cube. Our algorithm can be broken down to smaller, easier and more manageable subalgorithms (subproblems). We investigate every single subalgorithm further and try to optimize the ones that are going to execute frequently enough to affect the overall performance, while at the same avoiding becoming a victim of premature optimization. In particular, we ex- amine recursive and iterative approaches for the same subproblem and compare them, both theoretically and in practise. Due to the nature and simplicity of our algorithm, paral- lelization can be applied, both in the preprocessing stage, as well as in the query phase. The data we target are big enough to allow parallelization to give a significant boost in the execution time of our algorithm. Hashing is at the heart of our implementation, which prompts us to examine it gingerly. Namely, we examine a plethora of approaches regarding data representation and data type. We combine these approaches with custom-made simple, helper functions or func- tions provided by the standard library of C++, and compare them. Despite the huge effort in optimizing our code, we preserve its readability, which comes along with the popularity of our project in GitHub. Quite remarkable is the fact that our implementation amounts to only 716 lines of code, including the extensive documentation in every file. We report on several experiments with synthetic and real datasets in dimension ≤ 1024 and n ≤ 10^6. Our software is faster than brute force by several orders of magnitude. More- over, we compare it against the state-of-the-art LSH-based library FALCONN: our algorithm and implementation are significantly simpler, with comparable performance in terms of query time and storage for one of the LSH families used by FALCONN, whereas our code is orders of magnitude faster than brute force."],"dc:identifier":["uoadl:1331181","https://pergamos.lib.uoa.gr/uoa/dl/object/1331181"],"dc:language":["Ελληνικά","English","Greek"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Algorithms, Hashing, Parallel processing, and the Nearest Neighbor problem in High Dimensions"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:27:39Z"}