README.txt

Software-Development-for-Algorithmic-Problems_Project-2 |
—————————————————————————————————————————————————————————
Ομάδα Χρηστών 66	|
————————————————————————
-Ιωάννης Καπετανγεώργης |
 1115201800061 		|
-Δημήτριος Σιταράς	|
 1115201800178 	 	|
————————————————————————————————————————————————————————————————————————————————————————————————————
Github link: https://github.com/giannhskp/Software-Development-for-Algorithmic-Problems_Project-2
————————————————————————————————————————————————————————————————————————————————————————————————————

► Οργάνωση Κώδικα:


.
├── BinaryTree
│   ├── binaryTree.c
│   └── binaryTree.h
│   
├── Clustering
│   ├── clusterHelpingFuns.c
│   ├── clusterHelpingFuns.h
│   ├── clustering.c
│   ├── clustering.h
│   ├── kmeansPlusPlus.c
│   └── kmeansPlusPlus.h
│ 
├── FrechetDistance
│   ├── discreteFrechet.c
│   └── discreteFrechet.h
│   
├── Fred-master
│   └── src
│       ├── config.cpp
│       ├── config.hpp
│       ├── curve.cpp
│       ├── curve.hpp
│       ├── frechet.cpp
│       ├── frechet.hpp
│       ├── interval.cpp
│       ├── interval.hpp
│       ├── my_interface.cpp
│       ├── my_interface.hpp
│       ├── point.cpp
│       ├── point.hpp
│       ├── simplification.cpp
│       ├── simplification.hpp
│       └── types.hpp
│ 
├── Hypercube
│   ├── HashMap
│   │   ├── hashmap.c
│   │   └── hashmap.h
│   ├── hypercube.c
│   └── hypercube.h
│ 
├── LSH
│   ├── helperFunctions.c
│   ├── helperFunctions.h
│   ├── lsh.c
│   └── lsh.h
│   
│ 
├── Vector
│   ├── vector.c
│   └── vector.h
│   
│ 
├── hashTable
│   ├── hashTable.c
│   ├── hashTable.h
│   └── hashTableList
│       ├── hashTableList.c
│       └── hashTableList.h
│       
├── parsing
│   ├── parsingCluster.c
│   ├── parsingCluster.h
│   ├── parsingCube.c
│   ├── parsingCube.h
│   ├── parsingLSH.c
│   └── parsingLSH.h
│ 
├── Makefile
├── README.txt
├── cluster.conf
├── mainCluster.c
├── mainCube.c
├── mainCube.h
├── mainLSH.c
├── mainLSH.h
├── mainPart1.c  
└── unitTesting.c
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

► Γενικά:

	→ Ο κώδικας είναι σχολιασμένος.

	→ Πληρούνται όλες οι προϋποθέσεις / απαιτήσεις που αναγράφονται στην εκφώνηση της άσκησης.

        → Η υλοποίηση του project έγινε με τη χρήση συστήματος διαχείρισης εκδόσεων λογισμικού και συνεργασίας (Git).
          Ο σύνδεσμος του project είναι: https://github.com/giannhskp/Software-Development-for-Algorithmic-Problems_Project-2

	→ Όλη η μνήμη που δεσμεύεται δυναμικά κατά την εκτέλεση του προγράμματος, αποδεσμεύεται πλήρως.
  	  ( Έχει ελεγχθεί μέσω valgrind στα μηχανήματα linux της σχολής. )

	→ Υπάρχει η Απόκρυψη Πληροφορίας που ζητήθηκε στο φροντιστήριο.

	→ Eντολή μεταγλώττισης: make (υπάρχει αρχείο Makefile)

	→ Εντολές εκτέλεσης για κάθε ένα από τα δύο εκτελέσιμα:

		► ./search -i <input file> -q <query file> -k <int> -L <int> -M <int> -probes <int> -ο <output file> -algorithm <LSH or Hypercube or Frechet> -metric <discrete or continuous | only for -algorithm Frechet> -delta <double> -distanceTrueOff
			π.χ.:
				Ερώτημα Α.i/LSH: 	./search -i nasd_input.csv -q nasd_query.csv -o outLSHVector -algorithm LSH -k 6 -L 4
				Ερώτημα Α.i/Hypercube:  ./search -i nasd_input.csv -q nasd_query.csv -o outCubeVector -algorithm Hypercube -M 50 -probes 3 -k 5
				Ερώτημα Α.ii: 		./search -i nasd_input.csv -q nasd_query.csv -o outDiscreteFrechet -algorithm Frechet -metric discrete -delta 1 -k 4 -L 5
				Ερώτημα Α.iii: 		./search -i nasd_input.csv -q nasd_query.csv -o outContinuousFrechet -algorithm Frechet -metric continuous -delta 1 -distanceTrueOff

		
		► ./cluster -i <input file> -c <configuration file> -o <output file> -update <Mean Frechet or Mean Vector> -assignment <Classic or LSH or Hypercube or LSH_Frechet> -complete <optional> -silhouette <optional> -delta <optional>
			π.χ.:
				Μέθοδος 1: 	./cluster -i nasd_input.csv -c cluster.conf -o outputCluster1 -assignment Classic -update Mean Vector
				Μέθοδος 2: 	./cluster -i nasd_input.csv -c cluster.conf -o outputCluster1 -assignment Classic -update Mean Frechet -delta 1
				Μέθοδος 3: 	./cluster -i nasd_input.csv -c cluster.conf -o outputCluster1 -assignment LSH
					ή  	./cluster -i nasd_input.csv -c cluster.conf -o outputCluster1 -assignment LSH -update Mean Vector
				Μέθοδος 4: 	./cluster -i nasd_input.csv -c cluster.conf -o outputCluster1 -assignment LSH_Frechet -delta 1
					ή  	./cluster -i nasd_input.csv -c cluster.conf -o outputCluster1 -assignment LSH -update Mean Frechet -delta 1
				Μέθοδος 5: 	./cluster -i nasd_input.csv -c cluster.conf -o outputCluster1 -assignment Hypercube
 	

	→ Στο εκτελέσιμο του πρώτου μέρους προστέθηκε η δυνατότητα να δοθεί στη γραμμή εντολών η εξής παράμετρος: -distanceTrueOff, 
	  ώστε να παραλείπεται η εύρεση του πλησιέστερου γείτονα κάθε χρονοσειράς με τον brute force τρόπο.

	→ Στο εκτελέσιμο του δεύτερου μέρους προστέθηκε η δυνατότητα να δοθεί (προαιρετικά) στη γραμμή εντολών η εξής παράμετρος: -delta <value>, 
	  ώστε να μπορούμε να θέσουμε την τιμή του δ που επιθυμούμε (για τις μεθόδους 2 και 4). Αν δεν δοθεί, χρησιμοποιείται η default τιμή delta=1.

	→ Tα unit tests υλοποιήθηκαν με χρήση της βιβλιοθήκης CUnit στο αρχείο unitTesting.c, όπου 
	  ουσιαστικά "επαληθεύουμε" την σωστή λειτουργία των παρακάτω συναρτήσεων: 
		- discreteFrechet(...)
		- meanCurveBetween2Curves(...)
		- computeG(...)
	  
	  Η χρήση της βιβλιοθήκης CUnit προϋποθέτει να έχει πραγματοποιηθεί η εγκατάστασή της, αυτό σε μηχανήματα linux γίνεται μέσω της εντολής:

	  sudo apt-get install libcunit1 libcunit1-doc libcunit1-dev
	
	  Το εκτελέσιμο που παράγεται μέσο της εντολής make είναι το unitTesting και η εντολή εκτέλεσης του είναι η ακόλουθη:

	  ./unitTesting

	  Το Unit Testing εξηγείται αναλυτικά στην συνέχεια, στην αντίστοιχη παράγραφο.

	→ Υπάρχει η δυνατότητα μεταγλώττισης μόνο των απαραίτητων αρχείων για τα unit tests μέσο της εντολής: make unit_testing	

	→ make clean, για την διαγραφή των παραγόμενων από την μεταγλώττιση αρχείων.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------


Μέρος Α 
—————————
Το πρώτος μέρος της εργασίας αφορά την αναζήτηση του πλησιέστερου γείτονα μιας χρονοσειράς q εντός ενός 
συνόλου χρονοσειρών με τρεις τεχνικές.
Ο διαχωρισμός των τεχνικών γίνεται στο αρχείο mainLSH.c, καθώς για κάθε τεχνική που ζητείται υπάρχει και 
η αντίστοιχη συνάρτηση που την "υλοποιεί", συγκεκριμένα:

	1. vectorTimeSeriesLSH(...) για το πρώτο ερώτημα.
	2. vectorTimeSeriesLSHFrechetDiscrete(...) για το δεύτερο ερώτημα.
	3. vectorTimeSeriesLSHFrechetContinuous για το τρίτο ερώτημα.

