readme.txt

/* readme.txt */

==========================================
(α) ΣΤΟΙΧΕΙΑ ΦΟΙΤΗΤΩΝ
==========================================

ΚΩΝΣΤΑΝΤΙΝΟΣ ΤΣΙΚΟΥΡΗΣ | ΑΜ : 1115201800201
ΒΑΣΙΛΕΙΟΣ ΒΑΣΙΛΑΚΗΣ    | ΑΜ : 1115201800018

==========================================
(β) ΤΙΤΛΟΣ ΚΑΙ ΠΕΡΙΓΡΑΦΗ ΠΡΟΓΡΑΜΜΑΤΟΣ
==========================================

ΕΥΡΕΣΗ ΠΛΗΣΙΕΣΤΕΡΩΝ ΓΕΙΤΟΝΩΝ ΚΑΙ ΣΥΣΤΑΔΟΠΟΙΗΣΗ ΧΡΟΝΟΣΕΙΡΩΝ

Το παρόν πρόγραμμα υλοποιεί αλγορίθμους εύρεσης πλησιέστερων χρονοσειρών τόσο προσεγγιστικούς (LSH, Hypercube, Range Search) όσο και ωμής βίας.
Επίσης υλοποίουνται αλγόριθμοι συσταδοποίησης χρονοσειρών, με βάση τον αλγόριθμο του Lloyd's, οι οποίοι βελτιώνουν τον βασικό αλγόριθμο ως προς
την αρχικοποίηση των κεντροειδών (k-means++ initialization) και ως προς το βήμα της ανάθεσης (reverse assignment με χρήση LSH, Hypercube, LSH Frechet).
Τέλος υλοποιείται και μια μετρική για την αξιολόγηση της συσταδοποίησης (Silhouette).
Οι χρονοσειρές συγκρίνονται βάσει της μετρικής Frechet(δυσδιάστατες και μονοδιάστατες χρονοσειρές) και της ευκλείδιας απόστασης(μονοδιάστατες χρονοσειρές)

==========================================
(γ) ΚΑΤΑΛΟΓΟΣ ΚΑΙ ΠΕΡΙΓΡΑΦΗ ΑΡΧΕΙΩΝ
==========================================

ΣΤΟΝ ΦΑΚΕΛΟ common :

- Στο assist_functions.cpp/.hpp περιέχονται μερικές αυτοτελείς βοηθητικές συναρτήσεις του προγράμματος.

- Στο params.hpp, δηλώνονται μερικές global παράμετροι των αλγορίθμων, για ευκολία.

- Τα input_check.cpp/.hpp περιέχουν συναρτήσεις που τσεκάρουν τα arguments από το command line και αρχικοποιούν τις παραμέτρους
του κάθε αλγορίθμου, και συναρτήσεις που διαβάζουν τα αρχεία δεδομένων (input/query file, config file) .

- Τα object.cpp/.hpp περιέχουν την abstract κλάση που περιγράφει ένα αφηρημένο αντικείμενο abstract_object. Αυτή η κλάση αποτελεί στην ουσία
ένα interface για τις διαφορετικές αναπαραστάσεις των αντικειμένων που χρησιμοποιεί το πρόγραμμα.  Όλα τα διαφορετικά είδη αντικειμένων,
που χρησιμοποιεί το πρόγραμμα (d-διάστατα σημεία, μονοδιάστατες χρονοσειρές, δισδιάστατες χρονοσειρές) οι κλάσεις τους κληρονομούν από αυτήν
την abstract κλάση και επαναορίζουν τις pure virtual συναρτήσεις της.  Εδώ βρίσκονται και η κλάση που ορίζει, περιγράφει και αναπαριστά ένα d-διάστατο αντικείμενο-σημείο (ή μονοδιάστατη χρονοσειρά) και η κλάση που ορίζει, περιγράφει και αναπαριστά μια δισδιάστατη χρονοσειρά.
Επίσης ορίζονται βοηθητικές συναρτήσεις για τη διαχείριση αντικειμένων των κλάσεων.

