{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:3336118"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:3336118","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Node Community Participation for Enhancing Stream-Based Edge Partitioning","abstract":"Η διαμέριση ακμών είναι ένα κρίσιμο βήμα προεπεξεργασίας για τη βελτιστοποίηση κατανεμημένων υπολογιστικών εργασιών σε γράφους. Περιλαμβάνει τη διαχωρισμό του γράφου σε μικρότερους υπο-γράφους, ώστε να είναι δυνατοί οι ταυτόχρονοι υπολογισμοί και να μειωθεί η επιβάρυνση σε χρόνο και κόστος. Ο στόχος της διαμέρισης ακμών είναι να χωριστεί ο δεδομένος γράφος σε έναν δεδομένο αριθμό διαμερίσεων, ελαχιστοποιώντας παράλληλα την αναπαραγωγή κορυφών μεταξύ τους. Με τον τρόπο αυτό ελαχιστοποιούνται τα ερωτήματα που ανταλλάσσονται μεταξύ των διαμερίσεων και βελτιώνονται οι επιδόσεις. Η διαμέριση ακμών μπορεί να κατηγοριοποιηθεί ως stateful ή stateless. Η stateful προσέγγιση οδηγεί σε καλύτερα αποτελέσματα αλλά με υψηλότερο κόστος, ενώ η stateless προσέγγιση είναι ταχύτερη αλλά οδηγεί σε αποτελέσματα χαμηλότερης ποιότητας. Η παρούσα μελέτη επεκτείνει τον αλγόριθμο διαμέρισης 2PS-L, ο οποίος βασίζεται στο stateful μοντέλο ροής ακμών και έχει γραμμικό χρόνο εκτέλεσης. Ο αλγόριθμος 2PS-L αποτελείται από δύο φάσεις: ομαδοποίηση κορυφών και διαμέριση ακμών με βάση τις ομάδες που δημιουργούνται στην αρχική φάση. Στην παρούσα διπλωματική εργασία, εστιάζουμε στη βελτίωση της φάσης συσταδοποίησης, προκειμένου να επιτύχουμε χαμηλότερο παράγοντα αναπαραγωγής σε σύγκριση με την αρχική προσέγγιση. Η ελαχιστοποίηση του παράγοντα αναπαραγωγής στην διαμέριση γράφων συμβάλλει στη βελτιστοποίηση της χρήσης του αποθηκευτικού χώρου, στην ενίσχυση της εξισορρόπησης φορτίου, στη μείωση της επιβάρυνσης επικοινωνίας και στην απλοποίηση του ελέγχου συνέπειας και ταυτόχρονης λειτουργίας, οδηγώντας σε πιο αποδοτικά κατανεμημένα συστήματα επεξεργασίας γράφων. Εστιάζουμε επίσης στα ποιοτικά χαρακτηριστικά της προσέγγισής μας: ανεξαρτησία σειράς ροής ακμών και απαίτηση για ένα μόνο πέρασμα. Ο αρχικός αλγόριθμος 2PS-L εξαρτάται σε μεγάλο βαθμό από τη σειρά της ροής των ακμών του γράφου και απαιτεί τουλάχιστον δύο περάσματα μέσω της ροής ακμών. Αντίθετα, η προσέγγισή μας είναι ανεξάρτητη από τη σειρά της ροής ακμών και απαιτεί μόνο ένα πέρασμα.","abstract_html":"Η διαμέριση ακμών είναι ένα κρίσιμο βήμα προεπεξεργασίας για τη βελτιστοποίηση κατανεμημένων υπολογιστικών εργασιών σε γράφους. Περιλαμβάνει τη διαχωρισμό του γράφου σε μικρότερους υπο-γράφους, ώστε να είναι δυνατοί οι ταυτόχρονοι υπολογισμοί και να μειωθεί η επιβάρυνση σε χρόνο και κόστος. Ο στόχος της διαμέρισης ακμών είναι να χωριστεί ο δεδομένος γράφος σε έναν δεδομένο αριθμό διαμερίσεων, ελαχιστοποιώντας παράλληλα την αναπαραγωγή κορυφών μεταξύ τους. Με τον τρόπο αυτό ελαχιστοποιούνται τα ερωτήματα που ανταλλάσσονται μεταξύ των διαμερίσεων και βελτιώνονται οι επιδόσεις. Η διαμέριση ακμών μπορεί να κατηγοριοποιηθεί ως stateful ή stateless. Η stateful προσέγγιση οδηγεί σε καλύτερα αποτελέσματα αλλά με υψηλότερο κόστος, ενώ η stateless προσέγγιση είναι ταχύτερη αλλά οδηγεί σε αποτελέσματα χαμηλότερης ποιότητας. Η παρούσα μελέτη επεκτείνει τον αλγόριθμο διαμέρισης 2PS-L, ο οποίος βασίζεται στο stateful μοντέλο ροής ακμών και έχει γραμμικό χρόνο εκτέλεσης. Ο αλγόριθμος 2PS-L αποτελείται από δύο φάσεις: ομαδοποίηση κορυφών και διαμέριση ακμών με βάση τις ομάδες που δημιουργούνται στην αρχική φάση. Στην παρούσα διπλωματική εργασία, εστιάζουμε στη βελτίωση της φάσης συσταδοποίησης, προκειμένου να επιτύχουμε χαμηλότερο παράγοντα αναπαραγωγής σε σύγκριση με την αρχική προσέγγιση. Η ελαχιστοποίηση του παράγοντα αναπαραγωγής στην διαμέριση γράφων συμβάλλει στη βελτιστοποίηση της χρήσης του αποθηκευτικού χώρου, στην ενίσχυση της εξισορρόπησης φορτίου, στη μείωση της επιβάρυνσης επικοινωνίας και στην απλοποίηση του ελέγχου συνέπειας και ταυτόχρονης λειτουργίας, οδηγώντας σε πιο αποδοτικά κατανεμημένα συστήματα επεξεργασίας γράφων. Εστιάζουμε επίσης στα ποιοτικά χαρακτηριστικά της προσέγγισής μας: ανεξαρτησία σειράς ροής ακμών και απαίτηση για ένα μόνο πέρασμα. Ο αρχικός αλγόριθμος 2PS-L εξαρτάται σε μεγάλο βαθμό από τη σειρά της ροής των ακμών του γράφου και απαιτεί τουλάχιστον δύο περάσματα μέσω της ροής ακμών. Αντίθετα, η προσέγγισή μας είναι ανεξάρτητη από τη σειρά της ροής ακμών και απαιτεί μόνο ένα πέρασμα.","abstract_has_math":false,"creators":["Σταματίου Αθηνά","Stamatiou Athina"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023","date_published":"2023","updated_at":"2026-11-19T06:22:53Z","subjects":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:3336118"],"render_values":[{"text":"uoadl:3336118","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3336118","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3336118","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A3336118","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Σταματίου Αθηνά","Stamatiou Athina"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Τεχνολογία – Πληροφορική","Technology - Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:3336118","https://pergamos.lib.uoa.gr/uoa/dl/object/3336118"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η διαμέριση ακμών είναι ένα κρίσιμο βήμα προεπεξεργασίας για τη βελτιστοποίηση κατανεμημένων υπολογιστικών εργασιών σε γράφους. Περιλαμβάνει τη διαχωρισμό του γράφου σε μικρότερους υπο-γράφους, ώστε να είναι δυνατοί οι ταυτόχρονοι υπολογισμοί και να μειωθεί η επιβάρυνση σε χρόνο και κόστος. Ο στόχος της διαμέρισης ακμών είναι να χωριστεί ο δεδομένος γράφος σε έναν δεδομένο αριθμό διαμερίσεων, ελαχιστοποιώντας παράλληλα την αναπαραγωγή κορυφών μεταξύ τους. Με τον τρόπο αυτό ελαχιστοποιούνται τα ερωτήματα που ανταλλάσσονται μεταξύ των διαμερίσεων και βελτιώνονται οι επιδόσεις. Η διαμέριση ακμών μπορεί να κατηγοριοποιηθεί ως stateful ή stateless. Η stateful προσέγγιση οδηγεί σε καλύτερα αποτελέσματα αλλά με υψηλότερο κόστος, ενώ η stateless προσέγγιση είναι ταχύτερη αλλά οδηγεί σε αποτελέσματα χαμηλότερης ποιότητας. Η παρούσα μελέτη επεκτείνει τον αλγόριθμο διαμέρισης 2PS-L, ο οποίος βασίζεται στο stateful μοντέλο ροής ακμών και έχει γραμμικό χρόνο εκτέλεσης. Ο αλγόριθμος 2PS-L αποτελείται από δύο φάσεις: ομαδοποίηση κορυφών και διαμέριση ακμών με βάση τις ομάδες που δημιουργούνται στην αρχική φάση. Στην παρούσα διπλωματική εργασία, εστιάζουμε στη βελτίωση της φάσης συσταδοποίησης, προκειμένου να επιτύχουμε χαμηλότερο παράγοντα αναπαραγωγής σε σύγκριση με την αρχική προσέγγιση. Η ελαχιστοποίηση του παράγοντα αναπαραγωγής στην διαμέριση γράφων συμβάλλει στη βελτιστοποίηση της χρήσης του αποθηκευτικού χώρου, στην ενίσχυση της εξισορρόπησης φορτίου, στη μείωση της επιβάρυνσης επικοινωνίας και στην απλοποίηση του ελέγχου συνέπειας και ταυτόχρονης λειτουργίας, οδηγώντας σε πιο αποδοτικά κατανεμημένα συστήματα επεξεργασίας γράφων. Εστιάζουμε επίσης στα ποιοτικά χαρακτηριστικά της προσέγγισής μας: ανεξαρτησία σειράς ροής ακμών και απαίτηση για ένα μόνο πέρασμα. Ο αρχικός αλγόριθμος 2PS-L εξαρτάται σε μεγάλο βαθμό από τη σειρά της ροής των ακμών του γράφου και απαιτεί τουλάχιστον δύο περάσματα μέσω της ροής ακμών. Αντίθετα, η προσέγγισή μας είναι ανεξάρτητη από τη σειρά της ροής ακμών και απαιτεί μόνο ένα πέρασμα.","Edge partitioning is a crucial preprocessing step for optimizing distributed computing tasks on graphs. It involves dividing the graph into smaller sub-graphs to enable simultaneous computations and reduce time and cost overhead. The objective of edge partitioning is to split the given graph into a given number of partitions while minimizing vertex replication across partitions. This minimizes cross-partition queries and improves performance. Edge partitioning can be categorized as stateful or stateless. Stateful partitioning delivers better results but at a higher cost, whereas stateless partitioning is faster but yields lower quality outcomes. This study extends the 2PS-L partitioning algorithm, which operates on the stateful streaming model in linear runtime. 2PS-L consists of two phases: edge clustering and edge partitioning based on the clusters generated in the initial phase. In this thesis, we primarily focus on enhancing the clustering phase of graph partitioning in order to achieve a lower replication factor compared to the original approach. Minimizing the replication factor in graph partitioning helps optimize storage utilization, enhance load balancing, reduce communication overhead, and simplify consistency and concurrency control, leading to more efficient and scalable graph processing systems. We also focus on our approach quality characteristics: edge stream independence and single pass requirement. The original 2PS-L algorithm is heavily dependent on the order of the graph stream and requires at least two passes through the stream. In contrast, our approach is independent of the stream order and only requires a single stream pass."]},{"key":"dc:title","label":"Title","values":["Node Community Participation for Enhancing Stream-Based Edge Partitioning"]}]}],"canonical_facts":{"dc:creator":["Σταματίου Αθηνά","Stamatiou Athina"],"dc:date":["2023"],"dc:description":["Η διαμέριση ακμών είναι ένα κρίσιμο βήμα προεπεξεργασίας για τη βελτιστοποίηση κατανεμημένων υπολογιστικών εργασιών σε γράφους. Περιλαμβάνει τη διαχωρισμό του γράφου σε μικρότερους υπο-γράφους, ώστε να είναι δυνατοί οι ταυτόχρονοι υπολογισμοί και να μειωθεί η επιβάρυνση σε χρόνο και κόστος. Ο στόχος της διαμέρισης ακμών είναι να χωριστεί ο δεδομένος γράφος σε έναν δεδομένο αριθμό διαμερίσεων, ελαχιστοποιώντας παράλληλα την αναπαραγωγή κορυφών μεταξύ τους. Με τον τρόπο αυτό ελαχιστοποιούνται τα ερωτήματα που ανταλλάσσονται μεταξύ των διαμερίσεων και βελτιώνονται οι επιδόσεις. Η διαμέριση ακμών μπορεί να κατηγοριοποιηθεί ως stateful ή stateless. Η stateful προσέγγιση οδηγεί σε καλύτερα αποτελέσματα αλλά με υψηλότερο κόστος, ενώ η stateless προσέγγιση είναι ταχύτερη αλλά οδηγεί σε αποτελέσματα χαμηλότερης ποιότητας. Η παρούσα μελέτη επεκτείνει τον αλγόριθμο διαμέρισης 2PS-L, ο οποίος βασίζεται στο stateful μοντέλο ροής ακμών και έχει γραμμικό χρόνο εκτέλεσης. Ο αλγόριθμος 2PS-L αποτελείται από δύο φάσεις: ομαδοποίηση κορυφών και διαμέριση ακμών με βάση τις ομάδες που δημιουργούνται στην αρχική φάση. Στην παρούσα διπλωματική εργασία, εστιάζουμε στη βελτίωση της φάσης συσταδοποίησης, προκειμένου να επιτύχουμε χαμηλότερο παράγοντα αναπαραγωγής σε σύγκριση με την αρχική προσέγγιση. Η ελαχιστοποίηση του παράγοντα αναπαραγωγής στην διαμέριση γράφων συμβάλλει στη βελτιστοποίηση της χρήσης του αποθηκευτικού χώρου, στην ενίσχυση της εξισορρόπησης φορτίου, στη μείωση της επιβάρυνσης επικοινωνίας και στην απλοποίηση του ελέγχου συνέπειας και ταυτόχρονης λειτουργίας, οδηγώντας σε πιο αποδοτικά κατανεμημένα συστήματα επεξεργασίας γράφων. Εστιάζουμε επίσης στα ποιοτικά χαρακτηριστικά της προσέγγισής μας: ανεξαρτησία σειράς ροής ακμών και απαίτηση για ένα μόνο πέρασμα. Ο αρχικός αλγόριθμος 2PS-L εξαρτάται σε μεγάλο βαθμό από τη σειρά της ροής των ακμών του γράφου και απαιτεί τουλάχιστον δύο περάσματα μέσω της ροής ακμών. Αντίθετα, η προσέγγισή μας είναι ανεξάρτητη από τη σειρά της ροής ακμών και απαιτεί μόνο ένα πέρασμα.","Edge partitioning is a crucial preprocessing step for optimizing distributed computing tasks on graphs. It involves dividing the graph into smaller sub-graphs to enable simultaneous computations and reduce time and cost overhead. The objective of edge partitioning is to split the given graph into a given number of partitions while minimizing vertex replication across partitions. This minimizes cross-partition queries and improves performance. Edge partitioning can be categorized as stateful or stateless. Stateful partitioning delivers better results but at a higher cost, whereas stateless partitioning is faster but yields lower quality outcomes. This study extends the 2PS-L partitioning algorithm, which operates on the stateful streaming model in linear runtime. 2PS-L consists of two phases: edge clustering and edge partitioning based on the clusters generated in the initial phase. In this thesis, we primarily focus on enhancing the clustering phase of graph partitioning in order to achieve a lower replication factor compared to the original approach. Minimizing the replication factor in graph partitioning helps optimize storage utilization, enhance load balancing, reduce communication overhead, and simplify consistency and concurrency control, leading to more efficient and scalable graph processing systems. We also focus on our approach quality characteristics: edge stream independence and single pass requirement. The original 2PS-L algorithm is heavily dependent on the order of the graph stream and requires at least two passes through the stream. In contrast, our approach is independent of the stream order and only requires a single stream pass."],"dc:identifier":["uoadl:3336118","https://pergamos.lib.uoa.gr/uoa/dl/object/3336118"],"dc:language":["English"],"dc:subject":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"dc:title":["Node Community Participation for Enhancing Stream-Based Edge Partitioning"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T06:22:53Z"}