README-Project1.txt

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

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


.
├── Clustering
│   ├── clusterHelpingFuns.c
│   ├── clusterHelpingFuns.h
│   ├── clustering.c
│   ├── clustering.h
│   ├── kmeansPlusPlus.c
│   └── kmeansPlusPlus.h
│  
├── 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
├── mainLSH.c
├── mainCluster.c
├── mainCube.c
└── cluster.conf

------------------------------------------------------------------------------------

► Γενικά:

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

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

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

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

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

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

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

				► ./demolsh –i <input file> –q <query file> –k <int> -L <int> -ο <output file> -Ν <number of nearest> -R <radius>
				  ( π.χ. ./demolsh -i input_small_id -q query_small_id -o outputLSH -k 6 -L 8 -N 3 -R 300 )

				► ./cube –i <input file> –q <query file> –k <int> -M <int> -probes <int> -ο <output file> -Ν <number of nearest> -R <radius>
				  ( π.χ. ./cube -i input_small_id -q query_small_id -o outputCube -k 6 -M 8 -probes 3 -N 3 -R 300 )

				► ./cluster –i <input file> –c <configuration file> -o <output file> -complete <optional> -m <method: Classic OR LSH or Hypercube>
				  ( π.χ. ./cluster -i input_small_id -c cluster.conf -o outputCluster -m Classic -complete)

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

Μέρος Α - Κοντινότεροι Γείτονες
————————————————————————————————

Για το πρώτο μέρος της εργασίας έχουμε υλοποιήσει τους αλγορίθμους LSH και τυχαίας προβολής στον υπερκύβο για την εύρεση των πλησιέστερων γειτόνων.
Οι δύο μέθοδοι δέχονται τις αντίστοιχες παραμέτρους που περιγράφονται στην εκφώνηση καθώς και δύο αρχεία εισόδου.
Ένα αρχείο με το σύνολο των δεδομένων καθώς και ένα αρχείο με το σύνολο αναζήτησης.
Με βάση το αρχείο dataset, αρχικοποιείται η αντίστοιχη δομή LSH/HyperCube και εισάγονται όλα τα δεδομένα σε αυτήν. Στην συνέχεια, με βάση το αρχείο του συνόλου αναζήτησης εκτελείται διαδοχικά για κάθε ένα σημείο που περιέχεται στο αρχείο:
- Εύρεση των πραγματικών Κ κοντινότερων γειτόνων χρησιμοποιώντας την εξαντλητική μέθοδο, δηλαδή συγκρίνοντας το σημείο αναζήτησης με κάθε ένα σημείο του dataset.
- Εύρεση των προσεγγιστικών K κοντινότερων γειτόνων χρησιμοποιώντας την αντίστοιχη δομή LSH/HyperCube.
- Εύρεση των σημείων εντός του δοθέντος radius (Range Search) χρησιμοποιώντας την αντίστοιχη δομή LSH/HyperCube.

Κατά την διάρκεια αναζήτησης των πλησιέστερων γειτόνων χρειάζεται να κρατάμε συνεχώς τους τρέχοντες Κ πλησιέστερους γείτονες.
- Αν Κ=1 τότε χρησιμοποιούνται δύο μεταβλητές στις οποίες αποθηκεύονται ο τρέχον κοντινότερος γείτονας και η απόσταση του από το query vector αντίστοιχα. Κάθε φορά που ελέγχουμε ένα νέο vector του dataset, αν είναι κοντινότερο από το αποθηκευμένο τότε ανανεώνουμε τις δύο μεταβλητές. Τελικά, οι δυο μεταβλητές περιέχουν τον κοντινότερο γείτονα και την απόσταση του.
- Αν K>1 τότε  τότε χρησιμοποιούνται δύο πίνακες Κ θέσεων στους οποίες αποθηκεύονται οι τρέχοντες κοντινότεροι γείτονες και η απόσταση τους από το query vector αντίστοιχα. Οι πίνακες είναι συνεχώς ταξινομημένοι (μέσω της quicksort) έτσι ώστε να μπορούμε εύκολα/γρήγορα να συγκρίνουμε ένα νέο σημείο με τον πιο απομακρυσμένο από τους Κ κοντινότερους γείτονες και να το αντικαταστήσουμε αν το νέο σημείο βρίσκεται πιο κοντά.

Έπειτα από τον υπολογισμό των K κοντινότερων γειτόνων, εκτυπώνεται κάθε ένας με σειρά από τον κοντινότερο προς τον μακρύτερο.
Για κάθε έναν γείτονα εκτυπώνεται η απόσταση του πραγματικού Κ-οστού κοντινότερου γείτονα που βρέθηκε με την εξαντλητική μέθοδο (distanceTrue) καθώς και η απόσταση του προσεγγιστικού Κ-οστού κοντινότερου γείτονα που βρέθηκε με την αντίστοιχη μέθοδο LSH/HyperCube (distanceLSH/distanceHypercube). Έπειτα από την εκτύπωση όλων των γειτόνων εκτυπώνεται ο χρόνος που χρειάστηκε για εύρεση των Κ κοντινότερων γειτόνων τόσο με την εξαντλητική μέθοδό όσο και μέσω του LSH/HyperCube.
Όσον αφορά το Range Search, εκτυπώνονταί τα item_id όλων των σημείων που βρέθηκαν εντός του δοθέντος radius και στην συνέχεια ο χρόνος που χρειάστηκε για την εύρεση τους.


▪ LSH
———————————————

→ Δομή LSH
- - - - - - -
* Η δομή του LSH αποτελείται από:
	- Τον αριθμό l ο οποίος δόθηκε από τον χρήστη και αφορά τον αριθμό των hash tables που θα δημιουργηθούν
	- l Hash Tables
	- l συναρτήσεις g που αντιστοιχούν σε κάθε ένα από τα Hash Tables
Στην πράξη η δομή του LSH είναι ένα struct (το οποίο περιέχει τα παραπάνω). Η δήλωση του γίνεται στο αρχείο lsh.c.

* Τα Hash Tables που χρησιμοποιούνται είναι στατικά και το μέγεθος τους καθορίζεται κατά την αρχικοποίηση τους.
Σε κάθε bucket του hash table αντιστοιχεί μια λίστα έτσι ώστε να επιτρέπονται τα overflow σε ένα bucket. Κάθε λίστα περιέχει όλα τα vector τα οποία έχουν εισαχθεί στο συγκεκριμένο bucket του hash table.
Κάθε κόμβος της λίστας περιέχει ένα vector καθώς και το ID το οποίο αντιστοιχεί στο συγκεκριμένο vector για το συγκεκριμένο hash table και χρησιμοποιείται για την βελτίωση του Querying trick.
Η δήλωση της δομής του hash table υπάρχει στο αρχείο hashTable/hashTable.c.
Η δήλωση της δομής της λίστας, που χρησιμοποιείται από το hash table, υπάρχει στο αρχείο hashTable/hashTableList/hashTableList.c

* Κάθε συνάρτηση g αποτελείται από:
	- K συναρτήσεις h
	- Ένα διάνυσμα r, Κ διαστάσεων
	- Τον αριθμό Μ = 2^32 - 5
Στην πράξη, μία συνάρτηση g είναι ένα struct στο οποίο αρχικοποιούνται και στην συνέχεια αποθηκεύονται για όλη την εκτέλεση του προγράμματος τα παραπάνω στοιχεία. Η δήλωση του υπάρχει στο αρχείο LSH/lsh.c.
Για την δημιουργία μιας συνάρτησης g:
	- Δημιουργούνται K συναρτήσεις h (με τρόπο που εξηγείται στην συνέχεια) και αποθηκεύονται σε έναν πίνακα K θέσεων.
 	- Κατασκευάζεται το διάνυσμα r και αποθηκεύεται. Οι συντεταγμένες του διανύσματος r είναι τυχαίοι ακέραιοι αριθμοί,
	  δηλαδή r_i ε Z.
Δοθέντος ενός vector (έστω p), η τιμή της g (δηλαδή το g(p)) υπολογίζεται από την συνάρτηση computeG του αρχείου lsh.c. Ο υπολογισμός ακολουθεί τον τύπο που περιγράφεται στις διαφάνειες του μαθήματος, δηλαδή:
	- Yπολογίζεται η τιμή της κάθε συνάρτησης h για το δοθέν vector h_i(p) ,όπου 1<=i<=K
	- Πολλαπλασιάζεται με την αντίστοιχη συντεταγμένη του διανύσματος r, δηλαδή r_i * h_i(p)
	- Εφαρμόζουμε την πράξη mod M στο αποτέλεσμα του γινομένου, έτσι ώστε να αποφύγουμε τα overflow
	- Αθροίζουμε τα (r_i * h_i(p)) mod M , για κάθε i από 1 μέχρι K
	- Εφαρμόζουμε ακόμη μια φορά την πράξη mod M στο τελικό άθροισμα και παράγεται το ID το οποίο και αποθηκεύουμε
	- Τέλος εφαρμόζουμε την πράξη mod hashTableSize έτσι ώστε να προκύψει το index/bucket που αντιστοιχεί στο vector

* Κάθε συνάρτηση h αποτελείται από:
	- Ένα διάνυσμα v, d διαστάσεων (όπου d η διάσταση των vectors του αρχείου dataset)
	- Έναν αριθμό t
	- Τον προκαθορισμένο αριθμό w, ο οποίος όμως είναι ίδιος για κάθε συνάρτηση h και κατ' επέκταση
	  αποθηκεύεται μόνο μία φορά εξωτερικά των συναρτήσεων h.
Όσον αφορά το διάνυσμα v, κάθε συντεταγμένη του ακολουθεί κανονική κατανομή Ν(0,1). Οι συντεταγμένες αυτές υπολογίζονται μέσω της συνάρτησης normalRandom του αρχείου LSH/helperFunctions.c.
Όσον αφορά τον αριθμό t, ακολουθεί ομοιόμορφη κατανομή στο διάστημα [Ο,w) και υπολογίζεται μέσω της συνάρτησης uniform_distribution του αρχείου LSH/helperFunctions.c.
Τόσο το διάνυσμα v όσο και ο αριθμός t διαφέρουν σε κάθε συνάρτηση h, υπολογίζονται κατά την αρχικοποίηση κάθε συνάρτησης h και αποθηκεύονται έτσι ώστε να χρησιμοποιηθούν κατά την εκτέλεση του προγράμματος.
Δοθέντος ενός vector (έστω p), η τιμή της h (δηλαδή το h(p)) υπολογίζεται από την συνάρτηση computeH_LSH του αρχείου lsh.c.
Ο υπολογισμός ακολουθεί τον τύπο που περιγράφεται στις διαφάνειες του μαθήματος, δηλαδή:
	- Υπολογίζεται το εσωτερικό γινόμενο των διανυσμάτων v και p μέσω της συνάρτησης dot_product του αρχείου helperFunctions.c
	- Προστίθεται ο αριθμός t στο αποτέλεσμα του εσωτερικού γινομένου
	- Διαιρείται με το w
	- Και τελικά επιστρέφεται το floor (δηλαδή ο αμέσως μικρότερος ακέραιος) του αποτελέσματος της διαίρεσης



