-Ιωάννης Καπετανγεώργης |
 1115201800061 		|
-Δημήτριος Σιταράς	|
 1115201800178 	 	|
—————————————————————————


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


.
├── 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

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

► Γενικά:

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

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

	→ Όλη η μνήμη που δεσμεύεται δυναμικά κατά την εκτέλεση του προγράμματος, αποδεσμεύεται πλήρως.
  	  ( Έχει ελεγχθεί μέσω 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.


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

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

→ Δομή HyperCube
- - - - - - - - -
* Η δομή του HyperCube αποτελείται από:
	- k συναρτήσεις h, οι οποίες είναι οι ίδιες με το LSH.
	- k HashMap f (το 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.
Συνεπώς, στο τέλος της επανάληψης για ένα δεδομένο διάνυσμα (έστω 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 που θα εξεταστούν.


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

- Έχουμε επιλέξει την τιμή 4 για το w το οποίο χρησιμοποιείται από τις συναρτήσεις h. Δοκιμάσαμε να ορίζουμε το w με βάση την μέση απόσταση των vectors του dataset αλλά τα αποτελέσματα που παρατηρήσαμε ήταν χειρότερα. Η τιμή του w μπορεί εύκολα να αλλάζει από το αρχείο mainCube.c καθώς σε διαφορετικά αρχεία dataset μπορεί διαφορετική τιμή να δίνει καλύτερα αποτελέσματα.
- Όσον αφορά την απόδοση, παρατηρούμε ότι το HyperCube είναι κατά πολύ γρηγορότερο από την εξαντλητική μέθοδο και γρηγορότερο επίσης από το LSH.
  Συγκεκριμένα για το αρχείο dataset input_small_id το HyperCube είναι έως και 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(...) και silhouetteLloyds(...).
Πιο συγκέκριμένα, στην συνάρτηση clusteringLloyds(...) αφότου δεσμεύσουμε και αρχικοποιήσουμε τους κατάλληλους πίνακες, καλείται η συνάρτηση kmeansplusplus(...) ώστε να 
βρεθούν μέσω αυτής (η οποία περιγράφηκε παραπάνω) τα αρχικά κεντροειδή των clusters. Στη συνέχεια, δεσμεύουμε και αρχικοποιούμε έναν πίνακα με λίστες,
κάθε μια λίστα αντιπροσωπεύει ένα cluster, έτσι λοιπόν σε κάθε λίστα θα αποθηκεύονται όλα τα διανύσματα που θα βρίσκονται απο το αλγόριθμο (Lloyd's) ότι ανήκουν στο αντίστοιχο cluster.
Στη συνέχεια, μεχρις ώτου επιτευχθει σύγκλιση, δηλαδή η απόσταση μεταξυ των παλιών κεντροειδών και των καινούριων να ειναι μικρότερη ή ίση του 5, εκτελείται ο παρακάτω αλγόριθμος Lloyd's (η συνθήκη σύγκλησης ελέγχεται μετα την 2 επανάληψη του αλγορίθμου καθώς τότε πλέον θα έχω παλιά κεντροειδή), 
αναλυτικά:

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

→ Reverse assignment with LSH:
- - - - - - - - - - - - - - - - - -
O αλγόριθμος αυτός υλοποιείται στο αρχείο Clustering/clustering.c και αποτελείται από τις συναρτήσεις clusteringLSH(...), reverseAssignmentLSH(...) και silhouetteLSH_Hypercube(...).
Πιο συγκέκριμένα, στην συνάρτηση 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.
Στη συνέχεια, μεχρις ώτου πραγματοποιηθεί ένας συγκεκριμένος αριθμός επαναλήψεων ή επιτευχθει σύγκλιση, δηλαδή η απόσταση μεταξυ των παλιών κεντροειδών και των καινούριων να ειναι μικρότερη ή ίση του 5, 
εκτελείται ο παρακάτω αλγόριθμος reverse Assignment LSH(η συνθήκη σύγκλησης ελέγχεται μετα την 2 επανάληψη του αλγορίθμου καθώς τότε πλέον θα έχω παλιά κεντροειδή), αναλυτικά:
		
	-Για κάθε cluster (που αναπαριστάται από την αντίστοιχο hash table) υπολογίζεται μέσω της htMeanOfCluster(...) το μέσο διάνυσμα του cluster αυτού, το οποιο θα αποτελέσει το νέο κεντροειδή του (αν το cluster ειναι άδειο, δεν περιέχει ακόμα διανύσματα, το κεντροειδή παραμένει το ίδιο).
 	 Μετά τον υπολογισμό του νέου κεντροειδούς για κάθε cluster, διαγράφουμε τα διανύσματα που έχουν εκχωρηθεί σε αυτό και προχωράμε σε νέα ανάθεση διανυσμάτων με βάση τώρα τα καινούρια κεντροειδή.
	 (η παραπάνω διαδικασία παραλείπεται την πρώτη φορά που καλείται η συνάρτηση reverseAssignmentLSH(...) καθώς τα κεντροειδή έχουν αρχικοποιηθέι προηγουμένως απο την kmeans++)

	-Έπειτα, έχουμε την διαδικασία ανάθεσης κάθε διανύσματος του input στο αντιστοιχό cluster (με βάση τα κεντροειδή). 
	 Αρχικά, βρίσκουμε την μικρότερη απόσταση μεταξυ των κεντροειδών και την διαιρούμε δια 2, η απόσταση αυτή θα αποτελέσει
	 την αρχική ακτίνα αναζήτησης. Ακολούθως, εφαρμόζουμε επαναληπτικά την παρακάτω διαδικασία μεχρις ώτου να ανατεθούν στα clusters τουλάχιστον το 80% των διανυσμάτων 
	 ή πραγματοποιηθεί ενας συγκεκριμένος αριθμός επαναλήψεων ή ακόμα αν ο αριθμός των αναθέσεων που έγιναν στην τρέχουσα επανάληψη είναι ο ίδιος με
	 τον αριθμό των αναθέσεων που έγιναν στην προηγούμενη. 
         Έτσι, σε κάθε cluster μέσω την συνάρτησης radiusNeigborsLSH(...) (radiusNeigborsClustering()-> htFindNeighborsInRadiusClustering()-> listFindNeighborsInRadiusClustering()) ανατίθονται διανύσματα.
	 Συγκεκριμένα, κάνουμε αναζήτηση με βάση την ακτίνα (range search με LSH) που υπολογίστηκε (όπως και στην συνάρτηση listFindNeighborsInRadius(...)) μόνο που επιπλέον για 
	 κάθε ενα διάνυσμα που συναντάται στο αντιστοιχο 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 διαγράφεται, η ακτίνα διπλασιάζεται και εκτελείται η ιδια διαδικασία επαναληπτικά.


	


	► HyperCube:

		→

		→

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

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

	-Οι παραπάνω αλγόριθμοι ουσιαστικά διαφέρουν μονο στο βήμα της ανάθεσης των διανυσμάτων στα αντίστοιχα clusters. Η αρχικοποίηση (kmeans++) και η εύρεση του μέσου παρεμένει ίδια και στους 3 αλγορίθμους που 
	 υλοποιήσαμε.
	- Στην λίστα με τα conflicts πιθανόν υπάρχουν διπλότυποι κόμβοι που αφορούν τα ίδια διανύσματα, όταν όμως πραγματοποιηθέι η ανάθεση ενός διανύσματος σε ένα cluster, τότε στο διάνυσμα αποθηκεύεται στο πεδίο της ακτίνας (assignedAtRadius)
	  η τιμή -3.0, έτσι αν ξανα συναντηθεί στην λίστα το ίδιο διάνυσμα με έναν ελεγχο (getAssignedAtRadius(temp->v)<-1.0) καταφέρνουμε απλά να παραλείπεται.