Μπότσιος Ιωάννης 1115202200111
Έξαρχος Θεόδωρος 1115202200045

Οδηγίες Χρήσης

Για να γινει compile το προγραμμα, απλά γράψτε στο terminal την εντολη make. Αν θελετε να διαγραψετε τα αρχεια που δημιουργηθηκαν, καντε make clean.

Για να το εκτελεσετε, τρεξτε "./search" βαζοντας στο command line τα παρακατω υποχρεωτικα ορισματα:

• -d input_file
• -q query_file
• -o output_file
• -type mnist ή sift
• -lsh ή -hypercube ή -ivfflat ή -ivfpq

Προαιρετικα μπορειτε να προσθεσετε οποια ορισματα χρειαζεστε απο τα παρακατω (αν δεν τα δωσετε θα εχουν τις default τιμες):

• -seed (φυτρο)
• -k (πληθος h_i συναρτησεων στο LSH για τον υπολογισμο του g)
• -L (πληθος πινακων κατακερματισμου του LSH)
• -w (μηκος του κελιου επι της ευθειας προβολης για LSH και Hypercube)
• -N (πληθος πλησιεστερων γειτονων που θα βρεθουν)
• -R (ακτινα αναζητησης για range search)
• -kproj (η διάσταση στην οποία προβάλλονται τα σημεία του Hypercube)
• -probes (πληθος κορυφων του Hypercube που θα ελεγχθουν)
• -M (μεγιστο πληθος υποψηφιων σημειων που θα ελεγχθουν στο Hypercube ή αριθμος υποδιανυσματων για τον κβαντισμο γινομενου στο IVFPQ)
• -kclusters (πληθος clusters που θα δημιουργηθουν στους IVFFlat και IVFPQ)
• -nprobe (πληθος πλησιεστερων clusters που θα ελεγχθουν κατα την αναζητηση στους IVFFlat και IVFPQ)
• -nbits (2^nbits == πληθος sub-centroids σε καθε υποχωρο στο IVFPQ)

Τα αποτελεσματα της εκτελεσης θα εκτυπωθουν στο output_file αρχειο

Συνοψη Καθε Αρχειου

• main.cpp: Καλεί τις απαραιτητες συναρτησεις για να διαβασει και να αποθηκευσει τα command line arguments, καθως και τα στοιχεια απο τα query_file και input_file αναλογα με το αν ειναι τυπου SIFT ή MNIST. Μετά, καλεί την call_dispatcher για να ξεκινησει η διαδικασια του αλγοριθμου που επιλεχθηκε.

Φακελος "Common"

• Args.hpp: Περιέχει την δομη Args, η οποια αποθηκευει ολα τα δεδομενα που διαβαζονται απο το command line και ειναι απαραιτητα για την εκτελεση των αλγοριθμων.

• Brute_force.hpp: Περιεχει την συναρτηση brute_force, η οποια βρισκει ολες τις αποστασεις ενος στοιχειου απο ολα τα υπολοιπα στοιχεια και τις επιστρεφει ταξινομημενες

• Call_handler.hpp: Περιεχει την συναρτηση call_dispatcher, η οποια, αφου καθορισει ποιον αλγοριθμο θελουμε να τρεξουμε, ειναι υπευθυνη για την αρχικοποιηση των hashtables/inverted_lists του αλγοριθμου και καλει την searcher που θα κανει την αναζητηση

• HashTable.hpp: Περιεχει την δομη HashTable και την δομη Entry που ειναι ο τυπος δεδομενων που αποθηκευει το hashtable

• LoadData.hpp: Περιεχει την δομη DataImages που αποθηκευει πληροφοριες για τα δεδομενα που διαβαζουμε απο το input/query file.

• Search_dispatcher.hpp: Περιεχει την συναρτηση searcher, η οποια εκτελει την knn αναζητηση (προαιρετικα και την range) για ολα τα στοιχεια του query_file και υπολογιζει στατιστικα οπως το Recall, QPS, etc. και στην συνεχεια τα τυπωνει στο output_file

• Vector_distance.hpp: Περιεχει την συναρτηση lp_dist, η οποια υπολογιζει και επιστρεφει την αποσταση μεταξυ δυο στοιχειων.

Φακελος "Includes"

• Fhash.hpp: Περιεχει τον ορισμο της κλάσης Fhash, η οποια ειναι η συναρτηση f_i του hypercube.

• Hhash.hpp: Περιεχει τον ορισμο της κλάσης Hhash, η οποια ειναι η συναρτηση h_i του LSH και του hypercube.

• Hypercube.hpp: Περιεχει την κλαση Hypercube, η οποια εχει μεσα το hashtable, καθως και τις απαραιτητες συναρτησεις για αρχικοποιηση και αναζητηση. Περιεχει επισης την δομη F_Function, η οποια κραταει ολες τις συναρτησεις f_i και h_i που δημιουργηθηκαν, ωστε να χρησιμοποιηθουν αργοτερα για τον υπολογισμο της τιμης hash ενος στοιχειου.