→ Εισαγωγή σημείου στην δομή
- - - - - - - - - - - - - - -
Κάθε ένα vector του αρχείου dataset εισάγεται στην δομή του LSH.
Η εισαγωγή αυτή γίνεται μέσω της συνάρτησης insertToLSH του αρχείου lsh.c.
Ένα vector πρέπει να εισαχθεί σε κάθε ένα από τα hash tables της δομής.
Η διαδικασία που ακολουθείται για κάθε ένα από τα l Hash Tables είναι:
	- Μέσω της συνάρτησης computeG υπολογίζεται το ID καθώς και το bucket που αντιστοιχεί στο vector
	- Καλείται η συνάρτηση htInsert του αρχείου hashTable/hashTable.c έτσι ώστε να εισάγει το vector στο hash table
	- H htInsert καλεί την συνάρτηση listInsert δίνοντας της σαν όρισμα την λίστα του bucket που υπολόγισε η g
	- Η listInsert εισάγει το vector στην λίστα αποθηκεύοντας τόσο αυτό όσο και το ID του



→ Αναζήτηση κοντινότερων γειτόνων
- - - - - - - - - - - - - - - - - -
Όπως αναφέρθηκε και παραπάνω, για κάθε σημείο του query αρχείου βρίσκουμε τους K κοντινότερους γείτονες του.
Η αναζήτηση των K κοντινότερων γειτόνων ενός query vector μέσω του LSH γίνεται από την συνάρτηση kNearestNeighborsLSH του αρχείου LSH/lsh.c.
Ακολουθείται η ίδια διαδικασία για κάθε ένα από τα l hash tables κρατώντας καθ΄ όλη την διάρκεια τους Κ τρέχοντες κοντινότερους γείτονες.
Η διαδικασία είναι η εξής:
- Μέσω της συνάρτησης g που αντιστοιχεί στο κάθε hash table υπολογίζεται το ID του query vector καθώς και το bucket στο οποίο προκύπτει για το vector αυτό.
- Καλείται η συνάρτηση htKFindNearestNeighbors του αρχείου hashTable/hashTable.c η οποία έτσι ώστε να γίνει η αναζήτηση στο συγκεκριμένο bucket που υπολογίστηκε από την συνάρτηση g.
- Με την σειρά της καλείται η listFindKNearestNeighbors (του αρχείου hashTable/hashTableList/hashTableList.c) παίρνοντας σαν όρισμα την λίστα που αντιστοιχεί στο bucket αυτό. Η "ουσία" της αναζήτησης βρίσκεται στην listFindKNearestNeighbors.
- Έχοντας την λίστα με όλα τα vectors του dataset που βρίσκονται στο συγκεκριμένο bucket, ξεκινάμε να συγκρίνουμε τα σημεία. Για κάθε vector υπολογίζουμε την απόσταση του από το query vector. Αν η απόσταση του είναι μικρότερη από κάποιο/κάποια τρέχον Κ κοντινότερο γείτονα τότε το εισάγουμε στους Κ κοντινότερους γείτονες αφαιρώντας αυτόν με την μεγαλύτερη απόσταση από το query vector.
- Τέλος, αποφεύγουμε να συγκρίνουμε σημεία τα οποία έχουν διαφορικό ID όπως προτείνει το Querying trick στις διαφάνειες του μαθήματος. Δηλαδή αν ένα σημείο βρίσκεται στο ίδιο bucket με αυτό που προέκυψε για το query vector, αλλά έχει διαφορετικό ID, τότε απλά το προσπερνάμε χωρίς να υπολογίσουμε την απόσταση του από το query vector.



→ Range search
- - - - - - - -
Η αναζήτηση των γειτόνων ενός query αρχείου εντός του δοθέντος radius γίνεται μέσω της συνάρτησης radiusNeigborsLSH του αρχείου LSH/lsh.c.
Για την αποθήκευση των σημείων που βρίσκονται κατά την αναζήτηση εντός του radius χρησιμοποιούμε ένα hash table ίδιο με αυτά που χρησιμοποιεί η δομή του LSH και εξηγήθηκαν παραπάνω. Η επιλογή αυτή έγινε έτσι ώστε να μην εισάγονται δύο ίδια vectors σε αυτό καθώς στο LSH ενδεχομένως να ελέγξουμε το ίδιο διάνυσμα παραπάνω από μια φορά. Ταυτόχρονα έχουμε πολύ γρήγορη εισαγωγή σε χρόνο Ο(1).
Έτσι, κάθε φορά που βρίσκουμε ένα νέο vector εντός του δοθέντος radius αυτό εισάγεται στο hash table μόνο εάν δεν έχει εισαχθεί προηγουμένως και τελικά το hash table περιέχει όλους τους γείτονες του query vector που βρίσκονται εντός του radius.
Η διαδικασία που ακολουθείται είναι αντίστοιχη με αυτήν που περιγράφηκε παραπάνω για τους κοντινότερους γείτονες και εκτελείται διαδοχικά για κάθε ένα από τα l hash tables.
Πιο συγκεκριμένα:
- Αρχικά κατασκευάζεται το hash table στο οποίο θα αποθηκευτούν οι γείτονες εντός του radius που θα βρεθούν
Για κάθε ένα hash table:
-  Μέσω της συνάρτησης g που αντιστοιχεί στο κάθε hash table υπολογίζεται το ID του query vector καθώς και το bucket στο οποίο προκύπτει για το vector αυτό.
- Καλείται η συνάρτηση htFindNeighborsInRadius του αρχείου hashTable/hashTable.c η οποία έτσι ώστε να γίνει η αναζήτηση στο συγκεκριμένο bucket που υπολογίστηκε από την συνάρτηση g.
- Με την σειρά της καλείται η listFindNeighborsInRadius (του αρχείου hashTable/hashTableList/hashTableList.c) παίρνοντας σαν όρισμα την λίστα που αντιστοιχεί στο bucket αυτό.
- Έχοντας την λίστα με όλα τα vectors του dataset που βρίσκονται στο συγκεκριμένο bucket, ξεκινάμε να συγκρίνουμε τα σημεία. Για κάθε vector υπολογίζουμε την απόσταση του από το query vector. Αν η απόσταση είναι μικρότερη ή ίση από το δοθέν radius τότε εισάγουμε το vector αυτό στο hash table με τους γείτονες. Αν το vector υπάρχει ήδη στο hash table από αναζήτηση σε προηγούμενο hash table του LSH τότε δεν εισάγεται δεύτερη φορά.
- Όπως και στην αναζήτηση κοντινότερων γειτόνων εφαρμόζουμε το Querying trick, δηλαδή ελέγχουμε μόνο όσα vectors έχουν ίδιο ID με το query vector.

→ Επιλογή του w των συναρτήσεων h
- - - - - - - - - - - - - - - - - -
Ως γνωστών οι συναρτήσεις h χρησιμοποιούν μία παράμετρο w για τον υπολογισμό τον κάθε υπολογισμό.
Η τιμή του w καθορίζεται κατά την αρχή της εκτέλεσης και παραμένει σταθερή καθ' όλη την διάρκεια εκτέλεσης.
Για να βρούμε την ιδανική τιμή του w ανάλογα με το δοθέν dataset, υπολογίζουμε την μέση απόσταση των διανυσμάτων του dataset. Ο υπολογισμός της μέσης απόστασης για ολόκληρο το dataset είναι πολύ χρονοβόρος για μεγάλο αριθμό διανυσμάτων, επομένως το κάνουμε δειγματοληπτικά για ένα υποσύνολο αυτού.
Έπειτα από αρκετές δοκιμές, παρατηρήσαμε ότι για μεγάλες τιμές του w τα αποτελέσματα της μεθόδου δεν ήταν τόσο καλά.
Έτσι έχουμε επιλέξει να διαιρούμε την μέση απόσταση των διανυσμάτων έτσι ώστε να προκύπτει ένας μικρότερος αριθμός ο οποίος όμως είναι ανάλογος των δεδομένων του dataset.
Πιο συγκεκριμένα παρατηρήσαμε πως:
- Για τιμές του w ίσες ή μεγαλύτερες της μέσης απόστασης η μέθοδος έβγαζε αποτελέσματα με άριστη ακρίβεια και συνήθως έβγαζε τους ίδιους κοντινότερους γείτονες με την εξαντλητική μέθοδο. Προφανώς, ο χρόνος εκτέλεσης πλησίαζε αρκετά αυτόν της εξαντλητικής μεθόδου (ήταν περίπου 5 φορές γρηγορότερος τόσο για το μικρό input file που μας δόθηκε όσο και για το μεγάλο). Έτσι, χάνεται το νόημα του LSH καθώς μέσω του LSH προσπαθούμε να θυσιάσουμε λίγη από την ακρίβεια των αποτελεσμάτων για να κερδίσουμε μεγάλη μείωση χρόνου. Η καθυστέρηση στον χρόνο οφείλεται στο γεγονός ότι για μεγάλες τιμές του w, τα σημεία συγκεντρώνονταν όλα σε ελάχιστα buckets του κάθε hash table.
-  Όσο μειώνεται η τιμή του w παρατηρούμε μικρή μείωση στην ακρίβεια των αποτελεσμάτων αλλά ταυτόχρονα μειώνεται κατά πολύ ο χρόνος εκτέλεσης του LSH.
Τελικά επιλέξαμε η τιμή του w να είναι:
	w = (μέση απόσταση διανυσμάτων του dataset)/60