Έτσι, ανάλογα με τις παραμέτρους που δίνει ο χρήστης στην γραμμή εντολών καλείται κάθε φορά η κατάλληλη συνάρτηση
από το αρχείο search.c .
Στην συνέχεια ακολουθεί η επεξήγηση υλοποίησης των τεχνικών/ερωτημάτων.
Οι υλοποιήσεις των LSH και Hypercube είναι ακριβώς ίδιες με την πρώτη εργασία. Η μόνη διαφορά είναι η επιλογή της τιμής του w το οποίο χρησιμοποιείται από τις συναρτήσεις H.
Περισσότερες λεπτομέρειες σχετικά με την τιμή του w εξηγούνται στην συνέχεια στην αντίστοιχη παράγραφο.



▪ Ερώτημα 1ο
———————————————
Σε αυτό το ερώτημα κάθε χρονοσειρά αναπαρίσταται ως διάνυσμα στον ευκλείδιο χώρο R^d, η απόσταση μεταξύ των
διανυσμάτων υπολογίζεται με βάσει της μετρικής L2 και χρησιμοποιούνται οι αλγόριθμοι LSH και Hypercube της πρώτης
εργασίας. Επομένως, αφού έχουμε να ασχοληθούμε καθαρά με διανύσματα η υλοποίηση μας, όσον αναφορά τους αλγορίθμους
LSH και Hypercybe, είναι για την συγκεκριμένη περίπτωση ίδια με αυτή της πρώτης εργασίας.
Η μόνη "διαφορά" που υπάρχει είναι πως για κάθε χρονοσειρά-διάνυσμα αναζητείται ένας πλησιέστερος γείτονας.
Έχουμε προσθέσει στα αρχεία το README της προηγούμενης εργασίας προκειμένου να μπορείτε να ανατρέξετε εύκολα.

▪ Ερώτημα 2ο
———————————————
Σε αυτό το ερώτημα κάθε χρονοσειρά αναπαρίσταται ως πολυγωνική καμπύλη, επομένως δεσμεύουμε για κάθε χρονοσειρά
στo αντίστοιχο struct vec_node τον πίνακα (double* times) για την αποθήκευση του χρόνου, ο χρόνος έχει τιμές απο 0 έως την αντίστοιχη διάσταση των χρονοσειρών και μεταβάλλεται
κατά 1.00. Συνεπώς, για κάθε χρονοσειρά αποθηκεύουμε τις τιμές (άξονας y) που υπάρχουν στο αντίστοιχο αρχείο και τον 
χρόνο (άξονας x) που προφανώς είναι ο ίδιο για όλες τις χρονοσειρές. 

Πλέον, για την εισαγωγή των χρονοσειρών αλλά και την αναζήτηση των πλησιέστερων γειτόνων τους χρειάζεται να εφαρμοστεί snapping σε κάθε χρονοσειρά, έτσι
κάθε hash table του LSH έχει θεωρητικά ένα grid, τα grids διαφέρουν μεταξύ τους κατά έναν αριθμό t, ο οποίος παράγεται μέσω της ομοιόμορφης κατανομής.
Τα grids αυτά δεν χρειάζεται να αναπαρασταθούν μέσω κάποιας δομής, καθώς το snapping πραγματοποιείται μέσω της συνάρτησης timeSeriesSnapping() στο αρχείο LSH/lsh.c (αναλύεται στην συνέχεια).
Το μόνο, λοιπόν, που αποθηκεύουμε είναι ένας πίνακας με l αριθμούς t για κάθε διάσταση (struct grid_n στο αρχείο LSH/lsh.c), όπου ο κάθε t αντιστοιχεί σε ένα grid για κάθε ένα hash table του LSH.
Χρησιμοποιούμε διαφορετικό t για κάθε διάσταση, όπως αναφέρθηκε και στο eclass.
Πιο συγκεκριμένα, αφού δουλεύουμε στις δύο διαστάσεις, σε κάθε grid αντιστοιχούν δύο t. Ένα για την τιμή x (χρόνος) και ένα για την τιμή y.
Κάθε χρονοσειρά του input file και του query file πρέπει να περάσει από την διαδικασία του snapping,
ώστε η χρονοσειρά να μετατραπεί τελικά σε διάνυσμα για να εφαρμοστεί στην συνέχεια η εισαγωγή ή η αναζήτηση αντίστοιχα μέσο του LSH.
Συγκεκριμένα, κάθε σημείο (x,y) της χρονοσειράς αντιστοιχίζεται στο κοντινότερο σημείο του πλέγματος (grid) μέσω του τύπου
floor((x-t)/δ + 1/2)*δ + t . Ο τύπος αυτός στην συνάρτηση timeSeriesSnapping() εφαρμόζεται για κάθε συντεταγμένη ξεχωριστά χρησιμοποιώντας το αντίστοιχο t. Αποθηκεύουμε
λοιπόν κάθε τιμή που προκύπτει από τον παραπάνω τύπο στους αντίστοιχους πίνακες προκειμένου να γίνεται ο έλεγχος και 
η διαγραφή των διαδοχικών διπλότυπων σημείων της χρονοσειράς που κάνουν snap στο ίδιο σημείο του grid.
Αν δύο διαδοχικά σημεία γίνουν snap στο ίδιο σημείο του grid, τότε το δεύτερο απαλείφεται. 
Τελικά, προκύπτει έναν διάνυσμα τύπου (x1,y1,x2,y2,...,x2n,y2n), διπλάσιας διάστασης από την αρχική χρονοσειρά.
Βέβαια λόγω της απαλοιφής των διαδοχικών snapped σημείων μπορεί το διάνυσμα αυτό να είναι μικρότερης διάστασης. 
Έτσι στην περίπτωση που δεν υπάρχουν οι τιμές/τα σημεία, λόγω της διαγραφής των διαδοχικών διπλότυπων, ώστε να σχηματίσουν το διάνυσμα που θέλουμε
να παράγουμε τότε κάνουμε padding, συμπληρώνοντας ουσιαστικά το διάνυσμα με μεγάλες τιμές (PADDING_M 1000) για να φτάσουμε στην επιθυμητή διάσταση.
Έτσι, από την συνάρτηση timeSeriesSnapping επιστρέφεται ένα διάνυσμα, το οποίο το δίνουμε ως όρισμα στην συνάρτηση computeG() για να υπολογιστεί
η τιμή της g function, πηγαίνοντας στο αντίστοιχο bucket του hash table κλπ, η διαδικασίας εισαγωγής και αναζήτησης μετά το snapping/padding είναι η ίδια με αυτή της
πρώτη εργασίας.
Επίσης, από κάθε συνάρτηση G εκτός από το index/bucket προκύπτει και ένα ID το οποίο χρησιμοποιείται για το Querying trick (ακριβώς όπως και στην εργασία 1). 
Δηλαδή για να συγκρίνουμε μόνο curves με ίδιο ID στο εσωτερικό ενός bucket κερδίζοντας έτσι αρκετό χρόνο.


Επιπλέον, για να υπολογίσουμε την απόσταση μεταξύ των δύο διακριτών χρονοσειρών υλοποιούμε την ζητούμενη μετρική discrete
Frechet με χρήση του δυναμικού προγραμματισμού, δηλαδή όπως ακριβώς περιγράφεται στις διαφάνειες του μαθήματος.
Συγκεκριμένα, δημιουργούμε ένα 2-d πίνακα και αρχικοποιούμε την θέση [0][0] με την Ευκλείδια απόσταση (L2) μεταξύ των 2 πρώτων συντεταγμένων
των 2 χρονοσειρών που δίνονται ως είσοδο.
Έπειτα, συμπληρώνουμε την πρώτη γραμμή και την πρώτη στήλη του δυναμικού πίνακα κάνοντας τους αντίστοιχους υπολογισμούς, σύμφωνα με τους 
τύπους : c(1, j) = max{c(1, j − 1),|| p1 − qj ||} και c(i, 1) = max{c(i − 1, 1),|| p1 − qj ||}.
Ακολούθως, συμπληρώνουμε τον υπόλοιπο πίνακα, δηλαδή τα "εσωτερικά" του στοιχεία (i>1 και j>1), με βάση τον τύπο:
c(i, j) = max {min{c(i − 1, j), c(i − 1, j − 1), c(i, j − 1)}, || pi − qj ||}.
Τελικά, η απόσταση μεταξύ των 2 χρονοσειρών έχει υπολογιστεί μέσω του δυναμικού προγραμματισμού και βρίσκεται στο 
κάτω δεξιά στοιχείο του πίνακα, στην θέση [i-1][j-1], συνεπώς αυτήν την τιμή επιστρέφει και η συνάρτηση discreteFrechet() (η οποία βρίσκεται στο αρχείο FrechetDistance/discreteFrechet.c). 
Σημείωση: η απόσταση μεταξύ των συντεταγμένων των χρονοσειρών υπολογίζεται με την Ευκλείδια μετρική (L2).

