Repository files navigation

• Γλώσσα Υλοποίησης: C++11
• Μεταγλώττιση:g++ (έγινε modularization των αρχείων σε directories και χρήση τουmake)
• Επαλήθευση Ορθότητας Κώδικα:Unit Tests με την χρήση της βιβλιοθήκηςAcutest (η εκτέλεση των test γίνεται μέσω ένος makefile rule)
• Mέσω της χρήσηςGithub Actions εξασφαλίσαμε σε κάθε στάδιο ανάπτυξης του δεύτερου μέρους του Project την ορθή λειτουργία του κώδικα που γινόταν pushed στο main branch.

• Μεταγλώττιση του Κώδικα🛠️

  Για την κατασκευή των εκτελέσιμων αρχείων παρέχονται διάφορες εντολές που εξασφαλίζουν τη μεταγλώττιση της κύριας εφαρμογής, των unit tests, καθώς και συνδιασμό τους:

  • Για την μεταγλώττιση της κύριας εφαρμογής:

    make app

  • Για την μεταγλώττιση των unit tests

    make tests

  • Για την μεταγλώττιση και των δύο:

    make all

• Εκτέλεση των Unit Tests🧪

  Για την εκτέλεση τωνunit tests παρέχονται δύοmakefile rulew με τα οποία εκτελούνται όλα τα unit tests, απλά, είτε με τη χρήση τουvalgrind για έλεγχο της κατάστασης της μνήμης. Οι αντίστοιχες εντολές είναι:

  • Απλή Εκτέλεση:

    make run_tests

  • Εκτέλεση με Valgrind:

    make run_tests_valgrind

• Εκτέλεση Εφαρμογής▶️

  Η εφαρμογή στηρίζεται πάνω σεένα εκτελέσιμο αρχείο το οποίο αφού μεταγλωττίσετε τον κώδικα μπορείτε να το βρείτε στο/bin/main. Αυτό το εκτελέσιμο αρχείο είναι υπεύθυνο για την εκτέλεση όλων των αλγορίθμων, χρησιμοποιώντας κατάλληλαcommand line arguments τα οποία περιγράφονται παρακάτω. Μερικά ενδεικτικά παραδείγματα όλων των λειτουργιών που προφέρει η εφαρμογή έχουν συμπιεστεί σε κατάλληλα makefile rules τα οποία είναι:

  • Δημιουργία Simple Vamana:

    make create_simple_via

  • Δημιουργία Filtered Vamana:

    make create_filtered_via

  • Δημιουργία Stiched Vamana:

    make create_stiched_via

  καθώς επίσης και δοκιμές πάνω σεαποθηκευμένα indexes:

  • Δοκιμή Simple Vamana:

    make test_simple_via

  • Δοκιμή Filtered Vamana:

    make test_filtered_via

  • Δοκιμή Stiched Vamana:

    make test_stiched_via

make compute_groundtruth

• Καθαρισμός αρχείων🧹

  Για τον καθαρισμό των αντικειμενικών(object files) και των εκτελέσιμων αρχείων(executable files) χρησιμοποιείται η εντολή:

   make clean

• Πρώτο Μέρος (Simple VIA):

  Ταδεδομένα που χρησιμοποιούνται για τον ΑλγόριθμοVΙΑ του πρώτου μέρους, είναι ένα σετ διανυσμάτων128 διαστάσεων (με αριθμούς κινητής υποδιαστολής (float)). Στον κώδικά μας αξιοποιήσαμε το σετ δεδομένωνANN_SIFT10K. το οποίο περιέχει:

  Όνομα Αρχείου	Πλήθος στοιχείων	Διάσταση στοιχείων
  shiftsmall_base.fvecs	10.000	128
  shiftsmall_query.fvecs	100	128
  shiftsmall_groundtruth.ivecs	100	100

  όπου:

  • shiftsmall_base.fvecs:10.000base vectors διάστασης128. Κάθε vector θα αντιστοιχεί σε ένα κόμβο του γράφουVamana, και περιέχει 128 floats.
  • shiftsmall_query.fvecs:100query vectors διάστασης128 τα οποία αναπαριστούν τα"search" vectors μας. O VIA θα υπολογίσει τους πλησιέστερους γείτονες αυτών των vectors.
  • shiftsmall_groundtruth.ivecs: Αυτό το αρχείο, για κάθε query vector, περιέχει100 ακέραιες τιμές που αντιπροσωπεύουν τουςidentifiers (start 0) τωνbase vectors που είναι οι εγγύτεροι γείτονές τους.