Καθώς παρατηρήσαμε πολύ καλή χρονική απόδοση και ταυτόχρονα αποτελέσματα τα οποία δεν απέχουν πολύ από τα πραγματικά.
Συγκεκριμένα, όσον αφορά τους χρόνους εκτέλεσης, με την τιμή 60 σαν διαιρέτη του w παρατηρήσαμε:
	- To LSH είναι περίπου 100 φορές ταχύτερο από την εξαντλητική μέθοδο για το μικρό αρχείο εισόδου που μας δόθηκε
	- To LSH είναι περίπου 1000 φορές ταχύτερο από την εξαντλητική μέθοδο για το μεγάλο αρχείο εισόδου που μας δόθηκε

Ο διαιρέτης 60 που επιλέξαμε ορίζεται με define στην αρχή του αρχείου mainLSH.c με όνομα W_DIVIDER.
Σε περίπτωση που θέλουμε να αυξήσουμε την ακρίβεια του προγράμματος θυσιάζοντας λίγη ταχύτητα μπορούμε να μικρύνουμε την τιμή του W_DIVIDER, έτσι ώστε να μεγαλώσει η τιμή του w.


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



▪ HyperCube
———————————————

→ Δομή HyperCube
- - - - - - - - -
* Η δομή του HyperCube αποτελείται από:
	- k συναρτήσεις h, οι οποίες είναι οι ίδιες με το LSH.
	- k συναρτήσεις f. Κάθε συνάρτηση f υλοποιείται σαν ένα HashMap (το hash map λειτουργεί σαν το dictionary της Python).
	- και ένα HashTable.
Στην πράξη η δομή του HyperCube είναι ένα struct (το οποίο περιέχει τα παραπάνω). Η δήλωση του γίνεται στο αρχείο hypercube.c

* Τo Hash Table που χρησιμοποιείται είναι στατικό και το μέγεθος του καθορίζεται κατά την αρχικοποίηση του, συγκεκριμένα θα έχει 2^k κάδους.
Σε κάθε bucket του hash table αντιστοιχεί μια λίστα έτσι ώστε να επιτρέπονται τα overflow σε ένα bucket. Κάθε λίστα περιέχει όλα τα vector τα οποία έχουν εισαχθεί στο συγκεκριμένο bucket του hash table.
Κάθε κόμβος της λίστας περιέχει ένα vector καθώς και το ID το οποίο δεν χρησιμοποιείται στην υλοποίηση Hypercube, έτσι για όλα τα vectors έχουν ID ίσο με -1.
Η δήλωση της δομής του hash table υπάρχει στο αρχείο hashTable/hashTable.c.
Η δήλωση της δομής της λίστας, που χρησιμοποιείται από το hash table, υπάρχει στο αρχείο hashTable/hashTableList/hashTableList.c

* Τα Hash Maps που χρησιμοποιούνται και αναπαριστούν τις f συναρτήσεις είναι δυναμικά (το μέγεθος τους μεταβάλλεται) και το αρχικό μέγεθος του καθορίζεται κατά την αρχικοποίηση τους (στην αρχή έχουμε 100 κάδους).
Σε κάθε bucket του hash map αντιστοιχίζεται μια λίστα έτσι ώστε να επιτρέπονται τα overflow σε ένα bucket.
Όταν "γεμίσει" ένα hash map, δηλαδή του έχει εκχωρηθεί ένας αριθμός κόμβων μεγαλύτερος από το 90% των αριθμών των buckets (ht->count > 0.9*ht->size), τότε το hash map κάνει resizing, συγκεκριμένα
δημιουργείται ένα "καινούριο" hash map που έχει διπλασιασμένο μέγεθος σε σχέση με το παλιό (στη συνέχεια αντιγράφονται τα στοιχειά από το παλιό hash map στο καινούριο και το παλιό διαγράφεται/αποδεσμεύεται).
Κάθε κόμβος της λίστας περιέχει 2 ακεραίους (key:τιμή συνάρτησης hi() και value:0 ή 1).
Η δήλωση της δομής του hash map και της λίστας υπάρχει στο αρχείο HashMap/hashmap.c.

* Κάθε συνάρτηση f αναπαριστάται από ένα hashmap, μια συνάρτηση f επιστρέφει κάθε φορά μια συγκεκριμένη τιμή 0 ή 1 για κάθε τιμή της h συνάρτησης για ένα δεδομένο διάνυσμα.
  Για τον υπολογισμό της τιμής συνάρτησης της f ακολουθούνται τα εξής βήματα (συνάρτηση computeF(...)):

	→ Υπολογίζεται η τιμή της hi(p) για ένα διάνυσμα (έστω p), και δίνεται ως "όρισμα" στην αντίστοιχη f συνάρτηση/hashmap fi(hi(p)) ( έτσι καλείται η computeF(...) ).

	→ Γίνεται generate μια τυχαία τιμή (0 ή 1).

	→ Γίνεται αναζήτηση στο αντίστοιχο bucket του hash map αν υπάρχει ήδη το κλειδί, δηλαδή η τιμή της hi(p), αν ναι απλά επιστρέφεται η τιμή (0 ή 1) που είχε εκχωρηθεί προηγουμένως.
	  Διαφορετικά, στο αντίστοιχο bucket δημιουργείται και εισάγεται ένας κόμβος με κλειδί την τιμή της hi(p) και με αντικείμενο την ήδη generated τυχαία τιμή, η οποία τιμή τελικά επιστρέφεται.
	  (Hash Map-> hash function: η τιμή της hi(p) mod hash_map_size )

* Κάθε συνάρτηση h αποτελείται από:
	- Ένα διάνυσμα v, d διαστάσεων (όπου d η διάσταση των vectors του αρχείου dataset)
	- Έναν αριθμό t
	- Τον προκαθορισμένο αριθμό w, ο οποίος όμως είναι ίδιος για κάθε συνάρτηση h και κατ' επέκταση
	  αποθηκεύεται μόνο μία φορά εξωτερικά των συναρτήσεων h.
Όσον αφορά το διάνυσμα v, κάθε συντεταγμένη του ακολουθεί κανονική κατανομή Ν(0,1). Οι συντεταγμένες αυτές υπολογίζονται μέσω της συνάρτησης normalRandom του αρχείου LSH/helperFunctions.c.
Όσον αφορά τον αριθμό t, ακολουθεί ομοιόμορφη κατανομή στο διάστημα [Ο,w) και υπολογίζεται μέσω της συνάρτησης uniform_distribution του αρχείου LSH/helperFunctions.c.
Τόσο το διάνυσμα v όσο και ο αριθμός t διαφέρουν σε κάθε συνάρτηση h, υπολογίζονται κατά την αρχικοποίηση κάθε συνάρτησης h και αποθηκεύονται έτσι ώστε να χρησιμοποιηθούν κατά την εκτέλεση του προγράμματος.
Δοθέντος ενός vector (έστω p), η τιμή της h (δηλαδή το h(p)) υπολογίζεται από την συνάρτηση computeH_Cube του αρχείου hypercube.c.
Ο υπολογισμός ακολουθεί τον τύπο που περιγράφεται στις διαφάνειες του μαθήματος, δηλαδή:
	- Υπολογίζεται το εσωτερικό γινόμενο των διανυσμάτων v και p μέσω της συνάρτησης dot_product του αρχείου helperFunctions.c
	- Προστίθεται ο αριθμός t στο αποτέλεσμα του εσωτερικού γινομένου
	- Διαιρείται με το w
	- Και τελικά επιστρέφεται το floor (δηλαδή ο αμέσως μικρότερος ακέραιος) του αποτελέσματος της διαίρεσης



→ Εισαγωγή σημείου στην δομή
- - - - - - - - - - - - - - -
Κάθε ένα vector του αρχείου dataset εισάγεται στην δομή του Hypercube και συγκεκριμένα στο hash table.
Η εισαγωγή αυτή γίνεται μέσω της συνάρτησης insertToHyperCube του αρχείου hypercube.c.
Αναλυτικότερα για κάθε vector πρέπει αρχικά να σχηματιστεί το αντίστοιχο index, με την βοήθεια των
συναρτήσεων h και f, έτσι έχω k (new_dimension) επαναλήψεις
όπου για ένα διάνυσμα (έστω p) στην αντίστοιχη διάσταση/επανάληψη i παίρνω μέσω της συνάρτησης f, fi(hi(p)), ένα bit 0 ή 1, το οποιο γίνεται append (σε μια μεταβλητή ή πίνακα) με σκοπό τον σχηματισμό του index .
Συνεπώς, στο τέλος της επανάληψης για ένα δεδομένο διάνυσμα (έστω p) θα έχω : p → [f1(h1(p)), . . . , fd'(hd'(p))] ∈ {0, 1},
μια ακολουθία από bits (0,1) μήκους k (new_dimension). Μετατρέπουμε αυτό το index από το δυαδικό στο δεκαδικό και έτσι έχουμε το
index του bucket του πίνακα hash table όπου θα γίνει η εισαγωγή του δεδομένου vector.
Tέλος, μέσω της συνάρτησης htInsert(...) πραγματοποιείται η εισαγωγή του κάθε vector στο hash table.



→ Αναζήτηση κοντινότερων γειτόνων
- - - - - - - - - - - - - - - - - -
Για κάθε σημείο του query αρχείου βρίσκουμε τους K κοντινότερους γείτονες του.
Η αναζήτηση των K κοντινότερων γειτόνων ενός query vector μέσω του HyperCube γίνεται από την συνάρτηση kNearestNeigborsHypercube του αρχείου HyperCube/hypercube.c.
Ακολουθείται μια παρόμοια διαδικασία με την εισαγωγή δηλαδή για ένα δεδομένο διάνυσμα query (έστω q) που θέλουμε να βρούμε τους K κοντινότερους γείτονές του,
βρίσκουμε πρώτα το αντίστοιχο index του bucket του hashtable (p → [f1(h1(p)), . . . , fd'(hd'(p))] ∈ {0, 1}), αφού μετατρέψουμε την ακολουθία σε δεκαδικό, πάμε στο bucket και εκτελούμε αναζήτηση γειτόνων
μέσω της συνάρτηση htFindNearestNeighborCube(...) του αρχείου hashTable/hashTable.c  η οποία με την σειρά της καλεί την listFindNearestNeighborCube(...).
Η διαδικασία της αναζήτησης γειτόνων στο αντίστοιχο bucket είναι παρόμοια με αυτή του LSH για αυτό και δεν αναλύεται ξανά.
Η μόνη διαφορά είναι ότι δεν υπάρχει η βελτίωση του Querying trick που εφαρμόσαμε στο LSH.

