Managing Massive Graphs for the Web and Web 2.0:
Creators: name: Γιάτσογλου, Μαρία Κωνσταντίνου
Publisher: name: Aristotle University of Thessaloniki
Year: 2010
Subjects: Διαχείριση γράφων
Βάσεις δεδομένων
Συστήματα κοινωνικής σήμανσης
Graph management
Databases
Social tagging systems

description: Το πρόβλημα της αποτελεσματικής διαχείρισης πολύ μεγάλων συνόλων δεδομένων έχει αποκτήσει ολοένα αυξανόμενο ενδιαφέρον λόγω της διαθεσιμότητας μιας πληθώρας δεδομένων από διάφορες πηγές, όπως ο Παγκόσμιος Ιστός. Μια από τις σημαντικότερες πηγές μεγάλου όγκου δεδομένων είναι οι εφαρμογές του Web 2.0, οι οποίες έχουν καταφέρει να προσελκύσουν το ενδιαφέρον ενός μεγάλου αριθμού χρηστών, πρόθυμων να συμβάλουν στη δημιουργία νέων δεδομένων στο διαδίκτυο. Πολλές Web 2.0 εφαρμογές ενσωματώνουν χαρακτηριστικά Κοινωνικής Σήμανσης (Social Tagging) επιτρέποντας στους χρήστες να χαρακτηρίζουν με ετικέτες (tags) της επιλογής τους διαδικτυακούς πόρους που έχουν δημιουργήσει είτε οι ίδιοι, είτε άλλοι χρήστες. Αυτή η δραστηριότητα παράγει καθημερινά τεράστιες ποσότητες δεδομένων, τα οποία μπορούν να αναπαρασταθούν με τη δομή ενός τριμερούς γράφου (tripartite graph) που συνδέει τους χρήστες, τους πόρους και τις ετικέτες. Η ανάλυση των Συστημάτων Κοινωνικής Σήμανσης - ΣΚΣ (Social Tagging Systems) αναδεικνύεται ως ένα ιδιαίτερα ενδιαφέρον πεδίο έρευνας, που επιτρέπει π.χ. την ανακάλυψη κοινών προτύπων στη συμπεριφορά των χρηστών, και την ανεύρεση κοινοτήτων σχετικών ετικετών, πόρων, ή χρηστών. Το τεράστιο μέγεθος των δεδομένων που προκύπτουν από ΣΚΣ υπαγορεύει την ανάγκη για μια ισχυρή υποδομή λογισμικού διαχείρισΗς. Το βασικό τεχνικό πρόβλημα είναι ο καταμερισμός του γράφου μεταξύ της μνήμης και του δίσκου του Η/Υ, καθώς λόγω του μεγάλου μεγέθους δεν είναι συνήθως δυνατή η πλήρης φόρτωση του γράφου στη μνήμη. Το αντικείμενο της παρούσας διπλωματικής εργασίας είναι η μελέτη του προβλήματος της αποτελεσματικής διαχείρισης πολύ μεγάλων γράφων. Πιο συγκεκριμένα, η παρούσα εργασία παρέχει μια εκτενή επισκόπηση και κατηγοριοποίηση των υφιστάμενων λύσεων στο πρόβλημα της αποθήκευσης και διαχείρισης μεγάλων συνόλων συσχετισμένων δεδομένων. Στα πλαίσια της επισκόπησης ιδιαίτερη έμφαση δίνεται στον τρόπο με τον οποίο επηρεάζει η χρήση της εκάστοτε υποδομής διαχείρισης δεδομένων τη λειτουργία των Web 2.0 εφαρμογών, καθώς και την απόδοση των αλγορίθμων εξόρυξης δεδομένων από τον Παγκόσμιο Ιστό. Θεωρώντας τα ΣΚΣ ως ειδική κατηγορία Web 2.0 εφαρμογών, στα δεδομένα των οποίων εφαρμόζονται ποικίλες μέθοδοι ανάλυσης, παρουσιάζονται οι σημαντικότερες σχετικές ερευνητικές εργασίες, και επιπλέον περιγράφονται οι απαιτήσεις που τίθενται στην υποδομή που θα υποστηρίζει αποδοτικά τη διαχείρισή τους. Με βάση τις προαναφερθείσες απαιτήσεις αναπτύχθηκαν τρία συστήματα διαχείρισης γράφων δεδομένων, τα οποία χρησιμοποιούν ως βασικές υποδομές: (i) τη σχεσιακή βάση δεδομένων H2, (ii) τη βιβλιοθήκη για δεικτοδότηση και αναζήτηση κειμένου Lucene, και (iii) τη βάση δεδομένων για γράφους Neo4j, αντίστοιχα. Για την αξιολόγηση και σύγκριση των υποδομών σχεδιάστηκε μια σειρά πειραμάτων που προσομοιώνουν λειτουργίες που πραγματοποιούνται σε γράφους από ΣΚΣ. Οι προδιαγραφές των πειραμάτων καθώς και τα αποτελέσματα τους για τα τρία συστήματα υποδομής παρουσιάζονται αναλυτικά και σχολιάζονται. Επιπλέον, παρουσιάζεται μια προσέγγιση στο πρόβλημα της διαχείρισης μεγάλων γράφων από ΣΚΣ με μια υποδομή που συμπιέζει τη δομή του γράφου ώστε να μπορεί να αποθηκευτεί στην κύρια μνήμη του Η/Υ. Για τον σκοπό αυτό περιγράφεται μια ενδεικτική αρχιτεκτονική που βασίζεται στη βιβλιοθήκη αλγορίθμων συμπίεσης WebGraph, και στη συνέχεια παρουσιάζονται κάποια πειραματικά αποτελέσματα που δείχνουν τα πλεονεκτήματά της. Οι ιδιαιτερότητες, τα προτερήματα και οι περιορισμοί της κάθε υλοποίησης σχολιάζονται διεξοδικά, ενώ προτείνονται επεκτάσεις των υπαρχόντων συστημάτων, καθώς και νέες ερευνητικές κατευθύνσεις για το ζήτημα της αποτελεσματικής διαχείρισης μεγάλων γράφων.
description: The problem of efficiently managing massive datasets has gained increasing attention due to the availability of a plethora of data from various sources, such as the Web. Moreover, Web 2.0 applications seem to be one of the most fruitful sources of information as they have attracted the interest of a large number of users that are eager to contribute to the creation of new data, available online. Several Web 2.0 applications incorporate Social Tagging features, allowing users to upload and tag sets of online resources. This activity produces massive amounts of data on a daily basis, which can be represented by a tripartite graph structure that connects users, resources and tags. The analysis of Social Tagging Systems (STS) emerges as a promising research field, enabling the identification of common patterns in the behavior of users, or the identification of communities of associated tags and resources, and much more. The massive size of STS datasets dictates the necessity for a robust underlying infrastructure to be used for their storage and access. This thesis contains a survey of existing solutions to the problem of storing and managing massive graph data focusing particularly on the implications of the underlying technologies of such frameworks on the support/operation of Web 2.0 applications that use them as back-end storage solutions, as well as on the efficient execution of web mining tasks. Considering the category of STS as an example of Web 2.0 applications, the requirements that are posed for the management of STS data are thoroughly discussed. On the basis of these requirements three frameworks have been developed, using state-of-the-art technologies as backbones. The results of benchmarks conducted on the developed frameworks are presented and discussed. Moreover, a compression-based framework that can be used for the support of graph analysis tasks is also presented, along with some benchmark results.