Συντάχθηκε 02-07-2014 15:21
από Vasiliki Grigoraki
Email συντάκτη: vgrigoraki<στο>tuc.gr
Ενημερώθηκε:
-
Κύρια: υπάλληλος ΗΜΜΥ.
Άλλες ιδιότητες: Unknown -#-@ΗΜΜΥ
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Μεταπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΜΕΤΑΠΤΥΧΙΑΚΗΣ ΕΡΓΑΣΙΑΣ
Ιωακείμ Πέρρου
με θέμα
Τυχαιοκρατική διατήρηση της κατάταξης PageRank σε πλήρως κατανεμημένες αρχιτεκτονικές
Stochastic PageRank maintenance over shared-nothing architectures
Παρασκευή 4 Ιουλίου, 1:30μμ
Αίθουσα Συνεδριάσεων ΗΜΜΥ, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Καθηγητής Μίνως Γαροφαλάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Αντώνιος Δεληγιαννάκης
Αναπληρωτής Καθηγητής Μιχαήλ Λαγουδάκης
Περίληψη
Η κατάταξη PageRank έχει καθιερωθεί ως ένας από τους πιο σημαντικούς αλγορίθμους κατάταξης ιστοσελίδων. Για να συμβαδίσει με το συνεχώς αυξανόμενο μέγεθος του παγκόσμιου ιστού και την υψηλή συχνότητα ενημερώσεων, πρόσφατη έρευνα στοχεύει στην παραλληλοποίηση αλγορίθμων υπολογισμού της κατάταξης PageRank, όπως και στην συνεχή διατήρηση της κατάταξης PageRank σε ενημερώσεις πραγματικού χρόνου. Παρόλα αυτά, καμία εργασία ως τώρα δεν έχει στοχεύσει στην διατήρηση της κατάταξης PageRank πάνω από πλήρως κατανεμημένες αρχιτεκτονικές, όπως τα μεγάλης κλίμακας νέφη υπολογιστών που είναι διαθέσιμα στο Internet. Η συγκεκριμένη εργασία γεφυρώνει αυτό το χάσμα, προτείνοντας τον πρώτο αποδοτικό τυχαιοκρατικό αλγόριθμο για την διατήρηση της κατάταξης PageRank πάνω από πλήρως κατανεμημένες αρχιτεκτονικές. Ο αλγόριθμος ελαχιστοποιεί αποδοτικά τα δεδομένα που διατηρεί ο κάθε κόμβος του συστήματος, δίνοντας την δυνατότητα για επίτευξη χαμηλού ίχνους επικοινωνίας και μνήμης. Η ορθότητα του αλγορίθμου θεμελιώνεται θεωρητικά. Μία εκτεταμένη πειραματική αξιολόγηση με πραγματικά δεδομένα από τον παγκόσμιο ιστό και από κοινωνικά δίκτυα δείχνει την απόδοση και την ακρίβεια της προτεινόμενης προσέγγισης, καθώς και την υπεροχή της απέναντι στις εναλλακτικές.
Abstract
PageRank is established as one of the leading ranking algorithms in the web. To keep up with the increasing size of the web graph and the high frequency of updates, recent research has focused on parallelizing PageRank algorithms as well as the continuous maintenance of PageRank scores over streaming updates. However, no work up to now has considered PageRank maintenance over distributed shared-nothing architectures, such as the large-scale clouds available in the Internet today. This work bridges this gap by proposing the first known efficient stochastic algorithm for PageRank maintenance over distributed shared-nothing architectures. The algorithm effectively minimizes the amount of state per system node, enabling a small communication and memory footprint. The algorithm’s correctness is theoretically established. An extensive experimental evaluation with real web and social network data shows the efficiency and accuracy of the proposed approach, and its superiority compared to the state-of-the-art competitors.
