Inhalt:

Internet und World Wide Web bieten aufgrund ihrer riesigen Größe (aktuell ca. 681 Millionen Hosts und größenordnungsmäßig 1010 indizierte Web-Seiten, siehe z.B. www.isc.org bzw. www.worldwidewebsize.com), ihrer Dynamik und der extremen Verteilung von Ressourcen viele interessante algorithmische Herausforderungen. In dieser Vorlesung sollen exemplarisch einige der wesentlichen neuen Modelle und Techniken vorgestellt werden, die zur Lösung solcher Probleme entwickelt worden sind. Dabei wird der Schwerpunkt auf grundlegenden, allgemein einsetzbaren Ideen liegen.

Ausschnitt des Webgraphen

Geplante Themen im Einzelnen:

• Struktur des Webgraphen. Wir sehen uns Experimente an, die zeigen, dass der Webgraph (bestehend aus zu URLs korrespondierenden Knoten und Links als Kanten) nicht einfach nur ein "stark zusammenhängendes Spaghettiknäuel" ist, sondern große isolierbare Einzelkomponenten mit viel eingeschränkterer Verbindungsstruktur aufweist. Außerdem diskutieren wir mögliche formale Modelle, die die Webstruktur bez. wichtiger Graphparameter reproduzieren können.
• Suchmaschinen. Der heute erreichte Grad der Leistungsfähigkeit von Suchmaschinen wie Google erfordert natürlich viel firmeninternes Spezialwissen, aber die Arbeitsweise der grundlegenden Komponenten ist hinreichend gut in Veröffentlichungen dokumentiert (in der Anfangszeit der Suchmaschine auch von Google-Leuten). Von den vielen relevanten Themen werden wir Ranking-Algorithmen und Verfahren zur Entdeckung von Duplikaten ausführlicher behandeln.
• P2P-Netze. P2P-Netze dürften vor allem durch ihren illegalen Einsatz bei der massenhaften Vervielfältigung von urheberrechtsgeschützten Inhalten bekannt sein, haben aber auch legale Anwendungen im Bereich des verteilten Rechnens. Verfahren mit effizienten Nachschlage- und Update-Operationen wie z.B. Chord und Kademlia basieren auf der algorithmisch interessanten Technik des Consistent Hashing, die hier vorgestellt werden soll.
• Datenstromalgorithmen. Im üblichen Algorithmenentwurfsszenario betrachten wir Rechnermodelle, die von einer statischen Eingabe ausgehen, auf die der Rechner wahlfreien Zugriff hat. In vielen Anwendungen aus dem Bereich Internet geht es aber darum, einen Datenstrom aus in schneller zeitlicher Abfolge am Rechner ankommenden Datenpaketen zu verarbeiten, die nicht alle zwischengespeichert werden können. Ein Standardbeispiel ist die Erstellung von Statistiken über den Datenverkehr, der von einem Router verarbeitet wird. Auf dieses Szenario ist das Modell der Datenstromalgorithmen zugeschnitten, das inzwischen in Theorie und Praxis sehr intensiv untersucht worden ist. Wir werden in der Vorlesung sowohl obere Schranken in Form von Algorithmen als auch untere Schranken behandeln.