- Τα dataset.cpp/.hpp περιέχουν την κλάση που ορίζει και περιγράφει τη δομή που αποθηκεύει τη πληροφορία (ουσιαστικά δείκτες σε αφηρημένα αντικείμενα)
ενός αρχείου δεδομένων. Επίσης ορίζονται βοηθητικές συναρτήσεις για τη διαχείριση αντικειμένων της κλάσης. Στην περίπτωση του υπολογισμού της απόστασης
του continuous Frechet, εκτελείται και η διαδικασία του filtering και στις καμπύλες εισόδου (input curve) και στις καμπύλες ερωτήσεων (query curves) και αυτές
θα αποθηκευτούν στις δομές Dataset

- Τα h_hash.cpp/.hpp περιέχουν την κλάση που ορίζει και περιγράφει γενικά το H family συναρτήσεων (τις συναρτήσεις h των διαφανειών) .

- To search_method.hpp, περιέχει μια abstract κλάση search method, η οποία αποτελεί ουσιαστικά ένα interface για τις διαφορετικές μεθόδους
αναζήτησης πλησιέστερων χρονοσειρών (hypercube, lsh, lsh_frechet discrete/continuous κλπ).  Όλες οι κλάσεις που υλοποιούν κάποια απο τις 
μεθόδους αναζήτησης κληρονομούν από την abstract αυτή κλάση και επαναορίζουν τις pure virtual συναρτήσεις της.

____________________________________________________________________________________________________________________________________________

ΣΤΟΝ ΦΑΚΕΛΟ data :
Υπάρχει ένα cluster.conf αρχείο για το clustering, καθώς και τα αρχεία δεδομένων nasd_input, nasd_query.

____________________________________________________________________________________________________________________________________________

ΣΤΟΝ ΦΑΚΕΛΟ lsh_folder :

- Τα g_hash.cpp/.hpp περιέχουν την κλάση που ορίζει και περιγράφει τις amplified συναρτήσεις κατακερματισμού g.

- Τα hash.cpp/.hpp περιέχουν την κλάση που ορίζει και περιγράφει τη δομή ενός απλού πίνακα κατακερματισμού (hash-table),
ως πίνακα από συνδεδεμένες λίστες.

- Τα h_grid.cpp/.hpp περιέχουν την κλάση που ορίζει και περιγράφει ένα γενικευμένο πολυδιάστατο grid, πάνω στο οποίο γίνονται
snap οι χρονοσειρές για μείωση της πολυπλοκότητάς τους.

- Τα lsh_struct.cpp/.hpp περιέχουν την δομή που χρησιμοποιείται για το LSH (τα L hash-tables), καθώς και συναρτήσεις δημιουργίας/αρχικοποίσης/χειρισμού
της δομής.  Επίσης εδώ ορίζονται και υλοποιούνται οι προσεγγιστικοί αλγόριθμοι εύρεσης πλησιέστερων γειτόνων με χρήση LSH (appr_nearest_neighbors, range_search), μέσω της μεθόδου execute που εκτελεί τα απαιτούμενα της εργασίας και εκτυπώνει τα κατάλληλα αποτελέσματα στο αρχείο.
Η δομή υποστηρίζει LSH είτε σε πολυδιάστατα σημεία, είτε σε μονοδιάστατες χρονοσειρές , είτε σε δισδιάστατες χρονοσειρές.
Στην περίπτωση του continuous Frechet, πέρα από την αποθήκευση των καμπυλών στους πίνακες του αρχείου hash.cpp/hpp, για τον υπολογισμό του exact continuous Frechet ανάμεσα
σε 2 καμπύλες με χρήση της βιβλιοθήκης Fred, κάθε καμπύλη εισόδου μετατρέπεται σε καμπύλη της κλάσης Curve της βιβλιοθήκης Curve και αποθηκεύεται σε ένα std::vector για χρήση αργότερα
ώστε η μετατροπή να χρειαστεί να γίνει μόνο μια φορά για κάθε καμπύλη εισόδου

____________________________________________________________________________________________________________________________________________

ΣΤΟΝ ΦΑΚΕΛΟ cluster_folder :

- Τα cluster_info.cpp/.hpp περιέχουν την κλάση που χρησιμοποιείται για να κρατήσει πληροφορία για την συσταδοποίηση (τα κεντροειδή και τα clusters).
Επίσης εδώ ορίζονται και υλοποιούνται όλες οι συναρτήσεις για την υλοποιήση των αλγορίθμων συσταδοποίησης (kmeans++ initialization, exact lloyd's, 
reverse assignment using LSH or Hypercube range search or LSH_Frechet, update των κεντροειδών, μετρική Silhouette).

