Ανάπτυξη Λογισμικού για Αλγοριθμικά Προβλήματα

Κωνσταντίνος Μερκούρης (sdi1800319)

Μάριος-Τριαντάφυλλος Καρναβάς (sdi1900232)

Περιγραφή Εργασίας

Στην εργασία υλοποιούνται οι αλγόριθμοι GNNS και Search On Graph για την επίλυση του προβλήματος Aproximate k Nearest Neighbours (AkNN). Οι αλγόριθμοι εφαρμόζονται πάνω σε γράφους που έχουν παραχθεί είτε μέσω της μεθόδου παραγωγής kNN-graph, χρησιμοποιώντας LSH, είτε μέσω της μεθόδου MRNG. Και οι 2 αλγόριθμοι χρησιμοποιούν συναρτήσεις που έχουν παραγθεί από την προηγούμενη εργασία, η οποίες δεν θα αναφερθούν εδώ.

Η υλοποίηση του αλγορίθμου παραγωγής NN-Graph ήταν απλή: Εισάγουμε τα δεδομένα σε μία δομή LSH και κάνουμε kNN ερωτήσεις για κάθε δεδομένο, αφαιρώντας πάντα το ίδιο δεδομένο από το σύνολο γειτόνων. Ο αλγόριθμος GNNS υλοποιείται όπως στις διαφάνειες, με την βοήθεια marked λίστας και ουράς προταιρεότητας που προσομοιώνουν την λειτουργία των συνόλων του αλγορίθμου. Έχει προσθεθεί άλλη μία δομή, η οποία αποθηκεύει τους κόμβους από τους οποίους ξεκινήσαμε αναζήτηση και, αν ξαναεπιλεχθούν σε random restart, τους αγνοεί.

Κατάλογος Αρχείων

Όλες οι παραπάνω δομές έχουν δικά τους header και implementation αρχεία, τα οποία βρίσκονται αντίστοιχα εντός του source κατάλογου στους υποκαταλόγους:

• GraphCreation: Υλοποίηση μίας κλάσης γράφου, καθώς και των 2 μεθόδων που χρησιμοποιούνται για την δημιουργία των γράφων που θα χρησιμοποιήσουμε.
• GraphCreation/LSH: Δομή υλοποίησης LSH.
• GraphCreation/LSH/EuclideanSpace: Δομή υλοποίησης συναρτήσεων του ευκλείδιου χώρου
• GraphCreation/LSH/LinearCombinationHash: Δομή υλοποίησης συναρτήσεων γραμμικού συνδυασμού απο συναρτήσεις ευκλείδιου χώρου
• GraphSearch: Υλοποίηση των αλγορίθμων GNNS και SearchOnGraph για αναζήτηση κοντινότερων γειτόνων σε γράφο.

Εκτός από αυτές, υπάρχουν και κάποια ακόμα αρχεία στον κώδικα που χρησιμοποιούνται σαν βιβλιοθήκες:

• MathLib: Γενική βοήθεια με υπολογισμό μαθηματικών πράξεων, κυρίως όσων αφορούν διανύσματα.
• RandomHelper: Παροχή διεπαφής ανάμεσα στον προγραμματιστή και μίας μηχανής παραγωγής τυχαίων αριθμών, η οποία μπορεί να παράγει αριθμούς μέσω των εξής κατανομών: Normal, Uniform Real, Uniform Int..
• ExhaustiveSearch: Παρέχει επίλυση των προβλημάτων kNN και NN σε χρόνους Ο(nlogn) και Ο(n) αντίστοιχα.
• DataProcessing: Γενικές συναρτήσεις για φόρτωμα και προ-επεξεργασία των αρχείων εισόδου, καθώς και δομές που εξυπηρετούν την υλοποίηση των αλγορίθμων. Υλοποιείται από τα αρχεία dataLoading.cpp και dataProcessing.cpp, καθένα από τα οποία έχει δικό του header file(υλοποιούν όμως το ίδιο namespace).

Στον φάκελο Sim είναι υλοποιημένα τα προγράμματα που θα αποτελέσουν το σημείο εισόδου για ελεγχο των αλγορίθμων.

Οδηγίες Μεταγλώττισης

Οι παρακάτω εντολή πρέπει να εκτελεστεί από terminal στον root φάκελο της εργασίας:

make graph_search

Για γρήγορη εκτέλεση, μπορείτε επίσης να χρησιμοποιήσετε τις:

make haste1 make haste2

οι οποίες εκτελούν το πρόγραμμα με κάποιες προκαθορισμένες παραμέτρους για αναζήτηση με GNNS και SearchOnGraph αντίστοιχα.

Οδηγίες εκτέλεσης

Όπως δίνονται στην εκφώνηση

./graph_search –d <input file> –q <query file> –k <int> -E <int> -R <int> -N <int> -l <int, only for Search-on-Graph> -m <1 for GNNS, 2 for MRNG> -ο <output file>