• IVFFlat.hpp: Περιεχει την κλαση IVFFlat, η οποια εχει μεσα τα centroids και τα inverted_lists (table) τους, καθως και τις απαραιτητες συναρτησεις για αρχικοποιηση και αναζητηση.

• IVFPQ.hpp: Περιεχει την κλαση IVFPQ, η οποια εχει μεσα τα centroids και τα inverted_lists (lists) τους, τα sub-centroids των υποχώρων, καθως και τις απαραιτητες συναρτησεις για αρχικοποιηση και αναζητηση. Μεσα στην κλαση υπαρχει επισης και ο ορισμος μιας νεας δομης entry, η PQEntry, που ειναι ο τυπος δεδομενων που αποθηκευεται μεσα στα inverted_lists, και περιεχει μονο την κωδικοποιηση των στοιχειων αντι για ολα τους τα δεδομενα.

• LSH.hpp: Περιεχει την κλαση LSH, η οποια εχει μεσα τον πινακα με τα hashtable g, καθως και τις απαραιτητες συναρτησεις για αρχικοποιηση και αναζητηση. Περιεχει επισης την δομη GFunction, η οποια κραταει ολα τα r_i και h_i που δημιουργηθηκαν, ωστε να χρησιμοποιηθουν αργοτερα για τον υπολογισμο της τιμης hash ενος στοιχειου.

Φακελος "Modules"

• Args.cpp: Περιεχει την υλοποιηση της συναρτησης load_args, η οποια διαβαζει ολα τα δεδομενα απο το command line και τα αποθηκευει στην δομη Args, την οποια και επιστρεφει. Ελεχει πως εχουν δοθει ολα τα απαραιτητα ορισματα (-d input_file | -q query_file | -o output_file | -type mnist ή sift | -<algorithm_type>) επειδη αυτα χρειαζονται για την σωστη λειτουργια του προγραμματος. Τα υπολοιπα αν δεν εχουν δοθει, παιρνουν τις default τιμες τους.

• Fhash.cpp: Εχει τον constructor του Fhash που απλα κανει assign την τιμη του seed, και κανει overload τις παρενθεσεις "()" ωστε να επιστρεφουν για την τιμη με την οποια κληθηκαν εντελως τυχαια την τιμη 0 ή 1. Αν η τιμη ηταν ηδη υπολογισμενη νωριτερα τοτε εχει φυλαχθει απο την πρωτη κληση το αποτελεσμα (0 ή 1) και επιστρεφεται αμεσως, χωρις να γινεται ξανα randomize.

• Hhash.cpp: Περιεχει τον constructor της κλασης Hhash, ο οποιος αρχικοποιει ολα της τα δεδομενα και δημιουργει το τυχαιο διανυσμα v και το τυχαιο t που χρειαζονται για τον υπολογισμο της h(p). Γινεται επισης overload στις παρενθεσεις "()" ωστε να επιστρεφουν την τιμη της h(p) για το p με το οποιο κληθηκαν.

• Hypercube.cpp: Περιεχει τις υλοποιησεις για την F_Function και τις συναρτησεις του Hypercube. Ξεκινωντας με την F_Function, εχουμε τον constructor ο οποιος δημιουργει ολες τις f_i και h_i και τις αποθηκευει. Μετα κανουμε overload τις παρενθεσεις "()" για να υπολογιζουν και να επιστρεφουν την ακολουθια των bits που αντιστοιχει στο στοιχειο που δοθηκε ως ορισμα. Εχουμε επισης μια βοηθητικη συναρτηση bits_to_int η οποια μετατρεπει αυτην την ακολουθια σε αριθμο. Τωρα, για το hypercube, εχουμε τον constructor που αρχικοποιει ολα του τα δεδομενα, την build που ειναι υπευθυνη για την σωστη δημιουργια και αρχικοποιηση του hashtable, την insert_object που βαζει καθε entry στο σωστο bucket και τελος τις query_knn και query_range που εκτελουν αναζητηση. Και οι δυο ξεκινουν βρισκοντας την τιμη hash του query στοιχειου και στην συνεχεια ψαχνουν μεσα στο bucket του και στην συνεχεια ψαχνουν στα γειτονικα buckets αυξανοντας το hamming_distance. Η αναζητηση θα σταματησει οταν εχουμε ελεγξει M στοιχεια ή probes buckets.