Όμως, η διαδικασία αναζήτησης των γειτόνων στο HyperCube δεν σταματάει εδώ, η αναζήτηση συνεχίζεται και στους γειτονικούς κόμβους από αυτόν που προέκυψε αρχικά για το query vector.
Πιο συγκεκριμένα, ο χρηστής δίνει σαν ορίσματα κατά την εκτέλεση του προγράμματος: το μέγιστο επιτρεπόμενο πλήθος υποψήφιων σημείων που θα ελεγχθούν (Μ) και το μέγιστο επιτρεπόμενο πλήθος κορυφών του υπερκύβου που θα ελεγχθούν (probes).
Έτσι, η αναζήτηση συνεχίζεται έως ότου φτάσουμε ένα από τα δύο αυτά όρια. Σε περίπτωση που το M είναι μεγαλύτερο ή ίσο από τον συνολικό αριθμό σημείων του dataset και ταυτόχρονα το probes είναι μεγαλύτερο ή ίσο από τον αριθμό των κορυφών του υπερκύβου (δηλαδή 2^k) τότε ελέγχονται όλα τα σημεία του dataset.
Η αναζήτηση στις γειτονικές κορυφές γίνεται με βάση το hamming distance των indexes των κορυφών. Δηλαδή, πρώτα ψάχνουμε σε όλες τις κορυφές που έχουν hamming distance ίσο με 1 από την αρχική κορυφή, στην συνέχεια σε όλες τις κορυφές με hamming distance ίσο με δύο κ.ο.κ. .
Η εύρεση των κορυφών με τα αντίστοιχα hamming distances καθώς και η αναζήτηση σε αυτά, πραγματοποιείται από την συνάρτηση searchForHammingDistanceKNN του αρχείου Hypercube/hypercube.c. Η συνάρτηση αυτή, εκτός των άλλων ορισμάτων, δέχεται το αρχικό index του query vector καθώς και το επιθυμητό hamming distance.
Παράγει μόνο όσους αριθμούς έχουν hamming distance ίσο με το επιθυμητό και εκτελεί την αναζήτηση σε κάθε μία κορυφή με το αντίστοιχο index που παράχθηκε.
Προφανώς κάθε ένας αριθμός παράγεται μόνο μία φορά. Επίσης, δεν παράγονται αριθμοί οι οποίοι δεν έχουν hamming distance ίσο με το επιθυμητό.
Αναλυτικότερα, η συνάρτηση λειτουργεί αναδρομικά. Κάθε φορά αλλάζει ένα bit του index, και καλεί τον εαυτό της μειώνοντας το επιθυμητό hamming distance κατά 1 καθώς μόλις άλλαξε ένα bit (δηλαδή μας απομένει να αλλάξει ένα λιγότερο για την επίτευξη του επιθυμητού hamming distance). Η αναδρομική κλήση ξεκινά την αλλαγή των bits από το επόμενο bit και ακολουθεί την ίδια διαδικασία.
Όταν μια γίνει μια αναδρομική κλίση με επιθυμητό hamming distance ίσο με 0, σημαίνει πως έχουμε αλλάξει τον επιθυμητό αριθμό από bits στο αρχικό index, δηλαδή έχουμε παράγει έναν αριθμό με το επιθυμητό hamming distance. Έτσι, εκτελείται αναζήτηση στην κορυφή με αυτό το index και τελικά επιστρέφει από την αναδρομή.
Το πλεονέκτημα αυτής της λύσης είναι ότι είναι πολύ γρήγορη καθώς παράγονται μόνο όσοι αριθμοί έχουν hamming distance ίσο με το επιθυμητό και κάθε ένας από αυτούς παράγεται/ελέγχεται μόνο μία φορά. Διαφορετικά θα έπρεπε να παράγουμε όλους τους πιθανούς αριθμούς με το αντίστοιχο μήκος bits και να ελέγχουμε έναν προς έναν για το αν έχει hamming distance ίσο με το επιθυμητό, κάτι πολύ χρονοβόρο.
Η συνάρτηση searchForHammingDistanceKNN καλείται διαδοχικά για hamming distance αυξανόμενο κατά ένα (ξεκινώντας από το 1) μέχρι να επιτευχθεί κάποια από τις συνθήκες τερματισμού (M ή probes) ή να ελέγξουμε όλες τις κορυφές (δηλαδή να ελέγξουμε μέχρι και για hamming distance ίσο με k). Έτσι επιτυγχάνουμε να ελέγχουμε πρώτα όλες τις κορυφές με hamming distance = 1, μετά αυτές με hamming distance 2 κ.ο.κ.
Μόλις επιτευχθεί μία από τις 3 παραπάνω συνθήκες, ολοκληρώνεται η αναζήτηση των κοντινότερων γειτόνων.



→ Range search
- - - - - - - -
Η αναζήτηση των γειτόνων ενός query αρχείου εντός του δοθέντος radius γίνεται μέσω της συνάρτησης radiusNeigborsHypercube του αρχείου HyperCube/hypercube.c.
Για την αποθήκευση των σημείων που βρίσκονται κατά την αναζήτηση εντός του radius χρησιμοποιούμε ένα hash table ίδιο με αυτά που χρησιμοποιoύνται στις δομές LSH και HyperCube.
Η επιλογή αυτή έγινε για δικιά μας διευκόλυνση ώστε να υπάρχει μια ομοιομορφία μεταξύ Hypercube και LSH, στο Hypercube (σε αντίθεση με το LSH) δεν υπάρχει η περίπτωση να
ελέγξουμε ένα διάνυσμα παραπάνω από μια φορά.
Έτσι, κάθε φορά που βρίσκουμε ένα νέο vector εντός του δοθέντος radius αυτό εισάγεται στο hash table
μόνο εάν δεν έχει εισαχθεί προηγουμένως και τελικά το hash table περιέχει όλους τους γείτονες του query vector που βρίσκονται εντός του radius.
Η διαδικασία που ακολουθείται είναι αντίστοιχη με αυτήν που περιγράφηκε παραπάνω για τους κοντινότερους γείτονες:
Πιο συγκεκριμένα:
- Αρχικά κατασκευάζεται το hash table στο οποίο θα αποθηκευτούν οι γείτονες εντός του radius που θα βρεθούν
Έπειτα:
- Για το δεδομένο διάνυσμα query (έστω q) βρίσκουμε το αντίστοιχο index του bucket του hashtable (p → [f1(h1(p)), . . . , fd'(hd'(p))] ∈ {0, 1}).
- Αφού μετατρέψουμε την ακολουθία σε δεκαδικό, πάμε στο bucket και εκτελούμε αναζήτηση γειτόνων με βάση την ακτίνα μέσω της συνάρτησης htFindNeighborsInRadiusCube(...).
- Με την σειρά της καλείται η listFindNeighborsInRadiusCube (του αρχείου hashTable/hashTableList/hashTableList.c) παίρνοντας σαν όρισμα την λίστα που αντιστοιχεί στο bucket αυτό.
- Έχοντας την λίστα με όλα τα vectors του dataset που βρίσκονται στο συγκεκριμένο bucket, ξεκινάμε να συγκρίνουμε τα σημεία. Για κάθε vector υπολογίζουμε την απόσταση του από το query vector.
  Αν η απόσταση είναι μικρότερη ή ίση από το δοθέν radius τότε εισάγουμε το vector αυτό στο hash table με τους γείτονες.
- Όπως και στην αναζήτηση κοντινότερων γειτόνων, δεν σταματάμε εκεί, αλλά με βάση το hamming distance η αναζήτηση γειτόνων με την δεδομένη ακτίνα επεκτείνεται και στις γειτονικές κορυφές από την τρέχον που τα index τους διαφέρουν (σε σχέση με το index της κορυφής που βρήκαμε προηγουμένως) κατά 1,2 ή και περισσότερα bits (hamming distance).
  Η διαδικασία είναι ίδια με αυτήν που ακολουθείται στην αναζήτηση κοντινότερων γειτόνων και εξηγείται στην προηγούμενη παράγραφο αναλυτικά.
- Επίσης, όπως και παραπάνω, έχουμε περιορισμούς για όσον αναφορά των αριθμό των διανυσμάτων και των κορυφών/buckets του HyperCube που θα εξεταστούν.

→ Επιλογή του w των συναρτήσεων h
- - - - - - - - - - - - - - - - - -
Όπως και στο LSH, οι συναρτήσεις h χρησιμοποιούν μία παράμετρο w για τον υπολογισμό τον κάθε υπολογισμό.
Η τιμή του w καθορίζεται κατά την αρχή της εκτέλεσης και παραμένει σταθερή καθ' όλη την διάρκεια εκτέλεσης.
Για να βρούμε την ιδανική τιμή του w ανάλογα με το δοθέν dataset, υπολογίζουμε την μέση απόσταση των διανυσμάτων του dataset. Ο υπολογισμός της μέσης απόστασης για ολόκληρο το dataset είναι πολύ χρονοβόρος για μεγάλο αριθμό διανυσμάτων, επομένως το κάνουμε δειγματοληπτικά για ένα υποσύνολο αυτού.
Έπειτα από αρκετές δοκιμές, παρατηρήσαμε ότι για μεγάλες τιμές του w τα αποτελέσματα της μεθόδου δεν ήταν τόσο καλά.
Έτσι έχουμε επιλέξει να διαιρούμε την μέση απόσταση των διανυσμάτων έτσι ώστε να προκύπτει ένας μικρότερος αριθμός ο οποίος όμως είναι ανάλογος των δεδομένων του dataset.
Οι παρατηρήσεις που αναφέρθηκαν στην αντίστοιχη παράγραφο του LSH, ισχύουν και για τον υπερκύβο.
Τελικά επιλέξαμε η τιμή του w να είναι:
	w = (μέση απόσταση διανυσμάτων του dataset)/80
Καθώς παρατηρήσαμε πολύ καλή χρονική απόδοση και ταυτόχρονα αποτελέσματα τα οποία δεν απέχουν πολύ από τα πραγματικά.
Με την επιλογή αυτή τα διανύσματα κατανέμονται σχετικά ομοιόμορφα στις κορυφές του υπερκύβου.
Επίσης η επιλογή αυτή έγινε καθώς στην μέθοδο του υπερκύβου μας δίνεται η δυνατότητα να αυξήσουμε ή να μειώσουμε τον αριθμό των σημείων και των κορυφών που ελέγχονται. Έτσι μπορούμε εύκολα να αυξήσουμε ή να μειώσουμε την ακρίβεια του προγράμματος μας αυξάνοντας και μειώνοντας αντίστοιχα και τον χρόνο εκτέλεσης.
Δηλαδή μέσω του διαιρέτη 80 παρατηρήσαμε πολύ καλή κατανομή των σημείων στις κορυφές του υπερκύβου. Έτσι, η ακρίβεια καθώς και η ταχύτητα της μεθόδου εξαρτάται μόνο από τις αντίστοιχες παραμέτρους που θα δοθούν.
Με την κατάλληλη επιλογή των παραμέτρων αυτών, παρατηρούμε εξαιρετικούς χρόνους εκτέλεσης και πολύ ικανοποιητική ακρίβεια αποτελεσμάτων.