• Δεύτερο Μέρος (Filtered & Stiched VIA):

  Στο δεύτερο μέρος του project χρησιμοποιήσαμεδεδομένα μεφίλτρα τα οποία απαιτούν μία επιπλέον λειτουργικότητα στη διαδικασία κατασκευής τουVIA. Συγκεκριμένα στην υλοποίησή μας χρησιμοποιήσαμε τοDummy Dataset το οποίο παρέχει:

  Όνομα Αρχείου	Πλήθος στοιχείων	Διάσταση στοιχείων	Επιπλέον Παράμετροι
  dummy-data.bin	10.000	100	2
  dummy-queries.bin	1000	100	4

  όπου:

  • dummy-data.bin:10.000base vectors διάστασης100. Κάθε vector αντιστοιχεί σε ένα κόμβο του γράφουFiltered Vamana, και περιέχει100 floating values και2 επιπλέον παράμετροι που υποδεικνύουν ταφίλτρα του εκάστοτε vector. Κάθεbase vector έχει ένα συγκεκριμένο φίλτρο το οποίο καθορίζεται από τις αυτές τις δύο παραμέτρους. Συγκεκριμένα οι 2 επιπλέον παράμετροι είναι:

    • C (Categorical Attribute) και
    • T (Timestamp Attribute)

  • dummy-queries.bin:1000query vectors με100 floating values και4 επιπλέον παραμέτρους που επεξηγούν τι είδουςquery vector είναι και τι φίλτρα περιέχουν. Συγκεκριμένα οι επιπλέον παράμετροι είναι:

    • Query Type: Υποδεικνύει το είδος τουquery vector και παίρνει τιμές${0, 1, 2, 3}$.
    • v (Categorical Query Attribute): Σχετίζεται άμεσα με τοC τωνbase vectors και παίρνει ακέραιες τιμές.
    • l (Left Timestamp Query Attribute): Σχετίζεται άμεσα με τοT τωνbase vectors και παίρνει πραγματικές τιμές.
    • r (Right Timestamp Query Attribute): Σχετίζεται άμεσα με τοT τωνbase vectors και παίρνει πραγματικές τιμές.

    Κάθεquery vector αναπαριστά ένα"search" vector. Οι αλγόριθμοιFiltered VIA καιStiched VIA υπολογίζουν τους πλησιέστερους γείτονες αυτών των vectors.

Σε αυτό το Project κληθήκαμε να υλοποιήσουμε τον ΑλγόριθμοVamana Indexing, o oποίος λειτουργεί ως μία Προσεγγιστική Λύση του Προβλήματος της Εύρεσης των Κ-Εγγύτερων Γειτόνων, μέσω της χρήσης κατευθυνόμενου γράφου για την αναπαράσταση και επεξεργασία των δεδομένων, τόσο γιαfiltered όσο και γιαunfiltered δεδομένα. Η υλοποίησή μας στηρίχθηκε πάνω στα άρθρα:

• DiskANN:Fast Accurate Billion-point Nearest Neighbour Search on a Single Node Search (2019)
• Filtered − DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters (2023)

Πιο συγκεκριμένα, μας ζητήθηκε να υλοποιήσουμε τους εξής αλγορίθμους:

• Πρώτο Μέρος:
  • VamanaIndex()
  • GreedySearch()
  • RobustPrune()
  • FindMedoid()
  • RecallEvaluation()
• Δεύτερο Μέρος:
  • FilteredVamanaIndex()
  • StichedVamanaIndex()
  • FilteredGreedySearch()
  • FilteredRobustPrune()
  • FilteredFindMedoids()

Στην Ανάπτυξη του Project αξιοποιήθηκε το εργαλείοIssues του github για την επικοινωνία και τον συγχρονισμό των διεργασιών που είχε αναλάβει να διεκπεραιώσει το κάθε μέλος της ομάδας.

Καθ' όλη την διάρκεια της ανάπτυξης του Project υπήρξε συνεχείς επικοινωνία των μελών τόσο μέσω των εργαλείων του github όσο και με προγραμματισμένα online calls.

