Μπότσιος Ιωάννης 1115202200111
Έξαρχος Θεόδωρος 1115202200045

Neural-LSH

Το πρόγραμμα χωρίζεται σε δύο φάσεις:

• Build phase: Χτίσιμο και training του μοντέλου, δημιουργία ευρετηρίου
• Search phase: Χρήση του μοντέλου και του ευρετηρίου για k-NN αναζήτηση

Πριν ξεκινήσετε να τρέχετε το πρόγραμμα, μπείτε στον φάκελο Neural-LSH και δημιουργήστε ένα virtual environment:

python3 -m venv .venv
source .venv/bin/activate

(Σε αυτή την εργασία εμείς χρησιμοποιήσαμε το .venv.)

Εγκαταστήστε τις απαραίτητες βιβλιοθήκες:

pip install torch --index-url https://download.pytorch.org/whl/cu121
pip install kahip numpy scikit-learn

ή

pip install -r requirements.txt

extra:

pip install -r scripts_requirements.txt

για εκτέλεση των scripts

---

1. Build phase

Οδηγίες Χρήσης

Για εκτέλεση:

Αρχικά, σιγουρευτείτε ότι υπάρχει το εκτελέσιμο build_knn. Μπείτε στον φάκελο IVFFlat_build_knn και εκτελέστε:

make

Έπειτα επιστρέψτε στο root και κάντε build

python3 build/nlsh_build.py ...

(όπου στις ... συμπληρώνεται τα ορίσματα)

Υποχρεωτικά Ορίσματα

• -d <input file> Το αρχείο του συνόλου δεδομένων

• -i <index path> Το path όπου θα αποθηκευτούν τα αρχεία του ευρετηρίου

• -type <sift|mnist> Ο τύπος των δεδομένων

Προαιρετικά Ορίσματα (με default τιμές)

• --knn <int> — Αριθμός γειτόνων k για k-NN γράφο (Default: 10)
• -m <int> — Αριθμός μερών (blocks/parts) m για KaHIP (Default: 100)
• --imbalance <float> — Ποσοστό ανισορροπίας ϵ (Default: 0.03)
• --kahip_mode <int> — Λειτουργία KaHIP (0=FAST, 1=ECO, 2=STRONG) (Default: 2)
• --layers <int> — Αριθμός στρωμάτων MLP (Default: 3)
• --nodes <int> — Αριθμός κόμβων ανά hidden layer (Default: 64)
• --epochs <int> — Περίοδοι εκπαίδευσης (Default: 10)
• --batch_size <int> — Μέγεθος batch (Default: 128)
• --lr <float> — Learning rate (Default: 0.001)
• --seed <int> — Φύτρο ψευδοτυχαιότητας (Default: 1)

extra:

• --knn_mode <approx|brute> — Χρήση IVFFlat ή Brute Force για την κατασκευή του γράφου (Default: approx)

Αρχεία που δημιουργούνται

Στο τέλος, μέσα στον φάκελο <index_path> παράγονται:

• inverted_file.pkl — το ευρετήριο
• model.pth — το εκπαιδευμένο μοντέλο
• meta.pkl — βοηθητικές πληροφορίες για φόρτωση του μοντέλου στο search

---

2. Search phase

Οδηγίες Χρήσης

Για εκτέλεση:

python3 search/nlsh_search.py ...

(όπου στις ... συμπληρώνεται τα ορίσματα)

Υποχρεωτικά Ορίσματα

• -d <input file> — Το αρχείο του συνόλου δεδομένων
• -q <query file> — Το αρχείο ερωτημάτων
• -i <index path> — Το path του ευρετηρίου που δημιουργήθηκε από το nlsh_build.py
• -o <output file> — Το αρχείο εξόδου
• -type <sift|mnist> — Ο τύπος των δεδομένων

Προαιρετικά Ορίσματα

• -N <int> — Αριθμός πλησιέστερων γειτόνων (Default: 1)
• -R <double> — Ακτίνα αναζήτησης (Default: 2000 για MNIST, 2800 για SIFT)
• -T <int> — Αριθμός bins στο multi-probe (Default: 5)
• -range <true|false> — Ενεργοποίηση range search (Default: true)

---

3. Σύνοψη Κάθε Αρχείου

common/

• load_data.py — Περιέχει τις συναρτήσεις ανάγνωσης και μετατροπής δεδομένων από input και query files ανάλογα με το αν είναι τύπου mnist ή sift.

• models.py — Περιέχει την δομή του MLP ταξινομητή. Ο αριθμός hidden layers καθορίζεται από το όρισμα --layers <int> στο nlsh_build.py.

---

build/

• build_args.py — Διαβάζει και ελέγχει τα command line arguments του nlsh_build.py, επαληθεύοντας τα υποχρεωτικά και θέτοντας default τιμές στα υπόλοιπα.

• build_graph.py — Συναρτήσεις για:

1. κατασκευή k-NN γράφου
2. μετατροπή σε μη κατευθυνόμενο γράφο με κατάλληλα βάρη
3. μετατροπή σε CSR ώστε να μπορεί να χρησιμοποιηθεί από KaHIP

• nlsh_build.py — Εκτελεί τα ακόλουθα:

1. διαβάζει τα δεδομένα
2. κατασκευάζει τον k-NN γράφο
3. τον μετατρέπει σε CSR
4. χρησιμοποιεί KaHIP για ισοκατανεμημένη διαμέριση σε m μέρη
5. εκπαιδεύει MLP
6. αποθηκεύει μοντέλο, metadata και inverted file στον φάκελο index_path

---

search/

• search_args.py — Ανάγνωση και έλεγχος των arguments του nlsh_search.py.

• nlsh_search.py — Για κάθε query:

1. φορτώνει μοντέλο και inverted file
2. υπολογίζει την έξοδο του MLP
3. εντοπίζει τα κατάλληλα buckets από το inverted file
4. εκτελεί εξαντλητική αναζήτηση πάνω στους υποψηφίους
5. εκτελεί ξεχωριστά brute-force search για πραγματικούς k-NN
6. (προαιρετικά) εκτελεί range search αν έχει οριστεί

IVFFlat_build_knn/

• build_knn.cpp — Εκτέλεση kNN αναζήτησης με την χρήση IVFFlat και αποθήκευση αποτελεσμάτων σε .bin αρχείο

• Makefile — Αρχείο για εύκολο compile του c++ κώδικα με την χρήση της εντολής 'make'

• IVFFlat/IVFFlat.cpp(και .hpp) — Header file και υλοποίηση του αλγόριθμου IVFFlat.

---

scripts/

• run_build_grid.py — Εκτέλεση του nlsh_build.py με όλες τις ορισμένες παραμέτρους

• run_nlsh_experiments.sh — Εκτέλεση του nlsh_search.py με όλες τις ορισμένες παραμέτρους

• summarize_ann_results.py — Δημιουργία .csv αρχείου με βάση τα προϋπολογισμένα αποτελέσματα και διαγραμμάτων μεταξύ QPS/Recall και AverageAF/Recall

• summarize_to_latex.py — Δημιουργία κώδικα latex που προβάλλει τα προϋπολογισμένα αποτελέσματα (τα λαμβάνει μέσο του .csv) σε μορφή πίνακα

• csv_finder.py — Εκτύπωση των καλύτερων αποτελεσμάτων με βάση τις προκαθορισμένες συνθήκες

---