Ο διαιρέτης 80 που επιλέξαμε ορίζεται με define στην αρχή του αρχείου mainCube.c με όνομα W_DIVIDER.
Σε περίπτωση που θέλουμε να αυξήσουμε την ακρίβεια του προγράμματος θυσιάζοντας λίγη ταχύτητα μπορούμε να μικρύνουμε την τιμή του W_DIVIDER, έτσι ώστε να μεγαλώσει η τιμή του w. Ωστόσο δεν προτείνεται καθώς όπως ήδη αναφέρθηκε μπορούμε να επιτύχουμε ακριβώς το ίδιο (και με καλύτερη απόδοση) επιλέγοντας κατάλληλα τις παραμέτρους -m και -probes.


↪ Διευκρινίσεις και παρατηρήσεις :

- Κάθε bucket του hash table αντιπροσωπεύει μια κορυφή του υπερκύβου.
- Όσον αφορά την απόδοση, παρατηρούμε ότι το HyperCube είναι κατά πολύ γρηγορότερο από την εξαντλητική μέθοδο και γρηγορότερο επίσης από το LSH.
  Συγκεκριμένα για το αρχείο dataset input_small_id το HyperCube (και τις κατάλληλες παραμέτρους -m και -probes) είναι έως και 200 με 300 φορές ταχύτερο, ενώ για το αρχείο input_b_id είναι έως και 20000 με 30000 φορές ταχύτερο.
  Ωστόσο όπως είναι αναμενόμενο υστερεί στην ακρίβεια των αποτελεσμάτων, μερικές φορές είναι χειρότερη από αυτή του LSH.



Μέρος Β - Clustering
————————————————————————————————
→ Kmeans++
- - - - - - - - - - - - - - - - - -
Πριν την εφαρμογή οποιουδήποτε από τους παρακάτω αλγόριθμους για την αρχικοποίηση των αντίστοιχων clusters χρησιμοποιείται η τεχνική
kmeans++ ώστε να επιλεγούν τα αρχικά κεντροειδή για κάθε cluster. Τα αρχικά κεντροειδή είναι διανύσματα από το input που δίνεται.
Αναλυτικότερα, αν έχω T clusters, θέλω να βρω μέσω του kmeans++ t αρχικά κεντροιειδή, έτσι λοιπόν το πρώτο (t=1) το επιλέγω τυχαία (μέσω μιας rand())
από το input. Στη συνέχεια, μέχρις ότου να βρεθεί ο επιθυμητός αριθμός των κεντροειδών επαναλαμβάνεται η παρακάτω διαδικασία, η οποία περιγράφεται και στις διαφάνειες:

- Βρίσκουμε και αποθηκεύουμε σε έναν πίνακα (props[]) για κάθε μη κεντροειδές διάνυσμα την κοντινότερη απόσταση τους από τα t μέχρι τώρα επιλεγμένα κεντροειδή και παράλληλα βρίσκουμε την μεγαλύτερη απόσταση (maxDi) από αυτές τις ελάχιστες αποστάσεις μεταξύ διανυσμάτων-κεντροειδών.

- Ακολούθως, για κάθε μη κεντροειδές διάνυσμα υπολογίζουμε το επιμέρους άθροισμα στην αντίστοιχη θέση του πίνακα p[] με βάση τον πίνακα props[]. Επίσης χρησιμοποιούμε την μεγαλύτερη απόσταση maxDi για να κανονικοποιήσουμε τις τιμές.
  Εκτελούμε, λοιπόν n-t επαναλήψεις έχοντας ένα άθροισμα στο οποίο κάθε φορά προσθέτουμε (props[r]/maxDi)^2 και αποθηκεύουμε την τιμή στην αντίστοιχη θέση του πίνακα p[] (καθώς αποτελεί το επιμέρους άθροισμα του διανύσματος που θέλουμε).

- Τέλος, επιλέγουμε μια τυχαία τιμή x μέσω της ομοιόμορφης κατανομής στο εύρος των επιμέρους αθροισμάτων των διανυσμάτων που υπολόγισα παραπάνω (δηλαδή από 0 έως και p[n-t-1]) και κάνουμε δυαδική αναζήτηση αυτής στον πίνακα p[] (ο πίνακας p[] είναι ταξινομημένος) με σκοπό να βρούμε την κοντινότερη της τιμή ( την κοντινότερη τιμή "δεξιά", δηλαδή που να ισχύει η συνθήκη p(r − 1) < x ≤ p(r) ), επιστρέφοντας το αντίστοιχο index του p[], το οποίο χρησιμοποιούμε για να πάρουμε το ανάλογο διάνυσμα και να το θέσουμε ως κεντροειδή (αντιγράφεται στον πίνακα clusters[] που περιέχει τα κεντροειδή διανύσματα ).

Η υλοποίηση του γίνεται στο αρχείο Clustering/kmeansPlusPLus.c .