• Ζήκας Αντώνιος (1115202100038)

  • Υλοποίηση της βασικής κλάσηςVectorData και των μεθόδων της, για την αποθήκευση των δεδομένων των διανυσμάτων που διαβάζουμε από τα αρχεία.fvecs και.bin.
  • Υλοποίηση των κλάσεων και των μεθόδωνgraph_node καιgraph. Δομές πάνω στις οποίες στηρίζεται ο αλγόριθμος για την δημιουργία τωνVamana Indexes.
  • Υλοποίηση καιβελτιστοποίηση της συνάρτησηςCreateVamanaIndex().
  • Συμβολή στηναποσφαλμάτωση καιβελτιστοποίηση του αλγορίθμουGreedySearch().
  • Υλοποίηση συνάρτησηςReadGroundtruth(), για την ανάγνωση των ακέραιων δεδομένων του αρχείουshiftsmall_groundtruth.ivecs.
  • Υλοποίηση συνάρτησηςCalculateRecallEvaluation(), για την εξέταση της εγκυρότητας των αποτελεσμάτων τουANN Vamana Index, βάσει των τιμών τουshiftsmall_groundtruth.ivecs.
  • Υλοποίηση τωνUnit Test για τις μεθόδους τουgraph καιgraph_node.
  • Ολική συμβολή στηνβελτιστοποίηση καιαποσφαλμάτωση κώδικά για την ομαλή εκτέλεση των επιμέρους συναρτήσεων.
  • Προσθήκη γραφικής αναπαράστασης της προόδου κάθε αλγορίθμου.
  • Συμβολή στη δημιουργία συναρτήσεων για τοδιάβασμα των δεδομένων.
  • Δημιουργία συναρτήσεων για τονυπολογισμό, τηναποθήκευση και τηφόρτωση τουGroundtruth.
  • Συμβολή στηνυλοποίηση της συνάρτησηςfindFilteredMedoid()
  • Δημιουργία κλάσεωνVamanaIndex,FilteredVamana καιStichedVamana

• Χασιώτη Ευανθία (1115202100289)

  • Υλοποίηση της βασικής δομής του αλγορίθμουGreedySearch().
  • Υλοποίηση καισυμβολή στηνβελτιστοποίηση της συνάρτησηςRobustPrune().
  • Υλοποίηση της συνάρτησηςFindMediod(), για την εύρεση του μέσου κόμβου του γράφου.
  • Συμβολή στηνασποσφαλμάτωση καιβελτιστοποίηση της συνάρτησηςCreateVamanaIndex().
  • Ολική συμβολή στηνβελτιστοποίηση καιαποσφαλμάτωση κώδικά για την ομαλή εκτέλεση των επιμέρους συναρτήσεων.
  • Υλοποίηση της συνάρτησηςFilteredGreedySearch()
  • Υλοποίηση της συνάρτησηςFilteredRobustPrune()
  • Συμβολή στηνυλοποίηση της κλάσηςStichedVamana

• Κώτσιλας Σταύρος (1115201700292)

  • Υλοποίηση των συναρτήσεωνReadVectorFile() καιSaveVector(), για την ανάγνωση και αποθήκευση των δεδομένων των διανυσμάτων των αρχείων.fvecs.
  • Υλοποίηση τωνUnit Tests για τις συναρτήσειςReadVectorFile() καιSaveVector().
  • Συμβολή στονεμπλουτισμό καιβελτιστοποίηση της κλάσηςVectorData, για την ορθότερη αποθήκευση και επεξεργασία των δεδομένων.
  • Συμβολή στηνασποσφαλμάτωση καιβελτιστοποίηση της συνάρτησηςCreateVamanaIndex().
  • Documentation του project / συγγραφή του αρχείουREADME.md.
  • Ολική συμβολή στηνβελτιστοποίηση καιαποσφαλμάτωση κώδικά για την ομαλή εκτέλεση των επιμέρους συναρτήσεων.
  • Υλοποίηση της συνάρτησηςfilteredFindMedoid()
  • Επέκταση της κλάσηςDataVector και δημιουργία των υποκλάσεωνBaseDataVector καιQueryDataVector

Η υλοποίηση των αλγορίθμων έγινε σύμφωνα με τους ψευδοκώδικες που παρουσιάζονται στο άρθρο, και φαίνονται παρακάτω:

Οι βασικότερες κλάσεις και μέθοδοι που υλοποιήθηκαν συμπληρωματικά αυτών που ζητήθηκαν στην εκφώνηση είναι:

1. ΣυναρτήσειςFindMedoid() καιFilteredFindMedoid(), για την εύρεση του ενδιάμεσου στοιχείου του συνόλου G, που παράγεται μέσα στην Vamana και του ενδιάμεσου στοιχείου για κάθε φίλτρο.
2. ΣυνάρτησηCalculateRecallEvaluation() , για την εξέταση της εγκυρότητας των αποτελεσμάτων του ANN Vamana Index, βάσει των τιμών τουGroundtruth.
3. ΚλάσειςDataVector,BaseDataVector καιQueryDataVector, για την αποθήκευση των δεδομένων των αρχείων με ταbase vectors.
4. ΚλάσειςGraph καιGraphNode. Δομές τι οποίες αξιοποιεί οVIA.
5. ΣυναρτήσειςReadVectorFile() καιSaveVector(), για την ανάγνωση και αποθήκευση των δεδομένων.
6. ΣυναρτήσειςEuclidianDistance() καιManhattanDistance(), για τον υπολογισμό της απόστασης μεταξύ των διανυσμάτων.
7. ΚλάσειςVamanaIndex,FilteredVamanaIndex καιStichedVamanaIndex με τις δικές τους μεθόδους για την αναπαράσταση των indexes.
8. ΣυναρτήσειςwithProgress() καιdisplayProgressBar() για την οπτικοποίηση της προόδου του κάθε αλγορίθμου.

