National and Kapodistrian University of Athens
Node Community Participation for Enhancing Stream-Based Edge Partitioning
Abstract
dc:descriptionΗ διαμέριση ακμών είναι ένα κρίσιμο βήμα προεπεξεργασίας για τη βελτιστοποίηση κατανεμημένων υπολογιστικών εργασιών σε γράφους. Περιλαμβάνει τη διαχωρισμό του γράφου σε μικρότερους υπο-γράφους, ώστε να είναι δυνατοί οι ταυτόχρονοι υπολογισμοί και να μειωθεί η επιβάρυνση σε χρόνο και κόστος. Ο στόχος της διαμέρισης ακμών είναι να χωριστεί ο δεδομένος γράφος σε έναν δεδομένο αριθμό διαμερίσεων, ελαχιστοποιώντας παράλληλα την αναπαραγωγή κορυφών μεταξύ τους. Με τον τρόπο αυτό ελαχιστοποιούνται τα ερωτήματα που ανταλλάσσονται μεταξύ των διαμερίσεων και βελτιώνονται οι επιδόσεις. Η διαμέριση ακμών μπορεί να κατηγοριοποιηθεί ως stateful ή stateless. Η stateful προσέγγιση οδηγεί σε καλύτερα αποτελέσματα αλλά με υψηλότερο κόστος, ενώ η stateless προσέγγιση είναι ταχύτερη αλλά οδηγεί σε αποτελέσματα χαμηλότερης ποιότητας. Η παρούσα μελέτη επεκτείνει τον αλγόριθμο διαμέρισης 2PS-L, ο οποίος βασίζεται στο stateful μοντέλο ροής ακμών και έχει γραμμικό χρόνο εκτέλεσης. Ο αλγόριθμος 2PS-L αποτελείται από δύο φάσεις: ομαδοποίηση κορυφών και διαμέριση ακμών με βάση τις ομάδες που δημιουργούνται στην αρχική φάση. Στην παρούσα διπλωματική εργασία, εστιάζουμε στη βελτίωση της φάσης συσταδοποίησης, προκειμένου να επιτύχουμε χαμηλότερο παράγοντα αναπαραγωγής σε σύγκριση με την αρχική προσέγγιση. Η ελαχιστοποίηση του παράγοντα αναπαραγωγής στην διαμέριση γράφων συμβάλλει στη βελτιστοποίηση της χρήσης του αποθηκευτικού χώρου, στην ενίσχυση της εξισορρόπησης φορτίου, στη μείωση της επιβάρυνσης επικοινωνίας και στην απλοποίηση του ελέγχου συνέπειας και ταυτόχρονης λειτουργίας, οδηγώντας σε πιο αποδοτικά κατανεμημένα συστήματα επεξεργασίας γράφων. Εστιάζουμε επίσης στα ποιοτικά χαρακτηριστικά της προσέγγισής μας: ανεξαρτησία σειράς ροής ακμών και απαίτηση για ένα μόνο πέρασμα. Ο αρχικός αλγόριθμος 2PS-L εξαρτάται σε μεγάλο βαθμό από τη σειρά της ροής των ακμών του γράφου και απαιτεί τουλάχιστον δύο περάσματα μέσω της ροής ακμών. Αντίθετα, η προσέγγισή μας είναι ανεξάρτητη από τη σειρά της ροής ακμών και απαιτεί μόνο ένα πέρασμα.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Σταματίου Αθηνά
- Stamatiou Athina
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:3336118