Η μετρική discrete Frechet στο ερώτημα αυτό εξυπηρετεί τους ίδιους σκοπούς που εξυπηρετούσε η L2 στην πρώτη εργασία (και στο πρώτο ερώτημα),
δηλαδή μέσω αυτή καταφέρνουμε ουσιαστικά να συγκρίνουμε τις χρονοσειρές μεταξύ τους, υπολογίζοντας την μεταξύ τους απόσταση και έτσι
βρίσκουμε τελικά τον πλησιέστερο γείτονα κάθε χρονοσειράς που υπάρχει στο query file.

Επιγραμματικά, οι αλλαγές που έγιναν στην υλοποίηση (σε σχέση με την υλοποίηση του LSH της προηγούμενης εργασίας) για το συγκεκριμένο ερώτημα αναλύθηκαν παραπάνω και είναι:
	
	1) Στην δομή struct vec_node προστέθηκε ένας πίνακας για την αποθήκευση του χρόνου της κάθε χρονοσειράς.
	2) Για να εισαχθεί στην δομή LSΗ ή για να γίνει αναζήτηση του πλησιέστερου γείτονα μέσο της δομής LSΗ, 
	   κάθε χρονοσειρά περνάει πρώτα από την διαδικασία του snapping ώστε να μετατραπεί σε διάνυσμα και 
	   στην συνέχεια δίνεται σαν όρισμα σε κάθε συνάρτηση G του LSH έτσι ώστε να προκύψει το αντίστοιχο index (και ID) για το κάθε hash Table.
	3) Η απόσταση μεταξύ των χρονοσειρών υπολογίζεται βάσει την μετρικής Discrete Frechet.
	4) Παρατηρήσεις σχετικά με την παράμετρο delta αναφέρονται στην συνέχεια.



▪ Ερώτημα 3ο
———————————————
Στο ερώτημα αυτό, κάθε χρονοσειρά αναπαρίσταται ως πολυγωνική καμπύλη στην ευθεία R.
Έτσι απαλείφεται η διάσταση του χρόνου και δεν αποθηκεύεται εσωτερικά του αντίστοιχου struct (όπως στο ερώτημα A.ii).
Δηλαδή για την αναπαράσταση στο R χρησιμοποιούνται μόνοι οι τιμές που διαβάζονται από το αρχείο εισόδου.
Σε όλη την διαδικασία που εξηγείται στην συνέχεια (συμπεριλαμβανομένων των filtering, snapping, minima-maxima, Continuous Frechet Distance), δουλεύουμε με χρονοσειρές οι οποίες έχουν αναπαρασταθεί στην ευθεία R έχοντας απαλείψει την διάσταση του χρόνου. 

Η δομή που χρησιμοποιείται για την αποθήκευση αποτελείται από ένα μοναδικό hash table το οποίο ακολουθεί την λογική του LSH,
δηλαδή χρησιμοποιεί μια hash function G η οποία με την σειρά της χρησιμοποιεί k συναρτήσεις h. 
Άρα έχουμε ένα LSH με L=1.
 
Σε κάθε χρονοσειρά, πριν από το snapping, εφαρμόζουμε προεπεξεργασία φιλτραρίσματος για την μείωση της 
πολυπλοκότητάς της. Έτσι, έχουμε υλοποιήσει την συνάρτηση filtering(...) στο αρχείο LSH/lsh.c, η οποία δέχεται ως 
όρισμα μια χρονοσειρά και την παράμετρο epsilon ( ορίζεται ως σταθερά στο αρχείο search.c, FILTERING_E 0.1 ).
Στην συγκεκριμένη συνάρτηση, στις τιμές της χρονοσειράς εφαρμόζουμε τον τύπο των διαφανειών, δηλαδή για οποιαδήποτε
a, b, c "συνεχόμενα" σημεία της χρονοσειράς, αν ισχύει |a-b| <= epsilon και |b-c| <= epsilon τότε διαγράφουμε από την χρονοσειρά το σημείο b.
Επομένως, προκύπτει μια filtered χρονοσειρά με μειωμένα σημεία την οποία επιστρέφει η αντίστοιχη συνάρτηση.

Μετά από το filtering κάθε χρονοσειρά, όπως και στο προηγούμενο ερώτημα, περνάει από την διαδικασία του snapping, μόνο 
που τώρα υλοποιείται μέσο της συνάρτησης continuousTimeSeriesSnapping(...) ( στο αρχέιο LSH/lsh.c ) και εφαρμόζεται σε αντίθεση με πριν μόνο στην y συντεταγμένη της χρονοσειράς, αφού οι χρονοσειρές αναπαρίστανται στην ευθεία R.
Εφόσον έχουμε ένα μόνο hash table, έχουμε και ένα μόνο grid. Στο grid αυτό αντιστοιχεί μια μεταβλητή t, η τιμή της οποίας προκύπτει από την κανονική κατανομή (0,δ).
Δηλαδή προβάλουμε την χρονοσειρά στην μία διάσταση με βάση την συντεταγμένη y και εφαρμόζουμε snapping σε ένα μονοδιάστατο grid.  
Επομένως το νέο διάνυσμα που προκύπτει και επιστρέφεται από την εν λόγω συνάρτηση
είναι της μορφής (y1,y2,...yn), ίδιας διάστασης με την χρονοσειρά.
Το snapping προκύπτει εφαρμόζοντας σε κάθε συντεταγμένη τον εξής τύπο: floor( (x + t)/d ) * d
Τέλος, σε αντίθεση με το snapping στην discrete περίπτωση, δεν αφαιρούνται διαδοχικά σημεία τα οποία γίνονται snap στο ίδιο σημείο του grid.

Στην συνέχεια, στο ερώτημα αυτό, κάθε διάνυσμα πλέον ( η χρονοσειρά μέσω του snapping έχει "μετατραπεί" σε διάνυσμα) υφίσταται μια τελευταία επεξεργασία προτού
δοθεί ως όρισμα στην συνάρτηση g για να υπολογιστεί η τιμή της, η διαδικασία αυτή λέγεται minima and maxima και υλοποιείται μέσω της συνάρτησης
minima_maxima(...) στο αρχείο LSH/lsh.c. 
Αναλυτικότερα, η προαναφερόμενη συνάρτηση δέχεται ως όρισμα ένα διάνυσμα και ελέγχει διαδοχικές τριάδες σημείων του διανύσματος.
Για κάθε τριάδα διαδοχικών σημείων (έστω a,b,c) αν τα σημεία αυτά ακολουθούν ανοδική πορεία ή αντίστοιχα καθοδική πορεία τότε το ενδιάμεσο σημείο b απαλείφεται.
Δηλαδή αν a<=b<=c ή a>=b>=c. Αυτό, σαν ενιαίος τύπος μπορεί να γραφεί ως εξής:
αν min(a,c)<=b<=max(a,c) τότε το σημείο b αφαιρείται από το διάνυσμα.
Έτσι, τελικά σχηματίζεται ένα νέο "τριμαρισμένο" διάνυσμα (ίδιας διάστασης με το αρχικό), στο οποίο έχουμε εφαρμόσει και το κατάλληλο padding λόγω των 
τυχών διαγραμμένων τιμών από την παραπάνω διαδικασία.

Το διάνυσμα αυτό δίνεται ως είσοδος στην συνάρτηση G του μοναδικού hash table έτσι ώστε να προκύψει το index του αντίστοιχου bucket καθώς και το ID για το Querying trick.
Αφού βρούμε το index, αποθηκεύουμε στο hash table την αρχική καμπύλη εισόδου, που έχει γίνει projected στο R, (δηλαδή πριν το filtering) η οποία και θα χρησιμοποιηθεί στην συνέχεια για την σύγκριση και υπολογισμό απόστασης με τα queries.

Συνοπτικά η διαδικασία εισαγωγής ενός input curve στην δομή είναι η εξής:
	input curve projected to R -> filtering -> snapping -> minima-maxima -> G-function of LSH -> αποθήκευση του input curve στο hash table
Η διαδικασία που ακολουθεί ένα query curve είναι η ίδια με την διαφορά ότι αντί να αποθηκευτεί στο hash table υπολογίζει την απόσταση του με όλα τα curves που είναι αποθηκευμένα στο αντίστοιχο bucket του hash table και έχουν ίδιο ID (Querying trick). 
Τελικά κρατά αυτό με την μικρότερη απόσταση ως κοντινότερο γείτονα.

