Distributed and Streaming Graph Processing Techniques

Διδακτορική Διατριβή uoadl:2810763 220 Αναγνώσεις

Μονάδα:
Τμήμα Πληροφορικής & Τηλεπικοινωνιών
Πληροφορική
Ημερομηνία κατάθεσης:
2018-10-17
Έτος εκπόνησης:
2018
Συγγραφέας:
Λιάκος Παναγιώτης
Στοιχεία επταμελούς επιτροπής:
Αλέξιος Δελής, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Μέμα Ρουσσοπούλου, Αναπληρώτρια Καθηγήτρια, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Αλέξανδρος Ντούλας, Επίκουρος Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Δημήτρης Γουνόπουλος, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Γιάννης Ιωαννίδης, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Αντώνιος Δεληγιαννάκης, Αναπληρωτής Καθηγητής, Σχολή Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης
Γιάννης Κοτίδης, Αναπληρωτής Καθηγητής, Τμήμα Πληροφορικής, Οικονομικό Πανεπιστήμιο Αθηνών
Πρωτότυπος Τίτλος:
Distributed and Streaming Graph Processing Techniques
Γλώσσες διατριβής:
Αγγλικά
Μεταφρασμένος τίτλος:
Τεχνικές Επεξεργασίας Κατανεμημένων Γράφων και Ρευμάτων Γράφων
Περίληψη:
Κάτω από τα περισσότερα σύνθετα συστήματα που διαδραματίζουν έναν κομβικό ρόλο στην καθημερινή μας ζωή κρύβονται περίπλοκα δίκτυα. Τέτοια δίκτυα πραγματικού κόσμου μοντελοποιούνται συχνά με τη χρήση γράφων. Ο μεγάλος όγκος των γράφων που παράγονται στο σημερινό διασυνδεδεμένο κόσμο επιτρέπει την πραγματοποίηση πολυάριθμων συναρπαστικών εφαρμογών αλλά και εγείρει σημαντικές προκλήσεις. Αναλογιστείτε για παράδειγμα το γράφο φιλίας ενός ιστοχώρου κοινωνικής δικτύωσης και τα ευρήματα στα οποία μπορούμε να φτάσουμε αν εκτελέσουμε αλγορίθμους δικτύων, όπως η ανίχνευση κοινοτήτων, στο γράφο αυτό. Εντούτοις, ο όγκος τον οποίο αγγίζουν τα δίκτυα πραγματικού κόσμου συχνά καθιστούν την εκτέλεση ακόμη και θεμελιωδών αλγορίθμων γράφων αδύνατη όταν ακολουθούνται παραδοσιακές προσεγγίσεις.
Στην παρούσα διατριβή εστιάζουμε σε δύο κατευθύνσεις που επιτρέπουν τον χειρισμό δικτύων μεγάλης κλίμακας και συγκεκριμένα την κατανεμημένη επεξεργασία γράφων και τους αλγορίθμους ρευμάτων γράφων. Σε αυτό το πλαίσιο αρχικά συνεισφέρουμε όσον αφορά στη χρήση μνήμης των κατανεμημένων συστημάτων επεξεργασίας γράφων, επεκτείνοντας τις υπάρχουσες δομές ενός τέτοιου σύγχρονου συστήματος με συμπαγείς αναπαραστάσεις. Έπειτα, επικεντρωνόμαστε στο πρόβλημα της ανίχνευσης κοινοτήτων και προτείνουμε α) έναν τοπικό αλγόριθμο που αποκαλύπτει τη δομή κοινοτήτων γύρω από έναν κόμβο κι ο οποίος δύναται εύκολα να εκτελεστεί σε κατανεμημένο περιβάλλον και β) έναν αλγόριθμο ρευμάτων γράφων ο οποίος υπερκερά σημαντικά προσεγγίσεις τεχνολογίας αιχμής που χρησιμοποιούν ολόκληρο το γράφο, τόσο σε χρόνο εκτέλεσης όσο και σε χρήση μνήμης. Επιπρόσθετα, προτείνουμε μια τεχνική δειγματοληψίας που επιτρέπει την ανάκτηση του ενδιαφέροντος κομματιού ενός ρεύματος κοινωνικής δραστηριότητας που η εξ ολοκλήρου διαχείρισή του είναι αδύνατη εξαιτίας του όγκου του. Τέλος, εκμεταλλευόμαστε τα διαθέσιμα δεδομένα ενός δημοφιλούς ιστοχώρου κοινωνικής δικτύωσης ώστε να αξιολογήσουμε εμπειρικά ένα ευρέως διαδεδομένο μοντέλο διαμόρφωσης γνώμης, χρησιμοποιώντας έναν κατανεμημένο αλγόριθμο.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
Κατανεμημένη επεξεργασία γράφων, ρεύματα γράφων, συμπίεση γράφων, ανίχνευση κοινοτήτων, διαμόρφωση γνώμης
Ευρετήριο:
Ναι
Αρ. σελίδων ευρετηρίου:
7
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
136
Αριθμός σελίδων:
151