• IVFFlat.cpp: Περιεχει τις υλοποιησεις για τις συναρτησεις του IVFFlat. Αρχικα εχουμε τον constructor που αρχικοποιει ολα του τα δεδομενα. Στην συνεχεια, η build ειναι υπευθυνη για την σωστη δημιουργια και αρχικοποιηση των inverted_lists (table). Πρωτα, χρησιμοποιώντας την βοηθητικη συναρτηση kmeans_init κανει τον αλγοριθμο kmeans++ initialization για μια αρχικη εκτιμηση των centroids, και μετα κανει τον αλγοριθμο του lloyd για να βρει τα τελικα centroids που θα χρησιμοποιησουμε. Στο τελος καλει την insert_object που βαζει καθε entry στο σωστο inverted_list. Επειτα εχουμε τις query_knn και query_range που εκτελουν αναζητηση. Και οι δυο ξεκινουν βρισκοντας τα 'nprobe' κοντινοτερα centroids και μετα ψαχνουν μεσα στα αντιστοιχα inverted_lists τους. Η αναζητηση θα σταματησει οταν εχουμε ελεγξει εκεινα τα inverted_lists.

• IVFPQ.cpp: Περιεχει τις υλοποιησεις για τις συναρτησεις του IVFPQ. Αρχικα εχουμε τον constructor που αρχικοποιει ολα του τα δεδομενα. Στην συνεχεια, η build ειναι υπευθυνη για την σωστη δημιουργια και αρχικοποιηση των inverted_lists (lists). Πρωτα, χρησιμοποιώντας την βοηθητικη συναρτηση kmeans_init κανει τον αλγοριθμο kmeans++ initialization για μια αρχικη εκτιμηση των centroids, και μετα κανει τον αλγοριθμο του lloyd για να βρει τα τελικα centroids που θα χρησιμοποιησουμε. Αφου τα βρει, καλει την build_subcentroids, η οποια υπολογιζει τα residuals ολων των σημειων, τα χωριζει σε Μ κομματια (υποχωρους) και δημιουργει τα sub-centroids για καθε υποχωρο. Η διαδικασια δημιουργιας των sub-centroids ειναι ιδια με τα κανονικα centroids (kmeans++ init -> lloyd). Στο τελος καλει την insert_object που υπολογιζει το code καθε στοιχειου και το βαζει στο σωστο inverted_list. Επειτα εχουμε τις query_knn και query_range που εκτελουν αναζητηση. Και οι δυο ξεκινουν βρισκοντας τα 'nprobe' κοντινοτερα centroids και μετα ψαχνουν μεσα στα αντιστοιχα inverted_lists τους, υπολογιζοντας approximate αποστασεις με την χρηση των codes. Η αναζητηση θα σταματησει οταν εχουμε ελεγξει εκεινα τα inverted_lists.

• LoadData.cpp: Περιεχει τις υλοποιησεις των συναρτησεων load_mnist και load_sift, η οποιες διαβαζουν ολα τα δεδομενα απο το input_file και τα αποθηκευουν στην δομη DataImages, την οποια και επιστρεφουν.

• LSH.cpp: Περιεχει τις υλοποιησεις για την GFunction και τις συναρτησεις του LSH. Ξεκινωντας με την GFunction, εχουμε τον constructor ο οποιος δημιουργει ολες τις h_i και r_i και τις αποθηκευει. Μετα έχουμε τις συναρτησεις ID και gfunc που υπολογιζουν τις τιμες ID(p) και g(p) που αντιστοιχουν στο στοιχειο που δοθηκε ως ορισμα. Τωρα, για το LSH, εχουμε τον constructor που αρχικοποιει ολα του τα δεδομενα, την build που ειναι υπευθυνη για την σωστη δημιουργια και αρχικοποιηση του hashtable, την insert_object που βαζει καθε entry στο σωστο bucket και τελος τις query_knn και query_range που εκτελουν αναζητηση. Και οι δυο βρισκουν τις τιμες hash του query στοιχειου για καθε ενα απο τα L hashtables και στην συνεχεια ψαχνουν μεσα στο αντιστοιχο bucket σε καθε hashtable. Η αναζητηση θα σταματησει οταν εχουμε ελεγξει εκεινα τα buckets.

Φακελος "tests/BF_results"

• BFloader.hpp: Περιεχει συναρτησεις που επιστρεφουν τα προϋπολογισμένα αποτελεσματα απο την εκτέλεση brute_force

• BFloader.cpp: Πρόγραμμα που τρέξαμε μία φορα για να πάρουμε και να αποθηκευσουμε όλες τις τιμές του brute_force, ώστε να μπορούμε να κάνουμε πειραματικές εκτελέσεις πιο γρήγορα

• Search_dispatcher.hpp: Ιδια με την Search_dispatcher που βρίσκεται στον φακελο "Common", απλά αντι να εκτελει τον αλγοριθμο brute_force, χρησιμοποιει τα προϋπολογισμένα αποτελεσματα.

Φακελος "tests/Silhouette"

• Silhouette.hpp: Περιεχει την υλοποιηση της compute_silhouette, η οποια υπολογιζει την τιμη silhouette καθε στοιχειου και επιστρεφει την μεση τιμη τους.