Για να υπολογίσουμε την απόσταση μεταξύ των δύο συνεχών χρονοσειρών χρησιμοποιούμε την μετρική Continuous Frechet, η οποία μας δόθηκε 
υλοποιημένη μέσω μιας βιβλιοθήκης C++ από το GitHub, τα αρχεία της βρίσκονται στον φάκελο Fred-master/src. Συνεπώς, για να μπορέσουμε να συνδέσουμε
την βιβλιοθήκη C++ με τα αρχεία μας ( που είναι "γραμμένα" σε C) φτιάξαμε την αντίστοιχη διεπαφή-συνάρτηση, η οποία υλοποιείται στο αρχείο 
my_interface.cpp ( βρίσκεται στον φακελο Fred-master/src) και μας επιστρέφει την αντίστοιχη απόσταση μεταξύ 2 χρονοσειρών υπολογιζόμενη με χρήση της μετρικής Continuous Frechet.
Ουσιαστικά, έχουμε φτιάξει μια συνάρτηση (εν ονόματι compute_continuous_distance(...) ) η οποία δέχεται σαν ορίσματα 2 πίνακες
και 2 ακεραίους, οι πίνακες έχουν τις τιμές των χρονοσειρών (που αντιστοιχούν στην προβολή στο R), ενώ οι ακέραιοι τις διαστάσεις για τις αντίστοιχες χρονοσειρές που
πρόκειται να δημιουργηθούν. Έτσι, με βάσει των παραπάνω παραμέτρων που περνάμε στην συνάρτηση, δημιουργούμε τελικά δύο αντικείμενα της κλάσης Curve τα c1,c2 , τα οποία προκύπτουν
μέσο των αντικειμένων p1 και p2 της κλάσης Points αξιοποιώντας σε αυτά τις παραμέτρους αντίστοιχα για κάθε χρονοσειρά. Με τα αντικείμενα c1,c2 που δημιουργήσαμε 
(τα οποία αναπαριστούν τις αντίστοιχες χρονοσειρές), μας δίνετε πλέον η δυνατότητα να καλέσουμε την συνάρτηση distance(...) της βιβλιοθήκης (αφού η συγκεκριμένη συνάρτηση
παίρνει ως ορίσματα 2 αντικείμενα Curve), ώστε να υπολογιστεί τελικά η ζητούμενη απόσταση μεταξύ των 2 αυτών χρονοσειρών με βάσει της μετρικής Continuous Frechet, αφού υπολογιστεί αυτή η απόσταση, επιστρέφεται από τη συνάρτηση
που αποτελεί την "διεπαφή" μας μεταξύ του αρχείου στο οποίο καλείται η συνάρτηση και της βιβλιοθήκης που μας δίνετε. 
Αξίζει να σημειωθεί πως για να δουλέψει "σωστά" η διεπαφή, δηλαδή να μπορεί να κληθεί από τo αρχείο hashTable/hashTableList/hashTableList.c 
(πέρα του ότι έγινε το απαραίτητο include: #include "../../Fred-master/src/my_interface.hpp") στο αρχείο κεφαλίδας my_interface.hpp 
δηλώσαμε την συνάρτηση ανάμεσα στα εξής προσδιοριστικά:

#ifdef __cplusplus
extern "C" {
#endif

// function definition 

#ifdef __cplusplus
}
#endif


Η μετρική Continuous Frechet στο ερώτημα αυτό εξυπηρετεί τους ίδιους σκοπούς που εξυπηρετούσε η L2 στην πρώτη εργασία (και στο πρώτο ερώτημα),
δηλαδή μέσω αυτή καταφέρνουμε ουσιαστικά να συγκρίνουμε τις χρονοσειρές μεταξύ τους, υπολογίζοντας την μεταξύ τους απόσταση και έτσι
βρίσκουμε τελικά τον πλησιέστερο γείτονα κάθε χρονοσειράς που υπάρχει στο query file.

Επιγραμματικά, οι αλλαγές που έγιναν στην υλοποίηση (σε σχέση με την υλοποίηση του LSH της προηγούμενης εργασίας) για το συγκεκριμένο ερώτημα αναλύθηκαν παραπάνω και είναι:
	
	1) Για την αποθήκευση των σημείων της χρονοσειράς εξακολουθείται να χρησιμοποιείται ένας μόνο πίνακας, καθώς λόγω της αναπαράστασης της χρονοσειράς στο R, η διάσταση του χρόνου απαλείφεται.
	2) Για να εισαχθεί στην δομή LSΗ ή για να γίνει αναζήτηση του πλησιέστερου γείτονα μέσο της δομής LSΗ, κάθε χρονοσειρά υφίσταται πρώτα filtering, έπειτα περνάει από την διαδικασία του snapping ώστε να μετατραπεί σε διάνυσμα και τέλος περνάει από την διαδικασία του minima and maxima.
	3) Η απόσταση μεταξύ των χρονοσειρών υπολογίζεται βάσει την μετρικής Continuous Frechet, η υλοποίηση της οποίας δίνεται έτοιμη μέσω μιας βιβλιοθήκης C++.
	4) Παρατηρήσεις σχετικά με την παράμετρο delta αναφέρονται στην συνέχεια.


↪ Διευκρινίσεις και παρατηρήσεις για LSH :
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
- Έχουμε επιλέξει το μέγεθος του κάθε hash table να είναι ίσο με numberOfVectors/16 , όπου numberOfVectors ο αριθμός των vectors στο αρχείο του dataset.
- Γίνεται όσο το δυνατόν περισσότερη εξοικονόμηση μνήμης. Για παράδειγμα, κάθε vector αποθηκεύεται μόνο μία φορά στην μνήμη και κάθε ένα hash table περιέχει έναν δείκτή στην θέση μνήμης αυτή. Έτσι δεν έχουμε καθόλου data duplication.
- Όσον αφορά την απόδοση, παρατηρούμε ότι το LSH είναι κατά πολύ γρηγορότερο από την εξαντλητική μέθοδο. Το ποσοστό της βελτίωσης του χρόνου εξαρτάται από το μέγεθος του αρχείου εισόδου. 
  Όσο μεγαλύτερο είναι το πλήθος των vectors/curves του input, τόσο γρηγορότερο είναι και το LSH σε σχέση με την εξαντλητική μέθοδο.


→ Επιλογή του w των συναρτήσεων h
- - - - - - - - - - - - - - - - - -
Στα εξής ερωτήματα χρησιμοποιούμε LSH:
	- A.i LSH for vectors
	- A.ii 
	- A.iii (LSH με L=1)
Δηλαδή για το hashing χρησιμοποιούνται συναρτήσεις H.
Ως γνωστών στο LSH οι συναρτήσεις H τις οποίες χρησιμοποιούν τα hash functions G έχουν μια μεταβλητή w.
Η τιμή του w καθορίζεται κατά την αρχή της εκτέλεσης και παραμένει σταθερή.
Με βάση την θεωρία, η βέλτιστη τιμή για το w προκύπτει εν συναρτήσει της μέσης διανυσματικής απόστασης των vectos/curves του input.
Έτσι, στην πρώτη εργασία το υπολογίζαμε με βάση αυτού.
Ωστόσο στην εργασία αυτή παρατηρήσαμε μια διαφορετική συμπεριφορά από το LSH και την τιμή του w.
Συγκεκριμένα παρατηρήσαμε πως ο υπολογισμός του w με βάση την μέση διανυσματική απόσταση δεν ήταν καθόλου αποδοτικός, έτσι που τα περισσότερα vectors/curves να έχουν διαφορετικά ID με αποτέλεσμα το πρόγραμμα να αδυνατεί να βρει κοντινότερους γείτονες καθώς προσπερνούσε όλα τα vectors/curves με βάση το Querying trick.
Αφαιρώντας το Querying trick οι χρόνοι πλησίαζαν αυτούς της εξαντλητικής μεθόδου, κάτι που καθιστούσε το LSH αχρείαστο.
Έπειτα από πειραματισμούς με τα αρχεία εισόδου, παρατηρήσαμε τα εξής:
	- Στο μικρό αρχείο nasdaq2017_LQ.csv (διάστασης 119) η μέση απόσταση των vectors/curves είναι περίπου 900 ενώ η βέλτιστη τιμή που παρατηρήσαμε για το w είναι 6.
	- Στο αρχείο εξέτασης nasd_input.csv (διάστασης 729) η μέση απόσταση των vectors/curves είναι περίπου 1000 ενώ η βέλτιστη τιμή που παρατηρήσαμε για το w είναι 200.
	- Στο μεγάλο αρχείο nasdaq2015_2017.csv (διάστασης 729) η μέση απόσταση των vectors/curves είναι περίπου 25000 ενώ η βέλτιστη τιμή που παρατηρήσαμε για το w είναι επίσης 200.
(Η μέση απόσταση των vectors/curves υπολογίζεται σε ένα υποσύνολο του input)
Από τα παραπάνω συμπεραίνουμε ότι η βέλτιστη τιμή του w δεν μπορεί να προκύψει με βάση την μέση απόσταση του input καθώς:
	- Για παρόμοια μέση απόσταση (900/1000) βλέπουμε πολύ μεγάλη διαφορά στο βέλτιστο w (6/200).
	- Για πολύ μεγάλη διαφορά μέσης απόστασης (1000/25000) βλέπουμε το ίδιο βέλτιστο w.
Για τον λόγο αυτό επεκτείναμε την μελέτη μας σχετικά με την εύρεση της βέλτιστης τιμής για το w. Έτσι, τόσο με βάση το αρχείο nasdaq2015_2017.csv όσο και με το nasd_input.csv κατασκευάσαμε νέα datasets τα οποία περιέχουν vectors/curves διαφορετικών διαστάσεων. Πιο συγκεκριμένα κατασκευάσαμε datasets για τις εξής διαστάσεις: 100, 180, 360, 520, 680 και 729 (το αρχικό datasets).

