Back to search

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 × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:3336118

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Σταματίου Αθηνά; Stamatiou Athina. Node Community Participation for Enhancing Stream-Based Edge Partitioning. 2023. https://pergamos.lib.uoa.gr/uoa/dl/object/3336118