- Τα cbtree.cpp/.hpp υλοποιούν τη δομή ενός complete binary tree, όπου κάθε κόμβος αποθηκεύει τη μέση καμπύλη των παιδιών του.  Επίσης
υλοποιούνται διάφορες συναρτήσεις που υλοποιούν τη ζητούμενη λειτουργικότητα όπως η post order traversal που υπολογίζει και επιστρέφει τη συνολική μέση
καμπύλη του Cluster από τη ρίζα του δέντρου.

____________________________________________________________________________________________________________________________________________

ΣΤΟΝ ΦΑΚΕΛΟ hypercube_folder :

- Τα f_hash.cpp/hpp περιέχουν την κλάση των συναρτήσεων f_hash που αναθέτουν ακεραίους με τυχαίο τρόπο στο σύνολο {0,1}.

- Τα hypercube_class.cpp/hpp περιέχουν την κλάση hypercube που δημιουργεί τον d'-διάστατο υπερκύβο, αποθηκεύει τα αντικείμενα-σημεία με τον τρόπο που περιγράφουν οι διαφάνειες, καθώς και οι
 	απαραίτητες μέθοδοι kNN, range search και η έκδοση της ωμής βίας επίλυσης του kNN για τον υπερκύβο και έχει την μέθοδο execute που εκτελεί τα απαιτούμενα της εργασίας και 
 	εκτυπώνει τα κατάλληλα αποτελέσματα.

____________________________________________________________________________________________________________________________________________

- To search.cpp, περιέχει τη main συνάρτηση για το search (LSH, Hypercube, Frechet discrete/continuous) που υλοποιεί τη ζητούμενη λειτουργικότητα.
- To cluster.cpp, περιέχει τη main συνάρτηση για το clustering που υλοποιεί τη ζητούμενη λειτουργικότητα.
- Το unit_testing.cpp χρησιμοποιεί την βιβλιοθήκη acutest από το https://github.com/mity/acutest για τα unit tests επειδή είανι απλή στη χρήση της.
	Στο αρχείο αυτό ελέγχονται οι συναρτήσεις υπολογισμού του discrete Frechet ανάμεσα σε 2 2d και σε 2 1d καμπύλες αντίστοιχα, του βέλτιστου traversal ανάμεσα σε 2d καμπύλες αλλά και της
	κατασκευής της μέσης καμπύλης πάνω σε καμπύλες οι οποίες έχουν σχετικά απλή δομή ώστε να μπορεί να μπορεί ο χρήστης να γνωρίζει τι αποτελέσματα πρέπει να αναμένει να βγάλουν αυτές οι
	συναρτήσεις. 

=======================================
(δ) ΟΔΗΓΙΕΣ ΜΕΤΑΓΛΩΤΤΙΣΗΣ
=======================================

Η εντολή mv_objs μετακινεί όλα τα αντικειμενικά αρχεία .o σε έναν φάκελο για ευκολία.

Για τη δημιουργία του εκτελέσιμου στο search :

make search mv_objs

./search –i <input_file_path> –q <query_file_path> –k <int> -L <int> -M <int> -probes <int> -ο <output_file_path> -algorithm <LSH or Hypercube or Frechet> -metric <discrete or continuous | only for –algorithm Frechet> -delta <double> 
όπου οι παράμετροι είναι όπως ορίζονται στην εκφώνηση.

Για τη δημιουργία του εκτελέσιμου στο Clustering :

make cluster mv_objs

./cluster –i <input_file_path> –c <config_file_path> -o <output_file_path> -update <Mean Frechet or Mean Vector> –assignment <Classic or LSH or Hypercube or LSH_Frechet> -complete <optional> -silhouette <optional> 
όπου οι παράμετροι είναι όπως ορίζονται στην εκφώνηση.

Για την δημιουργία του unit_testing:

make unit_testing

./unit_testing


Για το config_file_path μπορεί να χρησιμοποιηθεί το έτοιμο config_file που έχουμε στο data/cluster.conf.

============================================================================
(ε) ΟΔΗΓΙΕΣ ΧΡΗΣΗΣ / ΣΧΕΔΙΑΣΤΙΚΕΣ ΕΠΙΛΟΓΕΣ-ΠΑΡΑΔΟΧΕΣ / ΕΠΙΛΟΓΕΣ ΠΑΡΑΜΕΤΡΩΝ 
============================================================================