- Για τα ερωτήματα A.i και A.ii:
Έπειτα από πολλαπλές εκτελέσεις με διαφορετικές τιμές του w σε κάθε ένα από τα datasets καταλήξαμε στις εξής βέλτιστες τιμές για το w:
	- διάσταση 100 -> βέλτιστο w = 25
	- διάσταση 119 -> βέλτιστο w = 25
	- διάσταση 180 -> βέλτιστο w = 40
	- διάσταση 360 -> βέλτιστο w = 50
	- διάσταση 520 -> βέλτιστο w = 100
	- διάσταση 680 -> βέλτιστο w = 150
	- διάσταση 729 -> βέλτιστο w = 200
Από τα παραπάνω συμπεραίνουμε πως η τιμή του w σχετίζεται άμεσα με την μέγεθος των vectors/curves του input.
Έτσι, βασιζόμενοι στα παραπάνω αποτελέσματα της μελέτης μας, κατασκευάσαμε μια συνάρτηση (wValueCalculation στο αρχείο mainLSH.c) η οποία αναθέτει την βέλτιστη τιμή στο w με βάση το μέγεθος των vectors/curves του input.
Χρησιμοποιώντας αυτήν την συνάρτηση παρατηρήσαμε πολύ καλή απόδοση ανεξαιρέτως του input (δηλαδή του μεγέθους των vectors/curves ή το πλήθος αυτών).

- Για το ερώτημα Α.iii:
Για το τρίτο ερώτημα (Continuous Frechet) παρατηρήσαμε μεγαλύτερες βέλτιστες τιμές για το w.
Αυτό οφείλεται στην ύπαρξη ενός μοναδικού hash table σε αντίθεση με τα δύο πρώτα ερωτήματα στα οποία έχουμε L διαφορετικά hash tables.
Λόγω αυτού έχουμε καλύτερη απόδοση όταν τα curves είναι συσσωρευμένα σε λιγότερα buckets του hash table, καθώς με μικρότερη συσσώρευση (και ειδικά για μικρό αριθμό input curves) η μέθοδος πολλές φορές αδυνατούσε να βρει κοντινούς γείτονες.
Επίσης, η μεγαλύτερη αυτή συσσώρευση δεν είχε αρνητική επίδραση στον χρόνο λόγω του Querying trick που χρησιμοποιούμε. Δηλαδή η χρονική απόδοση του προγράμματος εξακολουθεί να είναι πολύ καλή.
Πιο συγκεκριμένα έπειτα από τις εκτελέσεις με διαφορετικές τιμές του w σε κάθε ένα από τα datasets καταλήξαμε στις εξής βέλτιστες τιμές για το w: 
	- διάσταση 100 -> βέλτιστο w = 100
	- διάσταση 119 -> βέλτιστο w = 120
	- διάσταση 180 -> βέλτιστο w = 150
	- διάσταση 360 -> βέλτιστο w = 350
	- διάσταση 520 -> βέλτιστο w = 530
	- διάσταση 680 -> βέλτιστο w = 700
	- διάσταση 729 -> βέλτιστο w = 730
Παρατηρούμε ότι η βέλτιστη τιμή του w είναι αντίστοιχη με την διάσταση των curves.
Έτσι, βασιζόμενοι στα παραπάνω , κατασκευάσαμε μια συνάρτηση (wValueCalculationContinuous στο αρχείο mainLSH.c) η οποία αναθέτει την βέλτιστη τιμή στο w με βάση το μέγεθος των vectors/curves του input. 
Δηλαδή σε κάθε περίπτωση θέτει w = διάσταση.
Χρησιμοποιώντας αυτήν την συνάρτηση παρατηρήσαμε πολύ καλή απόδοση ανεξαιρέτως του input (δηλαδή του μεγέθους των vectors/curves ή το πλήθος αυτών).

→ Παράμετρος delta
- - - - - - - - - - - - - - - - - -
Τα ερωτήματα A.ii και A.iii, στα οποία εργαζόμαστε πάνω σε curves, χρησιμοποιούν την παράμετρο delta κατά την διαδικασία του snapping.
Η παράμετρος αυτή μπορεί να δοθεί από τον χρήστη κατά την εκτέλεση. Διαφορετικά χρησιμοποιείται η default τιμή η οποία έχουμε οριστεί.
Έπειτα από μελέτη σε διαφορετικά inputs παρατηρήσαμε καλύτερη απόδοση του προγράμματος όταν η τιμή του delta κυμαίνεται στο διάστημα [1,2].
Σαν βέλτιστη τιμή καταλήξαμε στην τιμή 1, την οποία έχουμε θέσει και ως default τιμή για το delta.






Μέρος Β - Clustering
————————————————————————————————
Το δεύτερο μέρος της εργασίας αφορά την συσταδοποιήση των χρονοσειρών με τους ακόλουθους 5 συνδυασμούς:
	1. Αρχικοποίηση: K-means++, Ανάθεση: Lloyd's, Update: υπολογισμός μέσης χρονοσειράς ως διάνυσμα (χρήση της L2 αποκλειστικά)
	2. Αρχικοποίηση: K-means++, Ανάθεση: Lloyd's, Update: υπολογισμός μέσης χρονοσειράς ως καμπύλη (χρήση της Discrete-Frechet Mean Curve of n curves )
	3. Αρχικοποίηση: K-means++, Ανάθεση: Reverse Assignment with LSH, Update: υπολογισμός μέσης χρονοσειράς ως διάνυσμα (χρήση της L2 αποκλειστικά)
	4. Αρχικοποίηση: K-means++, Ανάθεση: Reverse Assignment with LSH, Update: υπολογισμός μέσης χρονοσειράς ως καμπύλη (χρήση της Discrete-Frechet Mean Curve of n curves)
	5. Αρχικοποίηση: K-means++, Ανάθεση: Reverse Assignment with HyperCube, Update: υπολογισμός μέσης χρονοσειράς ως διάνυσμα (χρήση της L2 αποκλειστικά)

Έτσι, ανάλογα με τις παραμέτρους που δίνει ο χρήστης στην γραμμή εντολών εκτελείται κάθε φορά ο ζητούμενος συνδυασμός.
Οι υλοποιήσεις του αλγορίθμου της αρχικοποιήσης K-means++ και των συνδυασμών: 1, 3, και 5 είναι οι ίδιες με αυτές τις 1ης εργασίας καθώς οι χρονοσειρές σε αυτές τις περιπτώσεις
αντιμετωπίζονται ως διανύσματα, συνεπώς δεν θα αναλυθούν στην συνέχεια.
Έχουμε προσθέσει στα αρχεία το README της προηγούμενης εργασίας προκειμένου να μπορείτε να ανατρέξετε εύκολα.
————————————————————————————————

→ Lloyd's, 
  Update: υπολογισμός μέσης χρονοσειράς ως καμπύλη (χρήση της Discrete-Frechet Mean Curve of n curves )
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Η βασική υλοποίηση είναι ίδια με αυτήν του Lloyds για διανύσματα της πρώτης εργασίας.
Οι μόνες διαφορές είναι οι εξής:
	- Kάθε χρονοσειρά αναπαρίσταται ως πολυγωνική καμπύλη, επομένως δεσμεύουμε για κάθε χρονοσειρά
	  στo αντίστοιχο struct vec_node τον πίνακα (double* times) για την αποθήκευση του χρόνου.
	- Οι υπολογισμοί των αποστάσεων μεταξύ καμπυλών γίνεται μέσω της Discrete Frechet, η υλοποίηση της οποίας εξηγήθηκε παραπάνω.
	- Στην διαδικασία ενημέρωσης των centroids υπολογίζεται η μέση καμπύλη μεταξύ όλων των καμπυλών που έχουν ανατεθεί στο κάθε centroid (mean curve of n curves). 
	  Ο υπολογισμός της μέσης καμπύλης γίνεται μέσω της συνάρτησης meanCurveBetween2Curves. 
	  Η διαδικασία εύρεσης του mean curve εξηγείται αναλυτικά στην συνέχεια.
	- Έπειτα από τον υπολογισμό κάθε mean curve, εφαρμόζεται filtering σε αυτό έτσι ώστε να μειωθεί το πλήθος των σημείων του. Εξηγείται επίσης αναλυτικά στην συνέχεια.


→ Reverse Assignment with LSH,
  Update: υπολογισμός μέσης χρονοσειράς ως καμπύλη (χρήση της Discrete-Frechet Mean Curve of n curves)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