Μία ενδεικτική εκτέλεση της εφαρμογής μπορεί να είναι η εξής:

make all# Create and test simple vamana./bin/main --create -index-type'simple' -base-file'data/siftsmall/siftsmall_base.fvecs' -L 120 -R 12 -alpha 1.0 -save'simple_index.bin'./bin/main --test -index-type'simple' -load'simple_index.bin' -k 100 -L 120 -gt-file'data/siftsmall/siftsmall_groundtruth.ivecs' -query-file'data/siftsmall/siftsmall_query.fvecs' -query 1# Compute groundtruth for filtered and stiched indexes./bin/main --compute-gt -base-file'data/Dummy/dummy-data.bin' -query-file'data/Dummy/dummy-queries.bin' -gt-file'data/Dummy/dummy-groundtruth.bin'# Create and test filtered vamana./bin/main --create -index-type'filtered' -base-file'data/Dummy/dummy-data.bin' -L 120 -R 12 -alpha 1.0 -save'filtered_index.bin'./bin/main --test -index-type'filtered' -load'filtered_index.bin' -L 120 -k 100 -gt-file'data/Dummy/dummy-groundtruth.bin' -query-file'data/Dummy/dummy-queries.bin' -query 1# Create and test stiched vamana./bin/main --create -index-type'stiched' -base-file'data/Dummy/dummy-data.bin' -L-small 150 -R-small 12 -R-stiched 20 -alpha 1.0 -save'stiched_index.bin'./bin/main --test -index-type'stiched' -load'stiched_index.bin' -L 120 -k 100 -gt-file'data/Dummy/dummy-groundtruth.bin' -query-file'data/Dummy/dummy-queries.bin' -query 1make clean

Μερικά από τα command line arguments που χρησιμοποιούνται αντιστοιχούν στις παραμέτρους του ψευδοκώδικα και συγκεκριμένα:

• -k, ο αριθμός των εγγύτερων γειτόνων που θέλουμε να βρούμε.
• -alpha, πολλαπλασιαστικός παράγοντας μείωσης απόστασης προς το query vector.
• -L, η λίστα με τους πλησιέστερους κόμβους / γείτονες του query vector.
• -R, ο μέγιστος αριθμός εξερχόμενων ακμών που θα έχει ο κάθε κόμβος.
• -query, το Index του query vector για το οποίο θέλουμε να βρούμε τους εγγύτερους γείτονες.

Η εκτέλεση τουVamana Indexing Algorithm γίνεται σε τρεις φάσεις:

• Initialization Phase:

  Στο Initialization phase, γίνεται η ανάγνωση και η αποθήκευση των δεδομένων μας από τα datasetsSiftsmall καιDummy.

• Vamana Phase:

  Σε δεύτερη φάση, ξεκινά η δημιουργία του ευρετηρίου (index) χρησιμοποιώντας μία από τις κλάσειςVamana,FilteredVamana καιStichedVamana. Η δημιουργία των γράφων γίνεται μέσω της μεθόδουcreateGraph() η οποία περιέχεται μέσα σε κάθε κλάση.

  Κατά τη διαδικασία της κατασκευής, κάθεDataVector που περιέχει τα δεδομένα μας αποθηκεύεται σε έναGraphNode όπου πολλά αντικείμενα αυτού του τύπου, μαζί αποτελούν το γράφο (Graph).

  Ύστερα ακολουθεί η διαδικασία εμπλουτισμού αυτού του γράφου με βάση των εκάστοτε αλγόριθμο vamana, η οποία χρησιμοποιεί τους αλγορίθμουςGreedySearch καιRobustPrune και τιςfiltered εκδοχές τους.

• Validity Phase:

  Στην τελευταία φάση του αλγορίθμου, εκτελείται ο αλγόριθμος τηςGreedySearch για τον υπολογισμό τωνK εγγύτερων γειτόνων, και ακολουθεί η μέθοδοςCalculateRecallEvaluation(), η οποία εξετάζει την εγκυρότητα των αποτελεσμάτων που επιστράφηκαν από την δεύτερη φάση, με τις τιμές που βρίσκονται στο εκάστοτε αρχείο με ταbase vectors και επιστρέφει το ποσοστό "ομοιότητας" των προσεγγιστικών τιμών τουVIA με την πραγματική τιμή τουK.