→ Lloyd's (Classic):
- - - - - - - - - - - - - - - - - -
O ακριβής αλγόριθμος Lloyd's υλοποιείται στο αρχείο Clustering/clustering.c και αποτελείται από τις συναρτήσεις clusteringLloyds(...) και lloyds(...).
Πιο συγκεκριμένα, στην συνάρτηση clusteringLloyds(...) αφότου δεσμεύσουμε και αρχικοποιήσουμε τους κατάλληλους πίνακες, καλείται η συνάρτηση kmeansplusplus(...) ώστε να
βρεθούν μέσω αυτής (η οποία περιγράφηκε παραπάνω) τα αρχικά κεντροειδή των clusters. Στη συνέχεια, δεσμεύουμε και αρχικοποιούμε έναν πίνακα με λίστες,
κάθε μια λίστα αντιπροσωπεύει ένα cluster, έτσι λοιπόν σε κάθε λίστα θα αποθηκεύονται όλα τα διανύσματα που θα βρίσκονται από το αλγόριθμο (Lloyd's) ότι ανήκουν στο αντίστοιχο cluster.
Στη συνέχεια, μέχρις ότου επιτευχθεί σύγκλιση, δηλαδή η απόσταση μεταξύ των παλιών κεντροειδών και των καινούριων να είναι μικρότερη ή ίση του 5, εκτελείται ο παρακάτω αλγόριθμος Lloyd's (η συνθήκη σύγκλησης ελέγχεται μετά την 2 επανάληψη του αλγορίθμου καθώς τότε πλέον θα έχουμε "παλιά κεντροειδή").
Ο αριθμός 5, δηλαδή η επιθυμητή σύγκλιση που θέλουμε να πετύχουμε, ορίζεται μέσω ενός define στην αρχή του αρχείου Clustering/clusterHelpingFuns.c με όνομα CONVERGENCE. Έτσι, μπορεί εύκολα να αλλάξει σε περίπτωση που θέλουμε η συνθήκη να είναι πιο "χαλαρή".
Επίσης υπάρχει και μια δεύτερη συνθήκη τερματισμού καθώς πάντα υπάρχει και η περίπτωση ένας αλγόριθμος να μην συγκλίνει ή να αργεί πολύ να συγκλίνει. Συγκεκριμένα, ορίζουμε τον μέγιστο αριθμό επαναλήψεων που θα εκτελεστούν. Σαν μια επανάληψη ορίζουμε τον επαναυπολογισμό των νέων κεντροειδών καθώς και την ανάθεση των σημείων στα νέα αυτά κεντροειδή.
Ο αριθμός των μέγιστων επαναλήψεων που θα εκτελεστούν ορίζεται επίσης μέσω define στην αρχή του αρχείου Clustering/clustering.c με όνομα MAX_RECENTER_ITERATIONS και επίσης μπορεί εύκολα να αλλάξει ανάλογα με τις προτιμήσεις μας. Η default τιμή που έχουμε επιλέξει είναι 10.
Αναλυτικότερα σε κάθε επανάληψη εκτελείται:

	-Για κάθε cluster (που αναπαριστάται από την αντίστοιχη λίστα) υπολογίζεται μέσω της listMeanOfCluster(...) το μέσο διάνυσμα του cluster αυτού, το οποίο θα αποτελέσει το νέο κεντροειδή του (αν το cluster είναι άδειο, δεν περιέχει ακόμα διανύσματα, το κεντροειδές παραμένει το ίδιο).
 	 Μετά τον υπολογισμό του νέου κεντροειδούς για κάθε cluster, διαγράφουμε τα διανύσματα που έχουν εκχωρηθεί σε αυτό και προχωράμε σε νέα ανάθεση διανυσμάτων με βάση τώρα τα καινούρια κεντροειδή.
	 (η παραπάνω διαδικασία παραλείπεται την πρώτη φορά που καλείται η συνάρτηση lloyds(...) καθώς τα κεντροειδή έχουν αρχικοποιηθεί προηγουμένως από την kmeans++)

	-Έπειτα, έχουμε την διαδικασία ανάθεσης κάθε διανύσματος του input στο αντίστοιχο cluster (με βάση τα κεντροειδή).
	 Για κάθε διάνυσμα, λοιπόν, βρίσκουμε μέσω της ευκλείδειας απόστασης το κοντινότερο κεντροειδη συγκρίνοντας το με κάθε ένα κεντροειδές και έτσι εισάγουμε,
     με βάση το index αυτού, το διάνυσμα στο αντίστοιχο cluster (απλή εισαγωγή σε λίστα).



→ Reverse assignment with LSH:
- - - - - - - - - - - - - - - - - -
O αλγόριθμος αυτός υλοποιείται στο αρχείο Clustering/clustering.c και αποτελείται από τις συναρτήσεις clusteringLSH(...) και reverseAssignmentLSH(...).
Πιο συγκεκριμένα, στην συνάρτηση clusteringLSH(...), δεσμεύουμε και αρχικοποιούμε την δομή του LSH, όπου κάθε hash table θα έχει αριθμό buckets ίσο με το 0,5% του αριθμού των διανυσμάτων
αν αυτά είναι περισσότερα από 1000, διαφορετικά το μέγεθος του ισούται με τον αριθμός των διανυσμάτων διά 32 (numOfVecs/32). Έπειτα, αφού σε κάθε vector δεσμευθεί και αρχικοποιηθεί η δομή (clusterInfo), όπου
φυλάσσoνται οι πληροφορίες που είναι απαραίτητες για την υλοποίηση του αλγορίθμου, γίνεται η εισαγωγή του στην δομή LSH (όπως περιγράφηκε παραπάνω στην παράγραφο για το LSH), δηλαδή εισάγεται σε κάθε ένα από τα l hash tables που
έχουν δημιουργηθεί. Επίσης, κάθε cluster αναπαριστάται από ένα hash table μεγέθους (αριθμό από buckets) ίσου με numOfVecs/(4*numOfClusters), έτσι έχουμε έναν πίνακα από hash tables, όπου κάθε hash table (ή αλλιώς θέση πίνακα ) αντιστοιχίζεται σε ενα cluster.
Σε κάθε hash table θα αποθηκεύονται στην συνέχεια τα διανύσματα που θα βρίσκονται από το αλγόριθμο ότι ανήκουν στο αντίστοιχο cluster.
Μετά από όλα τα παραπάνω, καλείται η συνάρτηση kmeansplusplus(...) ώστε να βρεθούν μέσω αυτής (η οποία περιγράφηκε ήδη) τα αρχικά κεντροειδή των clusters.
Στη συνέχεια, μέχρις ότου πραγματοποιηθεί ένας συγκεκριμένος αριθμός επαναλήψεων (MAX_RECENTER_ITERATIONS->10) ή επιτευχθεί σύγκλιση, δηλαδή η απόσταση μεταξύ των παλιών κεντροειδών και των καινούριων να είναι μικρότερη ή ίση του 5,
εκτελείται ο παρακάτω αλγόριθμος reverse Assignment LSH (η συνθήκη σύγκλησης ελέγχεται μετά την 2η επανάληψη του αλγορίθμου καθώς τότε πλέον θα έχουμε "παλιά και καινούρια κεντροειδή"), αναλυτικά:

	-Για κάθε cluster (που αναπαριστάται από το αντίστοιχο hash table) υπολογίζεται μέσω της htMeanOfCluster(...) το μέσο διάνυσμα του cluster αυτού, το οποίο θα αποτελέσει το νέο κεντροειδές του (αν το cluster είναι άδειο, δεν περιέχει ακόμα διανύσματα, το κεντροειδές παραμένει το ίδιο).
 	 Μετά τον υπολογισμό του νέου κεντροειδούς για κάθε cluster, προχωράμε στην διαγραφή του (διαγραφή του hash table και αρχικοποίηση του στην συνέχεια) και έπειτα σε νέα ανάθεση διανυσμάτων με βάση τώρα τα καινούρια κεντροειδή.
	 (η παραπάνω διαδικασία παραλείπεται την πρώτη φορά που καλείται η συνάρτηση reverseAssignmentHypercube(...) καθώς τα κεντροειδή έχουν αρχικοποιηθεί προηγουμένως από την kmeans++).

	-Έπειτα, έχουμε την διαδικασία ανάθεσης κάθε διανύσματος του input στο αντίστοιχο cluster (με βάση τα κεντροειδή).
	 Αρχικά, βρίσκουμε την μικρότερη απόσταση μεταξύ των κεντροειδών και την διαιρούμε δια 2, η απόσταση αυτή θα αποτελέσει
	 την αρχική ακτίνα αναζήτησης. Ακολούθως, εφαρμόζουμε επαναληπτικά την παρακάτω διαδικασία μέχρις ότου να ανατεθούν στα clusters τουλάχιστον το 80% των διανυσμάτων
	 ή πραγματοποιηθεί ένας συγκεκριμένος αριθμός επαναλήψεων (MAX_RECENTER_ITERATIONS->10) ή ακόμα αν ο αριθμός των αναθέσεων που έγιναν στην τρέχουσα επανάληψη είναι ο ίδιος με
	 τον αριθμό των αναθέσεων που έγιναν στην προηγούμενη.
     Έτσι, σε κάθε cluster μέσω την συνάρτησης radiusNeigborsClustering(...) (με την σειρά καλούνται οι συναρτήσεις: radiusNeigborsClustering()-> htFindNeighborsInRadiusClustering()-> listFindNeighborsInRadiusClustering()) ανατίθενται διανύσματα.
	 Συγκεκριμένα, κάνουμε αναζήτηση με βάση την ακτίνα (range search με LSH) που υπολογίστηκε (όπως και στην συνάρτηση listFindNeighborsInRadius(...), μάλιστα χρησιμοποιείται επίσης και το Querying trick) μόνο που επιπλέον για
	 κάθε ένα διάνυσμα που συναντάται στο αντίστοιχο bucket του hash table ελέγχεται σε πρώτη φάση αν ήδη έχει ανατεθεί σε ένα cluster στην "ίδια επανάληψη",
	 τότε αν ισχύει αυτή η συνθήκη ελέγχεται ξανά το διάνυσμα για το αν έχει ανατεθεί ήδη στο παρόν cluster ή αν έχει ανατεθεί προηγουμένως σε αναζήτηση με της ίδιας επανάληψης με διαφορετική (μικρότερη)
	 ακτίνα, σε περίπτωση που είναι αληθής η συνθήκη αυτή το εξεταζόμενο διάνυσμα παραλείπεται και προχωράμε στο επόμενο. Αν ένα σημείο έχει ανατεθεί σε ένα cluster στην ίδια επανάληψη για μικρότερη ακτινά, τότε υποθέτουμε ότι έχει ανατεθέι στο κατάλληλο cluster, για αυτό και το παραλείπουμε. Διαφορετικά, υπολογίζεται η απόσταση μεταξύ του εξεταζόμενου διανύσματος και του δεδομένου κεντροειδούς τότε ΑΝ η απόσταση είναι εντός της ακτίνας
	 φαίνεται πως το διάνυσμα ανήκει σε περισσότερα από ένα cluster, συνεπώς το προσθέτουμε στην λίστα με τα conflicts (confList), ώστε μετά το πέρας των range searches, να αναθέσουμε αυτό και όποια άλλα διανύσματα είναι στην λίστα με τα conflicts στα αντίστοιχα clusters με βάση της ευκλείδειας απόστασης (εξηγείται παρακάτω).
	 Συνεπώς, αν ΔΕΝ έχει ανατεθεί το διάνυσμα που εξετάζεται σε ένα cluster στην "ίδια επανάληψη" τότε υπολογίζεται η ευκλείδεια μεταξύ αυτού και του κεντροειδή (του παρόν cluster) και με την προϋπόθεση
	 ότι είναι εντός ακτίνας (η απόσταση διανύσμαστος-κεντροειδούς) το διάνυσμα εισάγεται τελικά στο αντίστοιχο cluster, μάλιστα στο δεδομένο διάνυσμα καταχωρούνται οι ανάλογες πληροφορίες όσον αναφορά:
	 1) το index του cluster στο οποίο ανατέθηκε (assignedCluster)
	 2) τον αριθμό της επανάληψης (iterationAssigned)
	 3) την τιμή της ακτίνας του range search που έγινε η ανάθεση του (assignedAtRadius), ώστε να γίνονται οι έλεγχοι που περιγράφηκαν προηγουμένως,
	 αποφεύγοντας έτσι άσκοπους υπολογισμούς της ευκλείδειας απόστασης. Επίσης, κρατώντας τις πληροφορίες αυτές καταφέρνουμε να διαχειριστούμε κάθε φορά τα διανύσματα που παρουσιάζουν conflicts (ένα διάνυσμα
	 έχει conflict όταν για μια δεδομένη ακτίνα αντιστοιχίζεται σε περισσότερα από 1 cluster).
	 Μετά, λοιπόν, από την εφαρμογή του range search για όλα τα cluster διατρέχουμε την λίστα με τα conflicts (confList), ώστε να αναθέσουμε κάθε διάνυσμα στο αντίστοιχο cluster του κοντινότερου κεντροειδούς σε αυτό
	 το διάνυσμα (μέσω την ευκλείδειας απόστασης).
	 Τέλος, η λίστα με τα conflicts διαγράφεται, η ακτίνα διπλασιάζεται και εκτελείται η ίδια διαδικασία επαναληπτικά.

	-Στην συνέχεια, αφότου η παραπάνω επαναληπτική διαδικασία τερματίσει, θα περισσέψουν κάποια διανύσματα χωρίς να έχουν ανατεθεί σε κάποιο cluster. Συνεπώς,
	 Για κάθε τέτοιο διάνυσμα, βρίσκουμε μέσω της ευκλείδειας απόστασης το κοντινότερο κεντροειδές και έτσι εισάγουμε,
         με βάση το index αυτού, το διάνυσμα στο αντίστοιχο cluster ( εισαγωγή στο αντίστοιχο hash table που το αναπαριστά ).


→ Επιλογή του w των συναρτήσεων h στο LSH
- - - - - - - - - - - - - - - - - -
Όπως έχει ήδη αναφερθεί, οι συναρτήσεις h του LSH χρησιμοποιούν την παράμετρο w.
Ομοίως με την υλοποίηση του LSH, ορίζουμε και εδώ το w με βάση την μέση απόσταση των διανυσμάτων του dataset και παραμένει σταθερή για όλη την εκτέλεση.
Ο τρόπος υπολογισμού του w είναι αντίστοιχος με αυτόν που περιγράφεται αναλυτικά στην παράγραφο του LSH.
Συγκεκριμένα, έπειτα από δοκιμές για διάφορες τιμές του συντελεστή του w καταλήξαμε πως η βέλτιστη τιμή είναι 60. Δηλαδή:
	w = (μέση απόσταση διανυσμάτων του dataset)/60
Αναλυτικότερα, για μεγάλες τιμές του w (δηλαδή για μικρότερο διαιρέτη) παρατηρήσαμε χειρότερα αποτελέσματα (μικρότερες τιμές silhouette) και μεγαλύτερους χρόνους ειδικά για μεγάλα αρχεία dataset όπως το μεγάλο αρχείο που μας δόθηκε.