Η βασική υλοποίηση είναι ίδια με αυτήν του Reverse Assignment with LSH για διανύσματα της πρώτης εργασίας.
Οι μόνες διαφορές είναι οι εξής:
	- Kάθε χρονοσειρά αναπαρίσταται ως πολυγωνική καμπύλη, επομένως δεσμεύουμε για κάθε χρονοσειρά
	  στo αντίστοιχο struct vec_node τον πίνακα (double* times) για την αποθήκευση του χρόνου.
	- Οι υπολογισμοί των αποστάσεων μεταξύ καμπυλών γίνεται μέσω της Discrete Frechet, η υλοποίηση της οποίας εξηγήθηκε παραπάνω.
	- Στην διαδικασία ενημέρωσης των centroids υπολογίζεται η μέση καμπύλη μεταξύ όλων των καμπυλών που έχουν ανατεθεί στο κάθε centroid (mean curve of n curves).
	  Ο υπολογισμός της μέσης καμπύλης γίνεται μέσω της συνάρτησης treeFindMeanCurve. 
	  Η διαδικασία εύρεσης του mean curve εξηγείται αναλυτικά στην συνέχεια.
	- Έπειτα από τον υπολογισμό κάθε mean curve, εφαρμόζεται filtering σε αυτό έτσι ώστε να μειωθεί το πλήθος των σημείων του. Εξηγείται επίσης αναλυτικά στην συνέχεια.
	- Η δομή στην οποία αποθηκεύονται τα curves του input είναι η ίδια με αυτήν του ερωτήματος A.ii. Δηλαδή για την εισαγωγή ενός curve στην δομή ακολουθείται η ίδια ακριβώς διαδικασία με αυτήν που περιγράφηκε στην αντίστοιχη παράγραφο του ερωτήματος A.ii. 
	  Αντίστοιχα για ένα query, στην περίπτωση μας range search για ένα centroid, ακολουθείται η ίδια διαδικασία με τα queries του ερωτήματος A.ii. 
	  Η μόνη διαφορά είναι ότι τελικά αντί για την συνάρτηση εύρεσης κοντινότερου γείτονα, καλείται η συνάρτηση του range search που υλοποιήσαμε στην πρώτη εργασία. 
	  Λόγω των ελάχιστων διαφορών μεταξύ των μεθόδων/συνδιασμών 3 και 4 υλοποιούνται από την ίδια συνάρτηση clusteringLSH. Οι διαφορές διαχωρίζονται με if statements.
	  Πιο συγκεκριμένα, από πλευράς κώδικα οι αλλαγές είναι οι εξής:
	- Η διάσταση του vector V των συναρτήσεων Η. Στην μέθοδο 3 η διάσταση του V είναι ίση με dim (όπως στην εργασία 1), ενώ στην μέθοδο 4 είναι ίση με 2*dim καθώς το διάνυσμα που προκύπτει έπειτα από το snapping ενός curve είναι 2*dim. Λέγοντας dim εννοούμε την διάσταση του input.
	- Στην μέθοδο 4 χρειάζεται να ορίσουμε τα t των αντίστοιχων grids.
	- Στην μέθοδο 3 η εισαγωγή των vectors στο LSH γίνεται μέσω της συνάρτησης insertToLSH (της πρώτης εργασίας), ενώ στην μέθοδο 4 τα curves εισάγονται μέσω της insertTimeSeriesToLSH που υλοποιήθηκε στο ερώτημα A.ii.
	- Για τον υπολογισμό του update των centroids, στην μέθοδο 3 καλείται η συνάρτηση htMeanOfCluster (της πρώτης εργασίας), ενώ στην μέθοδο 4 καλείται η treeFindMeanCurve για τον υπολογισμό της μέσης καμπύλης και στην συνέχεια η συνάρτηση filterMeanCurve για το filtering αυτής.
	- Για το range search στο LSH, στην μέθοδο 3 καλείται η radiusNeigborsClustering (της πρώτης εργασίας), ενώ στην μέθοδο 4 καλείται η radiusNeigborsClusteringTimeSeries.


→ Yπολογισμός μέσης χρονοσειράς ως καμπύλη μεταξύ δυο καμπυλών (Mean curve of 2 curves)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
Ο υπολογισμός της μέσης χρονοσειράς ως καμπύλη μεταξύ δυο καμπυλών γίνεται μέσω της συνάρτησης meanCurveBetween2Curves του αρχείου FrechetDistance/discreteFrechet.c.
Για την εύρεση της μέσης καμπύλης μεταξύ δύο καμπυλών, αρχικά υπολογίζουμε την απόσταση Discrete Frechet μεταξύ τους.
Κατά τον υπολογισμό της απόστασης, αποθηκεύουμε το optimal path.
Αυτό υλοποιείται από την συνάρτηση discreteFrechet_optimalPath η οποία σε αντίθεση με την συνάρτηση discreteFrechet υπολογίζει και το optimal path ταυτόχρονα με την απόσταση.
Όσον αφορά την εύρεση του optimal path, για κάθε στοιχείο του πίνακα αποθηκεύουμε από ποιο προέκυψε η βέλτιστη τιμή.
Πιο συγκεκριμένα κατά τον υπολογισμού ενός στοιχείου i,j του πίνακα, ελέγχουμε πιο από τα τρία σημεία [i-1][j], [i-1][j-1], [i][j-1] έχει την μικρότερη τιμή.
Έτσι αποθηκεύουμε το αντίστοιχο index, σαν optimal "βήμα" του συνολικού optimal path.
Για την αποθήκευση των αντίστοιχων indexes του optimal path, έχουμε ορίσει μια δομή με όνομα Index η οποία περιέχει δύο ακεραίους για το i και το j αντίστοιχα.
Δηλαδή σε κάθε στοιχείο του δισδιάστατου πίνακα, αντιστοιχεί ένα αντικείμενο Index το οποίο δείχνει το index του γειτονικού σημείου από το οποίο προέκυψε η βέλτιστη τιμή.
Επίσης, ισχύει ότι αν i=0 (δηλαδή για την πρώτη στήλη) το index του optimal path είναι το [0,j-1] καθώς μόνο από το προηγούμενο σημείο της πρώτης στήλης μπορούμε να καταλήξουμε εκεί.
Αντίστοιχα αν j=0 το index του optimal path είναι [i-1,j].
Έχοντας υπολογίσει την απόσταση Discrete Frechet, δηλαδή έχοντας συμπληρώσει ολόκληρο τον δισδιάστατο πίνακα, έχουμε υπολογίσει και το optimal path.
Για την εύρεση αυτού ξεκινάμε από το τελευταίο σημείο του πίνακα [i-1,j-1] το οποίο περιέχει και την τελική απόσταση, και ακολουθούμε τα αντίστοιχα Index τα οποία αντιστοιχούν στο κάθε σημείο του πίνακα.
Ακολουθούμε αυτήν την διαδικασία έως ότου καταλήξουμε στο πρώτο στοιχείο του πίνακα, δηλαδή το [0,0].
Αποθηκεύουμε αυτά τα indexes σε έναν πίνακα από Index, και έτσι τελικά έχουμε το optimal path, το οποίο επιστρέφεται από την συνάρτηση discreteFrechet_optimalPath.
Στην συνέχεια, έχοντας το optimal path μπορούμε εύκολα να υπολογίσουμε το mean curve.
Όπως είπαμε, το optimal path είναι μια σειρά από δυάδες (i,j). Το i αντιστοιχεί στο πρώτο curve ενώ το j στο δεύτερο.
Για κάθε δυάδα (i,j) υπολογίζουμε το αντίστοιχο σημείο του mean curve ως εξής (vector1[i]+vector2[j])/2.
Αφού δουλεύουμε στις δύο διαστάσεις (έστω x,y) ο παραπάνω τύπος αντιστοιχεί στο εξής (x,y) = ( (vector1_x[i]+vector2_x[j])/2 , (vector1_y[i]+vector2_y[j])/2)
Υπολογίζοντας κάθε σημείο του mean curve με βάση το παραπάνω, έχουμε τελικά υπολογίζει το mean curve μεταξύ δύο καμπυλών το οποίο και επιστρέφεται από την συνάρτηση meanCurveBetween2Curves.


→ Yπολογισμός μέσης χρονοσειράς ως καμπύλη μεταξύ n καμπυλών (Mean curve of n curves)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
Για τον υπολογισμό της μέσης καμπύλης μεταξύ n καμπυλών, αρχικά χρειαζόμαστε ένα δυαδικό δέντρο.
Η υλοποίηση του βρίσκεται στο αρχείο BinaryTree/binaryTree.c.
Κάθε κόμβος του δέντρου περιέχει ένα αντικείμενο της κλάσης Vector, δηλαδή ένα curve και προφανώς δύο δείκτες για τα δύο "παιδιά" του.
Έχοντας όλες τις καμπύλες οι οποίες έχουν ανατεθεί σε ένα κεντροιδές, αρχικά θέλουμε να κατασκευάσουμε ένα δεντρο με βάση αυτές.
- Στην μέθοδο Lloyds οι καμπύλες ενός κεντροιδούς είναι αποθηκευμένες σε μια λίστα.
- Στην μέθοδο Reverse Assignment with LSH οι καμπύλες ενός κεντροιδούς είναι αποθηκευμένες σε ένα hash table.
Έτσι, έχουμε υλοποιήσει δύο συναρτήσεις οι οποίες κατασκευάζουν ένα δέντρο μέσω καμπυλών οι οποίες είναι αποθηκευμένες σε μια λίστα και σε ένα hash table αντίστοιχα.
Τα ονόματα των συναρτήσεων αυτών είναι createTreeFromList(...) και createTreeFromHt(...) και η υλοποίηση τους βρίσκεται στο αρχείο BinaryTree/binaryTree.c.
Έχοντας n καμπύλες (αποθηκευμένες είτε σε λίστα είτε σε hash table) κατασκευάζουμε ένα δέντρο το οποίο:
	- Περιέχει τις καμπύλες με τυχαία σειρά στους κόμβους φύλλα του
	- Οι εσωτερικοί κόμβοι του δέντρου αρχικά είναι κενοί δηλαδή δεν περιέχουν καμία καμπύλη.
