Aristotle University Of Thessaloniki (AUTH)
Διαχείριση γραφημάτων μεγάλης κλίμακας για δεδομένα του παγκόσμιου ιστού
Abstract
dc:descriptionThe 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.
Degree
thesis:*- Grantor dc:publisher
- Aristotle University Of Thessaloniki (AUTH)
- Year dc:date
- 2010
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Stamos, Konstantinos
- Στάμος, Κωνσταντίνος
Subjects
dc:subject × 12Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/20878