InvertedSearchEngine

Κ23α Ανάπτυξη Λογισμικού για Πληροφοριακά Συστήματα, Χειμερινό Εξάμηνο 2021 ~ SIGMOD-2013

Team

• Δημήτρης Μπέρος
• Γιώργος Κοκκίνης
• Σταύρος Κωστόπουλος

Δομές

Map

Αναπαριστά ένα κείμενο
Τα collisions χειρίζονται με separate chaining
Το κάθε bucket (MapNode) αναπαριστάται από ένα Binary Search Tree
Κάθε λέξη, αν είναι μοναδική, γίνεται insert στο Bst του bucket της hash position της
Το max load factor είναι 0,9 και αν μεγαλώσει σε κάποιο insert τότε συμβαίνει rehash

Binary Search Tree

Ένα δυαδικό δέντρο αναζήτησης που χρησιμοποιείται στο Map
Διάταξη με βάση την strcmp και γίνεται είσοδος μοναδικών strings
Όλες οι λειτουργίες γίνονται αναδρομικά
Καλείται πάντα μια βοητική bst_node_ συνάρτηση με όρισμα τη ρίζα στην αντίστοιχη bst συνάρτηση

Dictionary

Το dictionary είναι το Hash Table για τα entries
Κάθε bucket αναπαρίσταται από μία entry list
Το deduplication για τα entries γίνεται στο dictionary
Αν υπάρχει ήδη η λέξη, απλώς μπαίνει ένα νέο QueryID στο payload του entry

Entries

Λέξη με λίστα για payload
Το payload περιέχει τα QueryIDs που υπάρχει η λέξη

List

Απλά συνδεδεμένη λίστα για το Payload των Entries

BK-Τree

Μία ρίζα με ένα σύνολο από Vectors για κάθε δυνατή απόσταση
Η ρίζα δέχεται ένα τυχαίο entry
Τα υπόλοιπα γίνονται insert στο κατάλληλο Vector ανάλογα την απόσταση από τη ρίζα
Χρησιμοποιείται για το match Edit και Hamming Distance Queries

Query Vector

Το active Query Set
Περιέχει όλες τις πληροφορίες για τα ενεργά Queries

Priority Queue

Ουρά προτεραιότητας για ταξινόμηση των Query αποτελεσμάτων

Hash Table

Hash Table για εύρεση Query αποτελεσμάτων
Γίνεται hash το QueryID
Αν έχουν ταιριάξει όλες οι λέξης από ένα Query τότε έχει γίνει match 

LinkedList

Απλά συνδεδεμένη λίστα για Strings

Queues

FIFO Queues για Jobs | Documents

Tests

cd test/tests
make
make run | make valgrind 
make clean
ή ξεχωριστα π.χ make BK-Tree_Test && ./BK-Tree_Test

Multithread

cd test/testdriver
make
make run | make valgrind
make clean

Job Scheduler με 3 διαφορετικές ουρές
- Start | End Query
- MatchDocument
- GetNextAvailRes

- Start | End Query :
    Εισαγωγή και αφαίρεση Entries και Queries στις δομές

- MatchDocument :
    Για να αρχίσει πρέπει να έχουν τελειώσει όλα τα Start | End Query από το batch
    Σε κάθε ολοκληρωμένο Query Job γίνεται έλεγχος αν Total Jobs = Finished Jobs
    Στέλνεται signal σε αυτή την περίπτωση
    Αν δεν έχουν τελειώσει όλα τα Jobs όταν έρθει το πρώτο Document τότε ένα thread περιμένει
    Όταν τελειώσει ένα Document τότε γίνεται εισαγωγή στην ουρά των ready Documents

- GetNextAvailRes
    Το main thread περιμένει σε σηματοφόρο για ready Document 
    Περιμένει σε barrier για τα αποτελέσματα από ένα GetNextAvailRes thread που έχει κάνει post
    Όταν ένα thread τελειώσει τότε εισάγει το Document σε άλλη ουρά για διαγραφή στη DestroyIndex