Εφόσον έχουμε n καμπύλες αποθηκευμένες στα φύλλα του δέντρου, το ύψος του δέντρου είναι: ceil( log2( n ) ).
Στην συνέχεια εφαρμόζουμε Depth First search, έτσι έτσι ώστε ξεκινώντας από τα φύλα του δέντρου να υπολογίσουμε την τελική μέση καμπύλη η οποία μετά το τέλος του DFS θα είναι αποθηκευμένη στην ρίζα του δέντρου.
Για κάθε κόμβο του δέντρου εφαρμόζουμε μία από τις εξής συνθήκες:
	- Αν ο κόμβος έχει δύο παιδιά τα οποία περιέχουν και τα δύο από μία καμπύλη τότε υπολογίζεται το mean curve μεταξύ των δύο καμπυλών των παιδιών μέσω της συνάρτησης meanCurveBetween2Curves. Το mean curve που θα προκύψει, αποθηκεύεται στον κόμβο αυτό.
	- Αν μόνο ένα εκ των δύο παιδιών περιέχει μια καμπύλη, τότε στον κόμβο ανατίθεται η καμπύλη αυτό του παιδιού.
	- Αν κανένα από τα δύο παιδιά δεν περιέχει καμπύλη, τότε ο κόμβος παραμένει κενός.
Εφαρμόζοντας DFS και σε κάθε κόμβο, ένα από τα παραπάνω βήματα ανάλογα με την συνθήκη που ισχύει, τελικά, προκύπτει η μέση καμπύλη των n καμπυλών και είναι αποθηκευμένη στην ρίζα του δέντρου.
Την παραπάνω διαδικασία την εκτελεί η συνάρτηση treeFindMeanCurve(...) του αρχείου BinaryTree/binaryTree, η οποία τελικά επιστρέφει το mean curve που προέκυψε.

→ Mean curve Filtering 
- - - - - - - - - - - - -
Ως γνωστών, με βάση την θεωρία, ένα mean curve το οποίο προκύπτει από n curves έχει αρκετά μεγαλύτερο μέγεθος σε σχέση με τις καμπύλες. Συγκεκριμένα όσο μεγαλύτερος είναι ο αριθμός n τόσο μεγαλώνει και το μέγεθος του mean curve.
Λόγω του μεγάλου μεγέθους των mean curves που προκύπτουν για κάθε κεντροιδές παρουσιάζονται τα εξής προβλήματα:
	- Αυξάνεται αρκετά ο χρόνος εκτέλεσης καθώς έχουμε συνεχείς υπολογισμού αποστάσεων μεταξύ ενός κεντροιδούς (δηλαδή mean curve) 
          και καμπυλών των δεδομένων. Λόγω του μεγάλου μεγέθους της καμπύλης του centroid, κάθε υπολογισμός απόστασης είναι αρκετά χρονοβόρος. 
	  Αυτό ισχύει τόσο για την μέθοδο Lloyds όσο και για το LSH (μέθοδοι 2 και 4).
	- Λόγω του πολύ μεγάλου μεγέθους του curve παρατηρήσαμε πως στο LSH (μέθοδος 4) δεν είναι καθόλου αποδοτικό το Querying trick με βάση το ID. 
	  Συγκεκριμένα, για το mean curve δεν προέκυπτε ίδιο ID με σχεδόν κανένα από τα curves του input, με αποτέλεσμα στο range search να αγνοούνται σχεδόν όλα τα curves και να μην βρίσκει σχεδόν κανέναν γείτονα. 
	  Αφαιρώντας το Querying trick, το range search γινόταν αρκετά χρονοβόρο, καθιστώντας την μέθοδο Reverse Assignment with LSH αχρείαστη καθώς είχε χειρότερη απόδοση από την μέθοδο Lloyds.
	- Τέλος, κατά το hashing του LSH προέκυπτε το πρόβλημα εισόδου διαφορετικών μεγεθών. Πιο συγκεκριμένα το LSH χρησιμοποιεί συναρτήσεις H για το hashing οι οποίες με την σειρά τους περιέχουν κάποια διανύσματα V προκαθορισμένου μεγέθους. 
	  Έτσι, το μέγεθος του input ποικίλει και ταυτόχρονα το μέγεθος των διανυσμάτων V των Η είναι προκαθορισμένο το οποίο έρχεται σε αντίθεση με την θεωρία του LSH. 
	  Μια λύση που δοκιμάσαμε ήταν να ορίσουμε τα διανύσματα V να έχουν ένα προκαθορισμένο μεγάλο μέγεθος μέσω ενός άνω φράγματος. 
	  Στην συνέχεια, ανάλογα με το μέγεθος του διανύσματος εισόδου θα χρησιμοποιούνταν μόνο οι αντίστοιχες πρώτες συντεταγμένες του V 
	  για τον υπολογισμό του εσωτερικού γινομένου. Ωστόσο, μέσω αυτής της "λύσης" το hashing αποδείχθηκε μη αποδοτικό (και ταυτόχρονα εξακολουθούσαν να υπάρχουν τα δύο πρώτα προβλήματα).
          Έτσι η λύση αυτή απορρίφθηκε.

Ο τρόπος που επιλέξαμε να επιλύσουμε τα παραπάνω προβλήματα είναι να εφαρμόζουμε filtering στo mean curve.
Πιο συγκεκριμένα, αφού προκύψει το mean curve εφαρμόζουμε filttering έτσι ώστε τελικά το mean curve να έχει ίδιο μέγεθος με τα curves του input.
Το filtering αυτό υλοποιείται από την συνάρτηση filterMeanCurve του αρχείου LSH/lsh.c.
Αναλυτικότερα, η συνάρτηση αυτή εφαρμόζει επαναλαμβανόμενο filtering με αυξανόμενο epsilon έως ότου το curve μειωθεί στο επιθυμητό μήκος. Δηλαδή:
	- Ξεκινάμε με μια μικρή τιμή για το epsilon.
	- Εφαρμόζουμε filtering.
	- Αυξάνουμε το eplilon και εφαρμόζουμε ξανά το βήμα 2 (δηλαδή filtering).
	- Η διαδικασία αυτή σταματά μόλις το curve μειωθεί στο επιθυμητό μήκος.

Η επιλογή για το επαναλαμβανόμενο filtering με αυξανόμενο epsilon έγινε έτσι ώστε να απαλείφονται ομοιόμορφα σημεία κατά μήκος του curve και 
όχι συσσωρευμένα σημεία στην αρχή του curve (το οποίο θα γινόταν αν εφαρμόζαμε μόνο μια φορά filtering με πολύ μεγάλο epsilon),
Έτσι "χάνουμε" όσο το δυνατόν λιγότερη πληροφορία από την καμπύλη.
Η συνάρτηση αυτή διαφέρει από αυτήν που χρησιμοποιήθηκε για το filtering στο ερώτημα A.iii λόγω του επαναλαμβανόμενου filtering που πραγματοποιείται.

Εφαρμόζοντας το παραπάνω filtering στα mean curves τα οποία προκύπτουν για κάθε cluster τόσο στην μέθοδο Lloyds όσο και στην LSH 
λύνονται όλα τα παραπάνω προβλήματα που αναφέρθηκαν. Παρατηρήσαμε σημαντική μείωση στον χρόνο εκτέλεσης και ταυτόχρονα πολύ καλή συνολική απόδοση των μεθόδων.

→ Επιλογή του w των συναρτήσεων h
- - - - - - - - - - - - - - - - - -
Όσον αφορά την τιμή για το w το οποίο χρησιμοποιούν τα hash functions tou LSH (δηλαδή στις μεθόδους 3 και 4) ακολουθήσαμε την ίδια διαδικασία μελέτης η οποία περιγράφηκε αναλυτικά στο πρώτο μέρος της εργασίας.
Παρατηρήσαμε καλύτερη απόδοση χρησιμοποιώντας μεγαλύτερες τιμές για το w σε σχέση με αυτές που χρησιμοποιούνται στο πρώτο μέρος.
Αυτό καθώς χρησιμοποιώντας μεγαλύτερο w, συγκεντρώνονται περισσότερα σημεία στα ίδια buckets με αποτέλεσμα να προκύπτουν περισσότεροι γείτονες από κάθε range search κάνοντας έτσι το Reverse Assignment with LSH αποδοτικότερο.
Συγκεκριμένα παρατηρήσαμε τις εξής βέλτιστες τιμές για το w με βάση το μέγεθος των vectors/curves του input:
	- διάσταση 100 -> βέλτιστο w = 200
	- διάσταση 119 -> βέλτιστο w = 200
	- διάσταση 180 -> βέλτιστο w = 300
	- διάσταση 360 -> βέλτιστο w = 400
	- διάσταση 520 -> βέλτιστο w = 500
	- διάσταση 680 -> βέλτιστο w = 500
	- διάσταση 729 -> βέλτιστο w = 600
