Διαχείριση γραφημάτων μεγάλης κλίμακας για δεδομένα του παγκόσμιου ιστού

Abstract

The Web is a complicated and evolving human creation. Its distributed and self-organizing nature trigger the scientific interest of the last decades in studying its evolution and structure, posing new challenges in terms of performance. The Web, from the users’ perspective, is an everyday issue and it is a vital resource of information, entertainment, social networking, and enterprise. The ever-growing tendency of the Web along with the new resource-hungry web-applications, challenge the existing infrastructure. The need for a supporting infrastructure is overcome by the Content Distribution Networks (CDNs), as a short-term solution. CDNs, via geographically distributed points of presence, bring content closer to the end users thus minimizing latency and improving response times. Therefore, the primary objective will be the development of content management methodologies that further improve the existing content delivery scheme. In finding an appropriate representation of the Web to accomplish the objectιωε, the graph representation appears to be appropriate. Treating the web-pages as graph-nodes and the hyperlinks as graph-edges new graph management problems are defined, focused on the context of the Web and content delivery. This thesis proposes algorithmic solutions to the following graph management problems: - Nodes placement in a CDN in a way that the overall content transfer speed is optimized. The notion of communication cost is defined and several heuristic algorithms are suggested. - Communities detection. A community is a coherent subgraph that acts as an attractor for the users, who navigate inside the community with higher probability. In this context several algorithms are proposed that detect such communities eventually improving the overall performance in a CDN. - Large scale graph projection. The problem to solve is to appropriately represent the nodes as point clouds inside a $2-3$ dimensional Euclidean space where the communities appear as dense areas. To tackle this problem a high performance algorithm is proposed that is able to project graphs containing millions of nodes in almost linear time. Finally, in the context of experimentation a new simulation environment for CDNs is proposed that fills the gap in the literature.

Ο Παγκόσμιος Ιστός (Π.Ι.) αποτελεί ένα περίπλοκο συνεχώς εξελίξιμο ανθρώπινο κατασκεύασμα. Η κατανεμημένη φύση και η δομική αυτο-οργάνωση του προκαλούν το επιστημονικό ενδιαφέρον των τελευταίων δεκαετιών για μελέτη της εξέλιξης και της δομής του, θέτοντας νέες προκλήσεις σε ζητήματα απόδοσης. Ο Π.Ι., από την πλευρά των χρηστών, έχει περάσει πλέον στην καθημερινότητα και αποτελεί ζωτικής σημασίας πηγή πληροφόρησης, διασκέδασης, κοινωνικής δικτύωσης και επιχειρηματικότητας. Η αυξητική τάση του Π.Ι. σε συνδυασμό με τις νέες διαδικτυακές εφαρμογές, οι οποίες έχουν αυξημένες απαιτήσεις σε διαχείριση όγκου πληροφορίας, προκαλούν συνεχώς την υπάρχουσα υποδομή δικτύωσης. Η ανάγκη για καλύτερη υλικοτεχνική υποδομή καλύπτεται βραχυπρόθεσμα από τα Δίκτυα Παράδοσης Περιεχομένου (Δ.Π.Π.), τα οποία με κατανεμημένο τρόπο διαμοιράζουν περιεχόμενο στον Π.Ι. Συνεπώς, πρωταρχικός στόχος είναι εκμεταλλευόμενοι την υπάρχουσα υποδομή να βελτιωθεί η ποιότητα των υπηρεσιών του Π.Ι. σε επίπεδο μεταφοράς δεδομένων προς τους τελικούς χρήστες. Η φυσική δομή του Π.Ι. μπορεί να εκφραστεί κατάλληλα με την μορφή ενός γραφήματος όπου οι κόμβοι αποτελούν τις ιστοσελίδες και οι ακμές τους υπερσυνδέσμους. Η αναπαράσταση με γράφημα επιτρέπει τον ορισμό προβλημάτων διαχείρισης τα οποία έχουν πάντα ως πρόκληση την μεγάλη κλίμακα του Π.Ι. Στο πλαίσιο αυτό η διδακτορική διατριβή παρέχει αλγοριθμικές λύσεις στα ακόλουθα προβλήματα διαχείρισης γραφημάτων: - Τοποθέτηση των κόμβων του γραφήματος σε ένα Δ.Π.Π. με τρόπο ώστε η ταχύτητα μεταφοράς του περιεχομένου προς τους χρήστες να γίνεται με αποδοτικό τρόπο. Ορίζεται η έννοια του κόστους μεταφοράς και προτείνονται αλγόριθμοι οι οποίοι επιλύουν το πρόβλημα τοποθέτησης (NP-Hard) με ευριστικό τρόπο. - Εντοπισμός κοινοτήτων στο γράφημα. Ως κοινότητα θεωρείται ένα συνεκτικό υπογράφημα το οποίο δρα ως ατράκτορας για τους χρήστες οι οποίοι πλοηγούνται με μεγαλύτερη πιθανότητα μέσα στην κοινότητα. Παρέχεται ένας καινούριος ορισμός της κοινότητας και προτείνονται νέοι αλγόριθμοι για τον εντοπισμό τους. Η τελική επαλήθευση γίνεται με γνώμονα την επιτάχυνση της μεταφοράς του περιεχομένου στους τελικούς χρήστες. - Προβολή γραφήματος μεγάλης κλίμακας. Το πρόβλημα προς επίλυση είναι η αναπαράσταση του γραφήματος στον Ευκλείδειο χώρο $2-3$ διαστάσεων όπου οι κοινότητες είναι προφανείς πυκνότητες. Για τον σκοπό αυτό προτείνεται μια νέα μέθοδος η οποία επιτυγχάνει τον σκοπό αυτό για γραφήματα της τάξης των εκατομμυρίων κόμβων με σχεδόν γραμμική πολυπλοκότητα. Τέλος, στα πλαίσια της πειραματικής διαδικασίας προτείνεται ένα περιβάλλον προσομοίωσης ενός Δ.Π.Π. το οποίο καλύπτει το υπάρχον κενό στον τομέα αυτό.