Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-66068
URL: http://www.freidok.uni-freiburg.de/volltexte/6606/


Jacobs, Tobias

Hotlink Assignment

Hotlink Assignment

Dokument1.pdf (899 KB) (md5sum: 7a596d60d67f6b5d8dd29d56192f7a10)

Kurzfassung in Deutsch

Die vorliegende Dissertation behandelt kombinatorische Optimierungsprobleme, die mit dem Erweitern von Websites durch zusätzliche Hyperlinks zusammenhängen.

Das Einfügen ggf. speziell hervorgehobener zusätzlicher Links, so genannter Hotlinks, ist ein Verfahren zur Optimierung von Websites. Ein Vorteil dieses Verfahrens ist, dass es nicht destruktiv ist, da die ursprüngliche Struktur der Site erhalten bleibt. Hotlinks können - abhängig von den Interessen der Benutzer - so zugeordnet werden, dass auf beliebtere Seiten schneller zugegriffen werden kann. Auf diese Weise wird die erwartete Anzahl an ,,Klicks minimiert und der Datenverkehr gleichzeitig verringert.

Eine hierarchisch aufgebaute Website kann formal als gewichteter Baum T = (V,E,omega) beschrieben werden, wobei (V,E) ein Baum mit Wurzel r ist.
Die Gewichtsfunktion omega ordnet jedem Knoten eine Zugriffswahrscheinlichkeit zu. Ein Hotlink Assignment ist eine Menge A von zusätzlichen Kanten, welche für die Benutzer Abkürzungen darstellen. Aus Gründen der Übersichtlichkeit ist nur eine gewisse Anzahl ausgehender Hotlinks pro Seite erlaubt. Ein Hotlink Assignment ist für einen gegebenen gewichteten Baum optimal, wenn es unter allen zulässigen Assignments die erwartete Länge des Pfades von der Wurzel r zu einem Knoten im Baum minimiert. Hierbei betrachten wir nicht den kürzesten Pfad, sondern gehen davon aus, dass jeder Hotlink auf dem Weg von der Wurzel zum Zielknoten durch die Benutzerin oder den Benutzer unmittelbar benutzt wird.

Nach einer ausführlichen Einführung in die Problemstellung befassen wir uns zunächst mit der Berechnungskomplexität der optimalen Lösung. Hierbei zeigen wir, dass es NP-vollständig ist, zu entscheiden, ob für einen gegebenen Baum ein Hotlink Assignment existiert, welches eine bestimmte erwartete Pfadlänge erreicht. Dies gilt selbst für den Fall, dass maximal ein Hotlink von jedem Knoten ausgehen darf und dass nur die Blätter positive Zugriffswahrscheinlichkeit haben.

Im darauffolgenden Kapitel identifizieren wir eine praxisrelevante Einschränkung des Lösungsraumes, unter deren Berücksichtigung das Hotlink-Assignment-Problem in Polynomialzeit gelöst werden kann. Es handelt sich hierbei um die Anforderung, dass Hotlinks nur auf die Blätter des Baumes weisen dürfen.

Im weiteren Verlauf der Dissertation geben wir Algorithmen an, die in Polynomialzeit Näherungslösungen mit konstanten
Approximationsfaktoren berechnen. Der Greedy-Algorithmus fügt immer den Hotlink in den Baum ein, welcher momentan die größte Verbesserung erzielt. Wir zeigen, dass mit diesem Verfahren mindestens die Hälfte der maximal möglichen Verbesserung erreicht wird.
Des Weiteren geben wir ein Approximationsschema (PTAS) an, welches Lösungen mit beliebigem Näherungsgrad in Polynomialzeit berechnet, wobei der Grad des Polynoms vom gewünschten Näherungsgrad abhängt. Letzterer bezieht sich auch hier auf die maximal mögliche Verbesserung.
Eine alternative Zielsetzung ist es, die erwartete Pfadlänge möglichst gut zu approximieren. Hierfür präsentieren wir einen Polynomialzeitalgorithmus mit Approximationsfaktor 2.