Ο διαιρέτης 60 που επιλέξαμε ορίζεται με define στην αρχή του αρχείου Clustering/clustering.c με όνομα W_DIVIDER_LSH, έτσι ώστε να μπορεί εύκολα να αλλάξει.
Ενδεχομένως για διαφορετικά dataset η βέλτιστη τιμή του w να είναι μεγαλύτερη ή μικρότερη από αυτήν που έχουμε επιλέξει, ωστόσο μπορεί εύκολα να αλλάξει και να δοκιμαστεί μέσω του define.




→ Reverse assignment with Hypecube
- - - - - - - - - - - - - - - - - -
O αλγόριθμος αυτός υλοποιείται στο αρχείο Clustering/clustering.c και αποτελείται από τις συναρτήσεις clusteringHypercube(...) και reverseAssignmentHypercube(...).
Πιο συγκεκριμένα, στην συνάρτηση clusteringHypercube(...), δεσμεύουμε και αρχικοποιούμε την δομή του Hyper Cube, όπου to hash table θα έχει αριθμό buckets ίσο με (numOfVecs/16).
Έπειτα, αφού σε κάθε vector δεσμευθεί και αρχικοποιηθεί η δομή (clusterInfo), όπου
φυλάσσoνται οι πληροφορίες που είναι απαραίτητες για την υλοποίηση του αλγορίθμου, γίνεται η εισαγωγή του στην δομή Hyper Cube (όπως περιγράφηκε παραπάνω στην παράγραφο για το Hyper Cube).
Επίσης, κάθε cluster αναπαριστάται από ένα hash table μεγέθους (αριθμό από buckets) ίσου με numOfVecs/(4*numOfClusters), έτσι έχουμε έναν πίνακα από hash tables, όπου κάθε hash table (ή αλλιώς θέση πίνακα ) αντιστοιχίζεται σε ένα cluster.
Σε κάθε hash table θα αποθηκεύονται στην συνέχεια τα διανύσματα που θα βρίσκονται από το αλγόριθμο ότι ανήκουν στο αντίστοιχο cluster.
Μετά από όλα τα παραπάνω, καλείται η συνάρτηση kmeansplusplus(...) ώστε να βρεθούν μέσω αυτής (η οποία περιγράφηκε ήδη) τα αρχικά κεντροειδή των clusters.
Στη συνέχεια, μέχρις ότου πραγματοποιηθεί ένας συγκεκριμένος αριθμός επαναλήψεων (MAX_RECENTER_ITERATIONS->10) ή επιτευχθεί σύγκλιση, δηλαδή η απόσταση μεταξύ των παλιών κεντροειδών και των καινούριων να είναι μικρότερη ή ίση του 5,
εκτελείται ο παρακάτω αλγόριθμος reverse Assignment Hypecube (η συνθήκη σύγκλησης ελέγχεται μετά την 2η επανάληψη του αλγορίθμου καθώς τότε πλέον θα έχουμε "παλιά και καινούρια κεντροειδή"), αναλυτικά:

	-Για κάθε cluster (που αναπαριστάται από το αντίστοιχο hash table) υπολογίζεται μέσω της htMeanOfCluster(...) το μέσο διάνυσμα του cluster αυτού, το οποίο θα αποτελέσει το νέο κεντροειδή του (αν το cluster είναι άδειο, δεν περιέχει ακόμα διανύσματα, το κεντροειδή παραμένει το ίδιο).
 	 Μετά τον υπολογισμό του νέου κεντροειδούς για κάθε cluster, προχωράμε στην διαγραφή του (διαγραφή του hash table και αρχικοποίηση του στην συνέχεια) και έπειτα σε νέα ανάθεση διανυσμάτων με βάση τώρα τα καινούρια κεντροειδή.
	 (η παραπάνω διαδικασία παραλείπεται την πρώτη φορά που καλείται η συνάρτηση reverseAssignmentHypercube(...) καθώς τα κεντροειδή έχουν αρχικοποιηθεί προηγουμένως από την kmeans++).

	-Έπειτα, έχουμε την διαδικασία ανάθεσης κάθε διανύσματος του input στο αντίστοιχο cluster (με βάση τα κεντροειδή).
	 Αρχικά, βρίσκουμε την μικρότερη απόσταση μεταξύ των κεντροειδών και την διαιρούμε δια 2, η απόσταση αυτή θα αποτελέσει
	 την αρχική ακτίνα αναζήτησης. Ακολούθως, εφαρμόζουμε επαναληπτικά την παρακάτω διαδικασία μέχρις ότου να ανατεθούν στα clusters τουλάχιστον το 80% των διανυσμάτων
	 ή πραγματοποιηθεί ένας συγκεκριμένος αριθμός επαναλήψεων (MAX_RECENTER_ITERATIONS->15) ή ακόμα αν ο αριθμός των αναθέσεων που έγιναν στην τρέχουσα επανάληψη είναι ο ίδιος με
	 τον αριθμό των αναθέσεων που έγιναν στην προηγούμενη.
     Έτσι, σε κάθε cluster μέσω την συνάρτησης radiusNeigborHypercubeClustering(...) (με την σειρά καλούνται οι συναρτήσεις: radiusNeigborHypercubeClustering()-> htFindNeighborsInRadiusClusteringCube()-> listFindNeighborsInRadiusClusteringCube()) ανατίθενται διανύσματα.
	 Συγκεκριμένα, κάνουμε αναζήτηση με βάση την ακτίνα (range search με Hypercube) που υπολογίστηκε (όπως και στην συνάρτηση listFindKNearestNeighborsCube(...) με τους αντίστοιχους περιορισμούς, δηλαδή ελέγχεται συγκεκριμένο αριθμός διανυσμάτων και κορυφών του υπερκύβου) μόνο που επιπλέον για
	 κάθε ένα διάνυσμα που συναντάται στο αντίστοιχο bucket του hash table ελέγχεται σε πρώτη φάση αν ήδη έχει ανατεθεί σε ένα cluster στην "ίδια επανάληψη",
	 τότε αν ισχύει αυτή η συνθήκη ελέγχεται ξανά το διάνυσμα για το αν έχει ανατεθεί ήδη στο παρόν cluster ή αν έχει ανατεθεί προηγουμένως σε αναζήτηση με διαφορετική
	 ακτίνα, σε περίπτωση που είναι αληθής η συνθήκη αυτή το εξεταζόμενο διάνυσμα παραλείπεται και προχωράμε στο επόμενο. Διαφορετικά, υπολογίζεται η απόσταση μεταξύ του εξεταζόμενου διανύσματος και του δεδομένου κεντροειδούς τότε ΑΝ η απόσταση είναι εντός της ακτίνας
	 φαίνεται πως το διάνυσμα ανήκει σε περισσότερα από ένα cluster, συνεπώς το προσθέτουμε στην λίστα με τα conflicts (confList), ώστε μετά το πέρας των range searches, να αναθέσουμε αυτό και όποια άλλα διανύσματα είναι στην λίστα με τα conflicts στα αντίστοιχα clusters με βάση της ευκλείδειας απόστασης (εξηγείται παρακάτω).
	 Συνεπώς, αν ΔΕΝ έχει ανατεθεί το διάνυσμα που εξετάζεται σε ένα cluster στην "ίδια επανάληψη" τότε υπολογίζεται η ευκλείδεια μεταξύ αυτού και του κεντροειδή (του παρόν cluster) και με την προϋπόθεση
	 ότι είναι εντός ακτίνας (η απόσταση διανύσματος-κεντροειδούς) το διάνυσμα εισάγεται τελικά στο αντίστοιχο cluster, μάλιστα στο δεδομένο διάνυσμα καταχωρούνται οι ανάλογες πληροφορίες όσον αναφορά:
	 1) το index του cluster στο οποίο ανατέθηκε (assignedCluster)
	 2) τον αριθμό της επανάληψης (iterationAssigned)
	 3) την τιμή της ακτίνας του range search που έγινε η ανάθεση του (assignedAtRadius), ώστε να γίνονται οι έλεγχοι που περιγράφηκαν προηγουμένως,
	 αποφεύγοντας έτσι άσκοπους υπολογισμούς της ευκλείδειας απόστασης. Επίσης, κρατώντας τις πληροφορίες αυτές καταφέρνουμε να διαχειριστούμε κάθε φορά τα διανύσματα που παρουσιάζουν conflicts (ένα διάνυσμα
	 έχει conflict όταν για μια δεδομένη ακτίνα αντιστοιχίζεται σε περισσότερα από 1 cluster).
	 Μετά, λοιπόν, από την εφαρμογή του range search για όλα τα cluster διατρέχουμε την λίστα με τα conflicts (confList), ώστε να αναθέσουμε κάθε διάνυσμα στο αντίστοιχο cluster του κοντινότερου κεντροειδούς σε αυτό
	 το διάνυσμα (μέσω την ευκλείδειας απόστασης).
	 Τέλος, η λίστα με τα conflicts διαγράφεται, η ακτίνα διπλασιάζεται και εκτελείται η ίδια διαδικασία επαναληπτικά.

	-Στην συνέχεια, αφότου η παραπάνω επαναληπτική διαδικασία τερματίσει, θα περισσέψουν κάποια διανύσματα χωρίς να έχουν ανατεθεί σε κάποιο cluster. Συνεπώς,
	 Για κάθε τέτοιο διάνυσμα, βρίσκουμε μέσω της ευκλείδειας απόστασης το κοντινότερο κεντροειδές και έτσι εισάγουμε,
         με βάση το index αυτού, το διάνυσμα στο αντίστοιχο cluster ( εισαγωγή στο αντίστοιχο hash table που το αναπαριστά ).

→ Επιλογή του w των συναρτήσεων h στο Hypecube
- - - - - - - - - - - - - - - - - - - - - - - -
Όπως έχει ήδη αναφερθεί, οι συναρτήσεις h του Hypecube χρησιμοποιούν την παράμετρο w.
Ομοίως με την υλοποίηση του Hypecube, ορίζουμε και εδώ το w με βάση την μέση απόσταση των διανυσμάτων του dataset και παραμένει σταθερή για όλη την εκτέλεση.
Ο τρόπος υπολογισμού του w είναι αντίστοιχος με αυτόν που περιγράφεται αναλυτικά στην παράγραφο του Hypecube.
Έπειτα από δοκιμές για διάφορες τιμές του συντελεστή του w καταλήξαμε πως η βέλτιστη τιμή για το clustering μέσω του hypercube είναι 20. Δηλαδή:
	w = (μέση απόσταση διανυσμάτων του dataset)/20
