National and Kapodistrian University of Athens
Lakon: Επιτάχυνση κομβοκεντρικού μοντέλου επεξεργασίας γράφων, αποτρέποντας τη διάδοση εσφαλμένης πληροφορίας.
Abstract
dc:descriptionΣτα πλαίσια αυτής της διπλωματικής, ασχολούμαστε με την επιτάχυνση του κομβοκε- ντρικού μοντέλου για την επεξεργασία μεγάλων γράφων έτσι ώστε να αντιμετωπίσουμε καλύτερα τα προβλήματα άλγεβρας μονοπατιών (π.χ., ομοαφετηριακές συντομότατες δια- δρομές) και τις παραλλαγές τους (π.χ., συνδεδεμένες συνιστώσες). Γενικά, τα συστήματα που βασίζονται στο κομβοκεντρικό μοντέλο, εκτελούν μία παράλληλη κατά πλάτος αναζή- τηση (breadth-first-search) και εφαρμόζουν κατάλληλα την συνάρτηση που έχει ορίσει ο χρήστης. Παρόλο που αυτή η γενική προσέγγιση κλιμακώνει καλά σε μεγάλα γραφήματα και είναι η βάση πολλών συστημάτων του πραγματικού κόσμου, όπως το Google Pregel και το Apache Giraph, δεν εκμεταλλεύεται τις αλγεβρικές ιδιότητες της συνάρτησης. Το σύστημα μας, το Lakon, εξειδικεύεται σε προβλήματα άλγεβρας μονοπατιών και εισάγει αναζητήσεις βάσει προτεραιοτήτων αντί για την παράλληλη κατά πλάτος αναζήτηση. Διε- ξοδικά πειράματα δείχνουν σημαντική αύξηση της απόδοσης συγκριτικά με την απλή υλοποίηση του κομβοκεντρικού μοντέλου.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Καράμπελας Θωμάς
Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:1321196