Im letzten Kapitel der Dissertation präsentieren wir die Ergebnisse einer ausführlichen experimentellen Studie. Des weiteren geben wir eine neuartige heuristische Methode zum Einfügen von Hotlinks an, die in der Praxis exzellente Ergebnisse erzielt. Die Experimente basieren auf zwei Testdatensätzen. Der erste Datensatz besteht aus Baum-Instanzen, welche die Struktur der Websites großer Universitäten repräsentieren. Der zweite Datensatz beinhaltet synthetische Instanzen, die von einem probabilistisch arbeitenden Algorithmus erzeugt wurden. Letzterer wurde bei dieser Studie erstmals eingesetzt. Die Experimente zeigen, dass die heuristische Methode und der Greedy-Algorithmus in der Praxis die besten Lösungen berechnen und dass bei Einschränkung des Lösungsraumes auf Blätter durchaus vergleichbar gute Ergebnisse erzielt werden. Auf der anderen Seite schneiden Algorithmen, die auf Approximationsfaktoren bezüglich der erwarteten Pfadlänge abzielen, in den Experimenten deutlich schlechter ab.


Kurzfassung in Englisch

This thesis treats combinatorial optimization problems that arise from the task to enhance web sites with additional hyperlinks.

The goal of inserting additional hyperlinks called hotlinks is to optimize web sites. An advantage of this approach is that it is non-destructive, i.e. the original site structure is preserved. Hotlinks are typically assigned according to the interests of the users, such that popular pages can be accessed especially fast. This both minimizes user interaction and reduces web traffic.

A hierarchically structured web site can be formalized as a weighted tree T=(V,E,omega), where (V,E) is a tree rooted at r. The weight function omega assigns an access probability to each node. A hotlink assignment is a set A of additional shortcut edges. For reasons of clearness, only a certain maximum number of hotlinks is allowed to leave each node. A hotlink assignment is optimal for T if it minimizes the expected length of the path from r to some other node. Instead of considering the shortest path, we assume that the user immediately takes any hotlink on the path to her or his destination node.

After a detailed introduction to the problem, we first address the computational complexity of the optimal solution. We show that it is NP-complete to decide whether there exists a hotlink assignment for a given weighted tree achieving a given expected path length. This even holds true in the case where only one hotlink is allowed to leave each node and only the leaves can have a positive access probability.

Subsequently, we identify a restriction of the solution space that is relevant in practice and allows for a polynomial time optimal algorithm. Namely, we study the model where hotlinks may only point to the leaves of the tree.

Returning our attention to the original hotlink assignment problem, we give a number of polynomial time algorithms that compute solutions guaranteeing constant approximation factors. The Greedy algorithm always inserts a hotlink currently achieving the greatest improvement or gain. We prove that this algorithm achieves at least one half of the optimal solution's total gain. Furthermore, we give an approximation scheme (PTAS) which computes solutions with an arbitrary approximation ratio in polynomial time, where the degree of the polynom depends on the desired ratio. Here the ratio also corresponds to the gain. An alternative approach is to approximate the expected path length as good as possible. To this end, we present a polynomial time 2-approximation.

In the last chapter of the thesis, we present the results of an extensive experimental study. Moreover, we propose a new heuristic that achieves excellent results in practice. Our experiments are based on two data sets. One set contains tree instances representing the structure of large university web sites. The other data set consists of synthetic instances generated by a new random construction method. The experiments show that in practice our heuristic method and Greedy achieve the best results, and, in terms of solution quality, assignments which are optimal under the restriction that hotlinks only point to leaves are comparable to the best assignments not meeting that restriction. On the other hand, algorithms tailored to approximate the expected path length perform considerably worse in the experiments.


SWD-Schlagwörter: Algorithmus , Greedy-Algorithmus , Optimierung , Kombinatorische Optimierung , Diskrete Optimierung , Dynamische Optimierung , Approximation , WebGrap
Freie Schlagwörter (deutsch): Approximationsschema , PTAS
Freie Schlagwörter (englisch): Approximation Scheme , PTAS
CCS Klassifikation G.2.2 - Gr , G.2.1 - Co , F.2.2 - Co
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Erstgutachter: Albers, Susanne (Prof. Dr.)
Sprache: Deutsch
Tag der mündlichen Prüfung: 08.05.2009
Erstellungsjahr: 2009
Publikationsdatum: 18.06.2009
Indexliste