Αναλυτικότερα παρατηρήσαμε:
	- Οι χρόνοι εκτέλεσης ήταν πανομοιότυποι για διάφορες τιμές του w.
	- H τιμή (20) που επιλέξαμε έχει το καλύτερο tradeoff χρόνου/silhouette
	- Επιλέξαμε μικρότερη τιμή για τον διαιρέτη σε σχέση με αυτόν που επιλέξαμε στο hypercube για την εύρεση γειτόνων. Η επιλογή αυτή έγινε καθώς στο clustering θέλουμε οι κορυφές να είναι λίγο περισσότερο "πυκνοκατοικημένες" έτσι ώστε να παίρνουμε ικανοποιητικότερα αποτελέσματα σε κάθε range search. Ωστόσο η κατανομή πρέπει να παραμένει σχετικά ομοιόμορφη χωρίς να συγκεντρώνεται πολύ μεγάλος αριθμός σημείων σε μία κορυφή. Για αυτό και έγινε η επιλογή της τιμής 20.

Τέλος, όπως αναφέρθηκε και στην παράγραφο του hypercube, μεγάλο ρόλο στην αποδοτικότητα και την ταχύτητα του αλγορίθμου έχουν οι παράμετροι -m και -probes που θα δοθούν από τον χρήστη.
Για μικρές τιμές, σε κάθε ένα range search θα ελέγχονται πολύ λίγα σημεία με αποτέλεσμα τελικά τα περισσότερα σημεία να ανατίθενται σε cluster μέσω της εξαντλητικής μεθόδου. Αντίθετα, για πολύ μεγάλες τιμές, σε κάθε ένα range search θα ελέγχεται πολύ μεγάλο (ή όλο) το πλήθος των στοιχείων του dataset.
Έτσι, η σωστή επιλογή των δύο αυτών παραμέτρων κάνει την μέθοδο πολύ αποδοτική.

Ο διαιρέτης 20 που επιλέξαμε ορίζεται με define στην αρχή του αρχείου Clustering/clustering.c με όνομα W_DIVIDER_CUBE, έτσι ώστε να μπορεί εύκολα να αλλάξει.
Ενδεχομένως για διαφορετικά dataset η βέλτιστη τιμή του w να είναι μεγαλύτερη ή μικρότερη από αυτήν που έχουμε επιλέξει, ωστόσο μπορεί εύκολα να αλλάξει και να δοκιμαστεί μέσω του define.



→ Silhouettes
- - - - - - - - - - - - - - - - - -

Για τον υπολογισμό της σιλουέτας ενός cluster υπολογίζουμε τις σιλουέτες κάθε σημείου το οποίο έχει ανατεθεί σε αυτό το cluster και στην συνέχεια παίρνουμε τον μέσο όρο. Δηλαδή αθροίζουμε τις σιλουέτες όλων των σημείων ενός cluster και διαιρούμε το άθροισμα με τον αριθμό των σημείων του cluster.
Για τον υπολογισμό της σιλουέτας ενός σημείου i:
- Υπολογίζουμε το a(i), δηλαδή την μέση απόσταση του σημείου i από όλα τα υπόλοιπα σημεία που έχουν ανατεθεί στο ίδιο cluster. Πιο συγκεκριμένα, υπολογίζουμε την απόσταση του σημείου i με κάθε ένα σημείο του ίδιου cluster, αθροίζουμε τις αποστάσεις αυτές και διαιρούμε με το πλήθος των σημείων που συγκρίναμε το i.
- Υπολογίζουμε το b(i), δηλαδή την μέση απόσταση του σημείου i από όλα τα υπόλοιπα σημεία που έχουν ανατεθεί στο αμέσως κοντινότερο cluster του σημείου i (εκτός από αυτό που έχει ανατεθεί). Πιο συγκεκριμένα, βρίσκουμε το αμέσως κοντινότερο κεντροιδές, υπολογίζουμε την απόσταση του σημείου i με κάθε ένα σημείο που έχει ανατεθεί στο κεντροιδές αυτό, αθροίζουμε τις αποστάσεις και διαιρούμε με το πλήθος των σημείων που έχουν ανατεθεί σε αυτό το cluster (και υπολογίστηκαν οι αποστάσεις με το i).
- Αφού υπολογίσουμε τα a(i) και b(i) η σιλουέτα του σημείου i προκύπτει από τον τύπο:
	s(i) = ( b(i) - a(i) ) / max{ a(i), b(i) }

Επίσης υπολογίζουμε και την συνολική σιλουέτα (sTotal) η οποία προκύπτει από το άθροισμα όλων των σιλουετών των διανυσμάτων του dataset και την διαίρεση με το πλήθος των διανυσμάτων του dataset. Είναι δηλαδή ο μέσος όρος των s(i) όπου i όλα τα διανύσματα του dataset.

Για το Lloyds:
Έπειτα από την ολοκλήρωση του clustering τα σημεία που έχουν ανατεθεί σε κάθε cluster περιέχονται σε μια λίστα για κάθε ένα cluster.
Έτσι για τον υπολογισμό της σιλουέτας ενός cluster καλείται η συνάρτηση silhouetteofClusterLloyds του αρχείου hashTable/hashTableList/hashTableList.c με όρισμα την λίστα με τα στοιχεία του cluster.
Η συνάρτηση αυτή υπολογίζει την σιλουέτα για κάθε σημείο της λίστας, δηλαδή για κάθε σημείο που έχει ανατεθεί στο cluster αυτό και τελικά βρίσκει τον μέσο όρο.
Ο υπολογισμός της σιλουέτας ενός σημείου γίνεται από την συνάρτηση listComputeAverageDistOfEveryPointOfClusterLloyds η οποία επίσης περιέχεται στο ίδιο αρχείο. Η συνάρτηση αυτή χρησιμοποιεί την συνάρτηση listFindAverageDistOfVector η οποία υπολογίζει την μέση απόσταση ενός δοθέντος σημείου από μια λίστα με σημεία. Έτσι καλείται δύο φορές μία με όρισμα την λίστα με τα όλα τα στοιχεία του ίδιου cluster (για τον υπολογισμό του a(i)) και μία με όρισμα την λίστα με όλα τα στοιχεία του αμέσως κοντινότερου cluster (για τον υπολογισμό του b(i))

Για LSH και Hypercube:
Η διαδικασία που ακολουθείται για τον υπολογισμό της σιλουέτας στο LSH και στο Hypercube είναι ακριβώς η ίδια.
Όπως έχει αναφερθεί και παραπάνω, έπειτα από την ολοκλήρωση του clustering τα σημεία που έχουν ανατεθεί σε κάθε cluster περιέχονται σε ένα hash table για κάθε cluster.
Έτσι για τον υπολογισμό της σιλουέτας ενός cluster καλείται η συνάρτηση silhouetteofClusterLSH του αρχείου hashTable/hashTable.c με όρισμα το hash table που περιέχει όλα τα διανύσματα που ανατέθηκαν στο cluster αυτό.
Στην συνέχεια καλείται η συνάρτηση listComputeAverageDistOfEveryPointOfCluster του αρχείου hashTable/hashTableList/hashTableList.c η οποία είναι υπεύθυνη να υπολογίσει τα a(i) και b(i) για κάθε ένα σημείο του hash table (δηλαδή του cluster). Δέχεται σαν όρισμα έναν πίνακα από λίστες, δηλαδή μια λίστα για κάθε bucket του hash table.
Ο υπολογισμός των a(i) και b(i) γίνεται μέσω της htFindAverageDistanceOfVectorInCluster του αρχείου hashTable.c η οποία υπολογίζει την μέση απόσταση ενός σημείου από όλα τα σημεία ενός cluster. Προφανώς δέχεται σαν όρισμα το σημείο καθώς και ένα hash table το οποίο περιέχει όλα τα σημεία του cluster που θέλουμε να συγκρίνουμε.
Αφού υπολογιστούν τα a(i) και b(i) για κάθε ένα σημείο, υπολογίζουμε την σιλουέτα κάθε σημείου μέσω του τύπου που αναφέρθηκε παραπάνω. Τελικά βρίσκουμε και τον μέσο όρο των σιλουετών, δηλαδή την σιλουέτα του cluster.


Ο υπολογισμός των σιλουετών είναι μια πολύ χρονοβόρα διαδικασία, καθώς κάθε ένα διάνυσμα του dataset συγκρίνεται (δηλαδή υπολογίζεται η απόσταση του) με κάθε ένα σημείο από δύο cluster (το δικό του και το αμέσως κοντινότερο).
Υποθέτοντας ότι τα σημεία έχουν κατανεμηθεί σχετικά ομοιόμορφα στα cluster, η πολυπλοκότητα του υπολογισμού των σιλουετών είναι:
	numberOfVectors * 2*(numberOfVectors/numberOfClusters) * d
Επομένως είναι προφανές ότι είναι υπερβολικά χρονοβόρο.
Αυτό επιβεβαιώνει και το γεγονός ότι για το μεγάλο αρχείο dataset που μας δόθηκε (1.000.000 διανύσματα) ο υπολογισμός των σιλουετών καθυστερεί υπερβολικά.



	↪ Διευκρινίσεις και παρατηρήσεις :

	- Οι παραπάνω αλγόριθμοι ουσιαστικά διαφέρουν μονό στο βήμα της ανάθεσης των διανυσμάτων στα αντίστοιχα clusters. Η αρχικοποίηση (kmeans++) και η εύρεση του μέσου παραμένει ίδια και στους 3 αλγορίθμους που υλοποιήσαμε.
	- Στην λίστα με τα conflicts πιθανόν υπάρχουν διπλότυποι κόμβοι που αφορούν τα ίδια διανύσματα, όταν όμως πραγματοποιηθεί η ανάθεση ενός διανύσματος σε ένα cluster, τότε στο πεδίο της ακτίνας (assignedAtRadius) του διανύσματος αποθηκεύεται
	  η τιμή -3.0, έτσι αν ξανά συναντηθεί στην λίστα το ίδιο διάνυσμα με έναν έλεγχο (getAssignedAtRadius(temp->v)<-1.0) καταφέρνουμε απλά να παραλείπεται.
	- Τα hash tables που χρησιμοποιούνται στις υλοποιήσεις των αλγορίθμων reverse assignment with LSH and Hypercube είναι τα ίδια με αυτά που χρησιμοποιούνται στο Α μέρος της εργασίας.
	- Κάθε vector αποθηκεύεται μόνο μία φορά στην μνήμη και κάθε μία δομή που χρησιμοποιείται (hash table ή list ανάλογα) περιέχει έναν δείκτή στην θέση μνήμης αυτή.