Το τυχαίο διάνυσμα v στον ορισμό της συνάρτησης κατακερματισμού h, το κανονικοποιούμε (γιαυτό και τα w που επιλέγουμε είναι μικρά).

Για τα τυχαία ακέραια r_i στον ορισμό της συνάρτησης κατακερματισμού g, όπως ειπώθηκε στο φροντιστήριο δεν έχει 
ιδιαίτερη αλγοριθμική σημασία το εύρος τους, και γιαυτό, για πράξεις με μικρότερους αριθμούς, τα επιλέγουμε στο [1,10000].

Για το lsh σε vectors, καλά ** αποτελέσματα σε μικρό σχετικά χρόνο παρατηρήθηκαν για τιμές του w γύρω στο w = 20 με 30.
Επειδή τα αρχεία εισόδου είναι πολύ μικρά όμως, οι χρόνοι για το LSH σε vectors και για το brute force συνήθως
είναι συγκρίσιμοι, δε φαίνεται τόσο πολύ η διαφορά όσο στην πρώτη εργασία.
Μείωση του w οδηγεί σε ταχύτερους χρόνους αλλά σε προσεγγιστικά λιγότερο ακριβή αποτελέσματα, ενώ αύξηση του w
οδηγεί σε περισσότερο ακριβή αποτελέσματα, αλλά σε χειρότερους χρόνους.

Για το lsh σε time series χρησιμοποιώντας discrete frechet, το w επιλέγεται πάλι εκεί γύρω στο 30-40.
Αλλά δεν έχει τόση μεγάλη βαρύτητα σαν υπερπαράμετρος όσο η τιμή του δέλτα. 
Επίσης να αναφέρουμε ότι επειδή τα αρχεία είναι μικρά, για κάποια από τα query time series, σε αρκετές εκτελέσεις
δεν βρίσκεται κανένα input time series με ακριβώς ίδιο id.  Ο αριθμός αυτών που δεν βρέθηκε γείτονας αλλάζει
σε κάθε εκτέλεση, λόγω της πιθανοτικής φύσης του αλγόριθμου, αλλά γενικά είναι γύρω στα 2 με 3 από τα 10.
Με μικρότερες τιμές του δέλτα όμως, τα αποτελέσματα είναι πιο σταθερά, έχουμε προσεγγιστικά πιο ακριβή αποτελέσματα,
αλλά ο χρόνος αυξάνεται. Για τον discrete Frechet, σχετικά καλά αποτελέσματα, σε πολύ καλούς χρόνους σε σχέση με το brute force, 
παρατήρηθηκαν για δέλτα γύρω στο 1.2. Όπως είπαμε αν θέλουμε καλύτερη ακρίβεια, αλλά θυσιάζοντας χρόνο, μπορούμε να μειώσουμε
ακόμα το δέλτα.

Επίσης για συνδυασμούς των k, L, καλά αποτελέσματα δίνουν τα ζευγάρια k = 5, L = 7, αλλά και τα default k = 4, L = 5.

Για τον continuous Frechet, δηλαδή για lsh σε καμπύλες μονοδιάστατων σημείων, όπως αναφέρθηκε παραπάνω, γίνεται το filtering των καμπυλών στην εισαγωγή τους στις
δομές Dataset και μετά το πρόγραμμα χειρίζεται τις φιλτραρισμένες καμπύλες για την εξαγωγή των επιθυμητών αποτελεσμάτων. Όσον, αφορά το w, έχει την τιμή 40.
Ωστόσο, παρατηρήθηκε ότι έχει πολύ μεγαλύτερη βαρύτητα η παράμετρος delta παρά το w για καλές προσεγγιστικές λύσεις με καλή πιθανότητα. Για την τιμή της delta, προτείνεται να
είναι μικρότερη της τιμής 0.01 διότι διαφορετικά υπάρχει καλή πιθανότητα, για τις εισόδους και queries που έχουν δωθεί, να επηρεαστούν σημαντικά από την hash συνάρτηση για καμπύλες
Επίσης, η σταθερά epsilon στην προεπεξεργασία (filtering) των καμπυλών, έχει επιλεχθεί να είναι 0.01 ώστε να μην επηρεαστούν αρκετά οι τιμές των αποστάσεων Frechet ανάμεσα στις καμπύλες.
Ωστόσο, η τιμή delta μπορεί να γίνει και μεγαλύτερη αν είναι επιθυμητοί καλύτεροι LSH χρόνοι αλλά τότε αυξάνεται η πιθανότητα αρκετά ώστε να υπάρχει πλέον κάποιος κίνδυνος να μην είναι 
τόσο καλές οι προσεγγιστικές αποστάσεις. Μια κάπως καλή τιμή είναι η delta = 1. Αυτές οι παρατηρήσεις όσον αφορά το πρόβλημα Aiii, δηλαδή την περίπτωση του continuous Frechet.