Έτσι, βασιζόμενοι στα παραπάνω αποτελέσματα της μελέτης μας, κατασκευάσαμε μια συνάρτηση (wValueCalculation στο αρχείο mainLSH.c) η οποία αναθέτει την βέλτιστη τιμή στο w με βάση το μέγεθος των vectors/curves του input.
Χρησιμοποιώντας αυτήν την συνάρτηση παρατηρήσαμε πολύ καλή απόδοση ανεξαιρέτως του input (δηλαδή του μεγέθους των vectors/curves ή το πλήθος αυτών).

→ Silhouettes
- - - - - - - - - - - - - - - - - 
Ο τρόπος υπολογισμού των silhouettes είναι ακριβώς ίδιος με αυτόν της πρώτης εργασίας, έτσι δεν αναλύεται ξανά.
Η μόνη διαφορά είναι πως στις περιπτώσεις 2 και 4 (δηλαδή όταν εργαζόμαστε με καμπύλες) ο υπολογισμός των αποστάσεων γίνεται χρησιμοποιώντας Discrete Frechet distance. 
Στις υπόλοιπες περιπτώσεις όπου δουλεύουμε με vectors ο υπολογισμός των αποστάσεων γίνεται μέσω της μετρικής L2.
Λόγω του αρκετού χρόνου που χρειάζεται για τον υπολογισμό των silhouettes, δεν υπολογίζονται by default κατά την εκτέλεση.
Εάν θέλουμε να υπολογιστούν πρέπει να εκτελέσουμε το πρόγραμμα δίνοντας την επιπλέον παράμετρο -silhouette στο command line.

→ Παράμετρος delta
- - - - - - - - - - - - - - - - - -
Όσον αφορά την παράμετρο delta η οποία χρησιμοποιείται κατά το snapping των curves στην μέθοδο 4, παρατηρήσαμε αντίστοιχα αποτελέσματα με αυτά του πρώτου μέρους (δηλαδή στα ερωτήματα Α.ii A.iii)
Συγκεκριμένα παρατηρήσαμε καλύτερη απόδοση του προγράμματος όταν η τιμή του delta κυμαίνεται στο διάστημα [1,2].
Σαν βέλτιστη τιμή καταλήξαμε στην τιμή 1, την οποία έχουμε θέσει και ως default τιμή για το delta.
Επίσης προσθέσαμε την παράμετρο -delta και στο εκτελέσιμο του Β μέρους έτσι ώστε να μπορεί να δοθεί κάποια συγκεκριμένη τιμή από την χρήση. Η παράμετρος αυτή είναι αντίστοιχη με αυτήν που ζητείται από την εκφώνηση για το πρώτο μέρος της εργασίας. Αν δεν δοθεί τότε χρησιμοποιείται η default τιμή (= 1).


Unit Tests
————————————————————————————————

Όπως και προαναφέρθηκε παραπάνω τα unit tests πραγματοποιήθηκαν μέσω της βιβλιοθήκης CUnit στο αρχείο unitTesting.c.
Καταφέρνοντας να επαληθεύσουμε την ορθή λειτουργία των εξής συναρτήσεων:

	- Υπολογισμός απόστασης Discrete Frechet μεταξύ δύο καμπυλών: discreteFrechet(...)-> μέσω της συνάρτησης test_discreteFrechet(...)
	- Εύρεση μέσης καμπύλης μεταξύ δύο καμπυλών: meanCurveBetween2Curves(...)-> μέσω της συνάρτησης test_meanCurveBetween2Curves(...)
	- Hash Function G του LSH: computeG(...) -> μέσω της συνάρτησης test_gFunction(...)
	

Στην συνάρτηση test_discreteFrechet(...) δημιουργήσαμε τις ακόλουθες 2 χρονοσειρές:

	timeSeries1-> [ [0,1] [0,2] [0,3] [0,4] [0,5] ]

	timeSeries2-> [ [1,1] [1.1,2] [1.2,3] [1.1,4] [1,5] ]

και καλούμε την συνάρτηση discreteFrechet(...), δίνοντας αυτές ως ορίσματα, προκειμένου να υπολογιστεί η Discrete Frechet Distance.
Υπολογίσαμε "στο χαρτί", εφαρμόζοντας την συγκεκριμένη μετρική, πως η απόσταση μεταξύ των καμπυλών είναι ίση με 1.2 .
Συγκεκριμένα ο πίνακας που προέκυψε από τον υπολογισμό στο χαρτί είναι:
[1,     1.486, 2.332, 3.195, 4.123]
[1.414, 1.1,   1.562, 2.282, 3.162]
[2.236, 1.486, 1.2,   1.486, 2.236]
[3.162, 2.282, 1.562, 1.2,   1.414]
[4.123, 3.195, 2.332, 1.486, 1.2  ]
Συνεπώς, αυτή πρέπει να είναι και η τιμή επιστροφής της συνάρτησης discreteFrechet(...), δοθέντων αυτών των 2 χρονοσειρών ως ορίσματα , ώστε το συγκεκριμένο unit test να γίνει passed.
Φυσικά και η αντίστοιχη συνάρτηση επιστρέφει το αναμενόμενο αποτέλεσμα, διαβεβαιώνοντάς μας πως η υλοποίηση μας για τον υπολογισμό της Discrete Frechet Distance είναι σωστή.


Στην συνάρτηση test_meanCurveBetween2Curves(...), ομοίως με πριν, δημιουργήσαμε τις ακόλουθες 2 χρονοσειρές:

	timeSeries1-> [ [0,1] [0,2] [0,3] [0,4] [0,5] ]

	timeSeries2-> [ [1,1] [1.1,2] [1.2,3] [1.1,4] [1,5] ]

Υπολογίσαμε "στο χαρτί", εφαρμόζοντας την διαδικασία που περιγράφεται παραπάνω (Δυναμικός προγραμματισμός και Backtracking),
πως το mean curve που προκύπτει μεταξύ των καμπυλών είναι το εξής: [ [0.5,1] [0.55,2] [0.6,3] [0.55,4] [0.5,5] ].
Το mean curve μπορεί εύκολα να υπολογιστεί και "με το μάτι", καθώς λόγω των μηδενικών τιμών y της πρώτης καμπύλης αλλά και των ίδιων τιμών x και στις δύο καμπύλες, το optimal path που προκύπτει είναι κάνοντας "1 βήμα" κάθε φορά και στις δύο καμπύλες. Δηλαδή αντιστοιχεί στην διαγώνιο του πίνακα που παρουσιάστηκε παραπάνω. Έτσι, εύκολα προκύπτει η παραπάνω μέση καμπύλη.
Συνεπώς, αυτή πρέπει να είναι και η χρονοσειρά που επιστρέφει η συνάρτηση meanCurveBetween2Curves(...), δοθέντων αυτών των 2 χρονοσειρών ως ορίσματα , ώστε το συγκεκριμένο unit test να γίνει passed.
Φυσικά και η αντίστοιχη συνάρτηση επιστρέφει την αναμενόμενη χρονοσειρά, διαβεβαιώνοντάς μας πως η υλοποίηση μας για τον υπολογισμό της mean curve μεταξύ 2 χρονοσειρών είναι σωστή.


Στην συνάρτηση test_gFunction(...) δημιουργήσαμε τα ακόλουθα 2 παραπλήσια διανύσματα (σχεδόν ίδια)σ:

	vector1-> [ 3.53, 7.56, 13.34, 54.33, 10.02 ]

	vector2-> [ 3.4, 7.7, 13.5, 54.5, 10 ]

Είναι λογικό πως η τιμή της g function, η οποία χρησιμοποιείται ως hash function στο LSH, πρέπει να είναι η ίδια για 
2 παραπλήσια διανύσματα όπως τα παραπάνω.
Συνεπώς, η κλήση της αντίστοιχης συνάρτησης για τον υπολογισμό της ίδιας g function (γίνεται μέσω της getValueOfFirstGFun(...)
η οποία υπολογίζει αποκλειστικά την τιμή της g function που αντιστοιχεί στο 1ο hash table του LSH) και για τα 2 αυτά διανύσματα πρέπει 
να επιστρέψει την ίδια τιμή, ώστε το συγκεκριμένο unit test να γίνει passed.
Φυσικά και η κλήση της συνάρτησης αυτής επιστρέφει την αναμενόμενη τιμή και για τα 2 διανύσματα, 
διαβεβαιώνοντάς μας πως η υλοποίηση μας για την αρχικοποιήση και τον υπολογισμό της g function (επομένως και αυτή για τις h functions
 που χρησιμoποιεί) είναι σωστή.