Abstract
dc:descriptionΣύγχρονα συστήματα επεξεργασίας δεδομένων που δίνουν δυνατότητες αλληλεπίδρασης και μοντελοποιούν συσχετισμούς μεταξύ χρηστών παίζουν αποφασιστικό ρόλο στη σημερινή εποχή. Τροφοδοτούν καθημερινές ανθρώπινες δραστηριότητες, βοηθούν στον καθορισμό της παγκόσμιας επικοινωνίας και συμβάλλουν στη δημιουργία και διαχείριση δικτύων κοινοτήτων. Τέτοια δίκτυα αναπαρίστανται κατά κύριο λόγο με τη χρήση γράφων, τα μεγέθη των οποίων έχουν παρουσιάσει εκθετικές αυξήσεις κατά τη διάρκεια της περασμένης δεκαετίας. Τα μεγέθη αυτά εμποδίζουν την έγκαιρη ανάλυση τέτοιων δικτύων λόγω περιορισμών σε μνήμη αλλά και ιδιαίτερων απαιτήσεων I/O. Με τη χρήση τεχνικών συμπίεσης γράφων έχει επιτευχθεί μείωση της απαιτούμενης μνήμης για την αναπαράσταση τέτοιων δικτύων χρησιμοποιώντας μερικά bitsανάακμή. Αντίστοιχες προσεγγίσεις προσφέρουν σύντομες και περιεκτικές απεικονίσεις για κοινωνικά, βιολογικά και πληροφοριακά δίκτυα, ενώ ταυτόχρονα επιτρέπουν αποδοτική πρόσβαση σε συγκεκριμένα στοιχεία του γράφου προς αναζήτηση. Παρά την επιτυχία τους, τέτοιες μέθοδοι επικεντρώνουν την προσοχή τους κυρίως σε στατικούς γράφους και προσφέρουν πρόσβαση μονάχα σε ένα στιγμιότυπο ή σε συγκεντρωτικά χαρακτηριστικά ενός δικτύου. Στην πραγματικότητα όμως, τα δίκτυα εξελίσσονται διαρκώς με την πάροδο του χρόνου και σε πολλές περιπτώσεις είναι αναγκαία η αποτύπωση αυτής της εξέλιξης. Σε αυτή τη διπλωματική εργασία προτείνουμε ένα framework για τη συμπίεση τέτοιων χρονικά εξελισσόμενων γράφων, το οποίο βασίζεται σε μια δυϊκή αναπαράσταση στην οποία εμπεριέχονται η δομή του δικτύου, καθώς και η συναφής χρονική πληροφορία. Αν και εκμεταλλευόμαστε αρκετές δομικές ιδιότητες δικτύων που συναντώνται στην πραγματικότητα, εισάγουμε και εκμεταλλευόμαστε επίσης εμπειρικά παρατηρημένες ιδιότητες σχετικά με τη χρονική τους διάσταση. Η ανάλυση και η πειραματική αξιολόγηση που διεξάγουμε δείχνουν ότι το προτεινόμενο framework αποδίδει πολύ καλύτερα από άλλες γνωστές τεχνικές ίδιου σκοπού, ενώ ταυτόχρονα επιτυγχάνει σημαντικές βελτιώσεις στις αναλογίες συμπίεσης οι οποίες σε μερικές περιπτώσεις πέφτουν κάτω από το μισό άλλων προσεγγίσεων τελευταίας τεχνολογίας. Ταυτόχρονα, η αποδοτική ως προς τη μνήμη αναπαράσταση που προτείνεται, καταφέρνει πάνω από 60% πιο γρήγορη συμπίεση γράφων καθώς και πολλαπλών τάξεων μεγέθους γρηγορότερες επερωτήσεις πάνω στα στοιχεία των αντίστοιχων γράφων, ειδικά για δίκτυα μεγάλης κλίμακας. Εν τέλει, το framework που προτείνεται είναι η πρώτη εις γνώσιν μας προσπάθεια συμπίεσης χρονικά εξελισσόμενων γράφων που χρησιμοποιεί πραγματικό χρόνο αντί για αριθμημένα χρονικά βήματα. Αυτό βοηθάει στον ορισμό της χρονικής λεπτομέρειας και έχει ως αποτέλεσμα τον καλύτερο έλεγχο του μεγέθους της αναπαράστασης επιτυγχάνοντας ακόμα περισσότερο κέρδος σε μνήμη.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Στέφου Θεόδωρος
- Stefou Theodoros
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, English, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:2935329