Για τον υπερκύβο ισχύουν αυτά που είχαμε αναφέρει και στην πρώτη εργασία.

** Βάσει κάποιων μετρικών που εξηγούμε παρακάτω και τυπώνουμε στο std::cout σε κάθε εκτέλεση.

Μετρικές που επιλέξαμε για να αξιολογήσουμε τις υπερπαραμέτρους:

Άθροισμα των dist_true / Άθροισμα των dist_appr , όπου το κάθε άθροισμα το παίρνουμε για όλα τα query points, appr είτε lsh, είτε cube.
maxAF = μέγιστο κλάσμα από τα dist_appr / dist_true, όπου appr είτε lsh είτε cube.
averageAF = μέσος όρος των κλασμάτων dist_appr / dist_true, για όλα τα query points
average time fraction = μέσος όρος των λόγων των χρόνων time_appr / time_brute_force, για όλα τα query points.

Για το clustering, σαν κριτήριο τερματισμού επιλέχθηκε η μέση μετατόπιση των κεντροειδών, μεταξύ δύο συνεχόμενων επαναλήψεων, να είναι
μικρότερη από μία μικρή θετική ποσότητα e.  Σχετικά καλά αποτελέσματα σε λίγες επαναλήψεις, δίνει η τιμή e = 1 για mean vector update method
και e = 10 με 20 για mean frechet.
Επίσης προστέθηκε και ένα threshold στον αριθμό των επαναλήψεων του clustering, σε περίπτωση που κάποια εκτέλεση αργεί να συγκλίνει στα 
παραπάνω κριτήρια τερματισμού.  Το threshold που επιλέχθηκε είναι γύρω στις 12 επαναλήψεις.
Επίσης να αναφέρουμε ότι στη περίπτωση υπολογισμού της μέσης καμπύλης στο mean frechet update method, επειδή η πολυπλοκότητα της καμπύλης
δύναται να αυξηθεί αυθαίρετα πολύ ανάλογα με το πόσα αντικείμενα βρίσκονται σε ένα cluster, μετά τον υπολογισμό μιας μέσης καμπύλης,
τη φιλτράρουμε για να μειωθεί η πολυπλοκότητά της σε μέγεθος συγκρίσιμο ή το ίδιο με την ενιαία πολυπλοκότητα των καμπυλών του input.
Ο τρόπος που τη φιλτράρουμε είναι για όσα παραπάνω σημεία έχει η μέση καμπύλη, επιλέγουμε τυχαία 2 διαδοχικά, και τα αντικαθιστάμε με το
μέσο τους.  'Ετσι, μειώνουμε τη πολυπλοκότητα της μέσης καμπύλης κατά 1 κάθε φορά, μέχρι να φτάσουμε σε ικανοποιητικά μικρή πολυπλοκότητα,
χωρίς να αλλάζει υπερβολικά η μορφή της μέσης καμπύλης.


Στο makefile, πέρα από τη μεταγλώττιση των αρχείων υπάρχει και η εντολή make mv_objs όπου μεταφέρει όλα τα αντικειμενικά αρχεία σε ένα φάκελο objects. υπάρχουν και εντολές make για εκτελέσεις των εκτελέσιμων ανάλογο με το μέγεθος input, query και μεθόδου ανάλογα με το αν είναι το lsh, το hypercube η το cluster και με τις προκαθορισμένες παραμέτρους. Για το τελευταίο υπάρχει και ένα bash script το οποίο κάνει την ίδια δουλειά αλλά τώρα ο χρήστης μπορεί να προκαθορίσει και το ποιες θα είναι οι παράμετροι ανάλογα με το εκτελέσιμο.