Diploma Thesis DIP-2359

BibliographyPfahl, Timo: Entwicklung von Verfahren zur Cluster-Bildung in einem Informationsgraphen für die Vorabübertragung von Webseiten..
University of Stuttgart : Collaborative Research Center SFB 627 (Nexus: World Models for Mobile Context-Based Systems), Diploma Thesis No. 2359 (2005).
107 pages, german.
CR-SchemaH.3.3 (Information Search and Retrieval)
E.1 (Data Structures)
F.2.2 (Nonnumerical Algorithms and Problems)
KeywordsHoarding; Cluster; Vorabübertragung
Abstract

Aus unserem täglichen Leben sind mobile Endgeräte wie Mobiltelefone oder PDAs nicht mehr wegzudenken. Durch die zunehmende Verbreitung von Funknetzen ist der mobile Zugriff auf das Internet mit solchen Geräten an immer mehr Orten möglich. Von einer flächendeckenden Versorgung ist man jedoch noch weit entfernt. Eine Möglichkeit, dem Benutzer auch in Zeiten ohne Netzanbindung den Zugriff auf Inhalte des Internets bieten zu können, besteht darin, Webseiten in Phasen guter Netzanbindung vorab auf das Endgerät zu übertragen. Die Herausforderung dieser Vorgehensweise, im englischen Hoarding genannt, liegt darin, eine gute Vorhersage über zu erwartendes Benutzerverhalten zu treffen. Hierzu wird das vergangene Benutzerverhalten beobachtet und ausgewertet. Auf Basis dieser Auswertung erfolgt dann eine Vorhersage über das zukünftig erwartete Verhalten.

Im Rahmen dieser Arbeit wird ein solches Verfahren zur Vorhersage zukünftigen Zugriffsverhaltens auf Webseiten erarbeitet. In einem existierenden Verfahren wird das vergangene Zugriffsverhalten verschiedener Benutzer in einer Graphstruktur repräsentiert. Die Auswahl der Webseiten erfolgt dann durch eine Traversierung des Graphen nach dem Tiefen- oder Breitensuchprinzip. In dieser Arbeit wird ein Verfahren erstellt, das durch Clusterbildung jene Webseiten in diesem Graphen zu Informationseinheiten zusammenfasst, zwischen denen eine semantische Beziehung besteht. Das bedeutet, dass wenn eine Webseite eines Clusters aufgerufen wird, es sehr wahrscheinlich ist, dass auch auf die anderen enthaltenen Seiten zugegriffen wird. Um den Speicherplatz der Endgeräte effizienter zu nutzen, werden Cluster dann entweder komplett oder gar nicht vorab übertragen. Dadurch wird erwartet, dass eine bessere Auswahl der vorab zu übertragenden Webseiten getroffen wird.

Die Idee hinter der Clusterbildung basiert darauf, dass Benutzer beim Durchsuchen des Internets häufig eine Folge von Webseiten aufrufen, bis die gesuchte Information gefunden wurde. Dies ermöglicht eine Unterteilung der Seiten in so genannte Navigations- und Inhaltsseiten. Auf Basis dieser Unterteilung werden dann im Graphen Pfade von Webseiten gesucht, die eine solche Suche repräsentieren. Die einzelnen Seiten eines solchen so genannten Suchpfades werden dann zu einem Cluster zusammengefasst.

Es wird gezeigt, dass durch die Clusterbildung und -bewertung eine sehr viel bessere Vorhersage über zukünftiges Benutzerverhalten getroffen werden kann. Auf Basis von Bewertungsmetriken, die zur Ermittlung der Zufriedenheit der Benutzer dienen, werden bis zu dreimal bessere Ergebnisse erzielt als für das existierende Tiefen- und Breitensuchverfahren.

Full text and
other links
PDF (1768295 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Project(s)SFB-627, A2 (University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems)
Entry dateFebruary 17, 2006
   Publ. Computer Science