Der Webcrawl

Ausgangspunkt der Untersuchungen ist ein Webcrawl der Suchmaschine ``Speedfind''. Die gelieferten Daten bestehen aus einer Liste von $N=20,5\cdot 10^6$ Seiten-URLs und insgesamt $N_L=92 \cdot 10^6$ Link-URLs von Verweisen zwischen diesen Seiten. In Tabelle 3.3 ist exemplarisch ein Ausschnitt der Daten dargestellt.

Tabelle: Datenformat der Linkstruktur: ``p'' stellt eine Seiten-URL dar, ``c'' eine Verweis-URL auf der Seite, die mit ``p'' eingeleitet wurde.

c: http://www.ebgymhollabrunn.ac.at/feier/lehrerkoll.html

c: http://www.ebgymhollabrunn.ac.at/feier/22lehrer.html

p: http://www4.informatik.tu-muenchen.de/papers/GSB98-FTRTFT.html

p: http://www.frey-bautenschutz.de/arbeiten.htm

c: http://www.colfirmit.de/index.html

c: http://www.deitermann.de/index.html

c: http://www.frey-bautenschutz.de/index.htm . .

Insgesammt umfaßt dies eine Datenmenge von einigen Gigabyte. Der Umgang mit dieser Datenmenge ist sehr ressourcenintensiv, daher ist zunächst eine Umwandlung nötig, um den Speicherbedarf zu reduzieren.

Dazu wird jeder Seiten-URL eine eindeutige Nummer zugeordnet und die URLs aller Verweise auf diese Seiten werden durch diese Nummer ersetzt. Das Problem bei dieser Ersetzung ist die Notwendigkeit schnell prüfen zu können, ob eine und welche Nummer einer URL zugeordnet ist bzw. bereits vergeben ist. Bei der Verwendung eines einfachen Array würde eine einzelne Prüfung bei der hier betrachteten Datenmenge im Schnitt $N/2=10^7$ Vergleiche von Zeichenketten benötigen und die Ersetzung insgesamt ca. $N_L N /2=920 \cdot 10^6$. Diese Vergleiche sind relativ zeitaufwendig und würden extrem lange Programmlaufzeiten bedeuten. Daher werden assoziative Arrays (Hashes) für diese Ersetzung benutzt. In einem Hash werden einzelne Felder nicht, wie bei einfachen Arrays, über einen numerischen Index adressiert, sondern über eine Zeichenkette (Schlüssel). Ein besonderes Verfahren dieser Hashes erlaubt eine extrem schnelle Verarbeitung der Zugriffe. Wird die URL einer Seite als Schlüssel verwendet und das zugehörige Feld mit der zugeordneten Nummer versehen, reduziert sich die Programmlaufzeit um Größenordnungen. Allerdings besteht bei Hashes die Gefahr von Kollisionen, d.h. daß zwei verschiedene Schlüssel als identisch interpretiert werden. In diesem Fall würden zwei verschiedene Webseiten nach der Ersetzung als identisch gelten. Ein Vergleich zwischen der Anzahl verschiedener URLs in den ursprünglichen Daten und der Anzahl verschiedener Nummern nach der Ersetzung zeigte, daß es keinerlei Kollisionen gab.

Insgesamt ergibt diese Umwandlung ein Netzwerk, bestehend aus einer Liste von Verbindungen. Jede Verbindung wird durch einen numerischen Index des Quell- und Zielknoten beschrieben.