Aufgabe 1 c

Wie schafft es eine Suchmaschine, wie z.B. Google, das ”ganze Web“ zu erfassen? Erläutern Sie, wo die besonderen Schwierigkeiten eines Web-Crawlers (z.B. GoogleBot) bei der Erfassung des ”ganzen Webs“ liegen, und wie man diese beheben kann.

• Sehr große Datenmenge muss verarbeitet werden
  • effiziente Speicherstruktur notwendig, um schnelle Lese-/ Suchoperationen zu ermöglichen
• Datenmenge ändert sich potentiell häufig
  • regelmäßiges Herunterladen von Webseiten notwendig
  • Webseiten mit hohem PageRank werden dabei öfter besucht, als Webseiten mit niedrigerem PageRank
  • Der PageRank einer Webseite ist hoch, wenn viele Seiten auf die entsprechende Seite verweisen und wenn die referenzierten Seiten einen hohen PageRank haben
• Multimedia-Inhalte, die weiterführende Links für Webcrawler unauffindbar machen

Aufgabe 3 b

Angenommen, Sie hätten eine neue, semantische WWW-Suchmaschine implementiert und wollten die Welt von der überragenden Qualität ihrer Suchergebnisse überzeugen. Wie können Sie dies objektiv bewerkstelligen? Legen Sie dabei den Schwerpunkt auf die Möglichkeiten eines Vergleichs mit anderen Suchmaschinen und wie dieser praktisch umgesetzt und evaluiert werden könnte.

• Grundlage eines solchen Vergleichs kann nur eine nicht änderbare Kopie eines Teils des Webs sein (gefährlich, weil Auswahl des Fragments das Ergebnis beeinflussen kann), da sonst fraglich ist, ob beide Messungen auf dem gleichen Datenbestand basieren
  • Dieser Ausschnitt sollte nicht nur aufbereitete und kontrollierte Informationen aus Wikipedia enthalten (wie z.B. bei powerset und anderen Semantische-Suche-Projekten).
• Größen, die unter 3 a genannt wurden, können mit verschiedenen Probanden gemessen werden.
• Da das Credo semantischer Suchmaschinen ist, natürlichsprachliche Eingaben zu bearbeiten, sollten die Auswahl der Probanden repräsentativ bezüglich der Sprachkompetenz sein.
  • Muttersprachler oder nicht?
  • Alter
  • Bildungsstand

Weitere Aspekte, die den vergleich erschweren:

• Ist Eingabe von ganzen Sätzen einfacher als die Eingabe von Schlüsselwörtern?
• Kann man immer eine präzise Frage formulieren?
• Ergebnis: Links zu Webseiten, die gesuchte Informationen enthalten oder generierte Antworten.

Aufgabe 3 a

Wie lässt sich die Qualität der Suchergebnisse einer WWW-Suchmaschine objektiv messen?
Erläutern Sie entsprechende Maßgrößen und geben Sie jeweils ein Beispiel für deren Anwendung.

• Hypothese 1: Ein gute WWW-Suchmaschine ist eine, mit deren Hilfe man schnell die Information findet, die man sucht.
• grundlegende Kategorisierung: Information gefunden oder nicht gefunden?
• Wie kann man “schnelles Finden” messen?
  • Mausklicks
  • Zeitdauer
  • Anzahl der angeklickten Treffer

• Hypothese 2: Eine gute WWW-Suchmaschine ist eine, die für den Benutzer einfach und verständlich erscheint.
• Messgrößen, Qualitätsmerkmale:
  • Usability, einfache Benutzungsschnittstelle, Barrierefreiheit
  • Anpassbarkeit, Benutzereinstellungen, automatische Personalisierung, Zielgruppenorientierung
  • Kompetenz, Benutzer versteht Suchmaschine und kann Qualität der Ergebnisse einschätzen
  • Anzahl der Ergebnisse, Sortierung/ Kategorisierung/ Ordnung der Ergebnisse, Verhältnis des Anklickens “falscher” und “richtiger” Treffer

Aufgabe 1 b

Wie könnte eine Messung dieser Größen praktisch statt finden? Diskutieren Sie die praktische Umsetzung insbesondere in Bezug auf Skalierbarkeit und Effizienz.

Anzahl der Webseiten via Webcrawler:

• Parallelisierung aufgrund der riesigen Anzahl an Webseiten unumgänglich
• Trotzdem gemeinsame Datenbasis notwendig, um Dopplungen zu vermeiden

Anzahl der DNS-Einträge via ZONE:

• Skalierbarkeit ist gegeben, denn Parallelisierung kann durch Gruppierung der TLDs erreicht werden
• Skalierbarkeit ist nicht gegeben, denn Traffic um den Traffic so gering wie möglich zu halten, sollte nur eine Instanz dieses Programmes zu einem Zeitpunkt laufen

Aufgabe 1 a

Welches sind sinnvolle Messgrößen zur Bestimmung der Größe des Internets? Diskutieren Sie ihre Antworten …

Messgröße	Vollständigkeit	Praktikabilität	Aussagekraft
Anzahl der verbundenen Hosts	unvollständig: End-Nutzer-Hosts sind meist nur temporär verbunden Erreichbarkeit von Hosts in nicht öffentlichen Netzen? (Firmen-Intranets, etc.)	nicht realisierbar, denn Informationen über die tatsächlich mit dem Netz verbundenen Hosts haben nur ISPs, die solche Daten nicht zur Verfügung stellen	wenig aussagekräftig (s. Vollständigkeit)
Anzahl der Webseiten	unvollständig: Web ist nur ein Dienst, der durch das Internet ermöglicht wird (eMail, …)	realisierbar durch Webcrawler, Schwierigkeiten dabei: bestehende Datenmenge aktuell halten mit rasantem Wachstum Schritt halten	wenig aussagekräftig (s. Vollständigkeit)
Anzahl der DNS-Einträge	unvollständig: End-Nutzer-Hosts verfügen nicht über eine eigene Domain	realisiert durch ZONE (RFC 1296), Schwierigkeiten dabei: erzeugt erheblichen Traffic erzeugt große Last auf den DNS-Servern	wenig aussagekräftig (s. Vollständigkeit)

Aufgabe 1 d

Implementierungsaufgabe: Implementieren Sie einen primitiven WebCrawler…

Hier findet man den WC als php-Script.

Und hier den anderen in JavaScript (Browsereinstellung: JavaScript-Zugriff auf entfernte Dateien zulassen).

Einschränkungen: Die Betonung liegt auf “primitiv”.

Frage: Wie schnell ist Ihr WebCrawler? Wie lange bräuchte er, um die 10¹² Web-Seiten zu erfassen, die der GoogleBot erfasst hat? Gemessen an dem von Ihnen verwendeten Datenstrukturen, wieviel Speicherplatz würde Ihr Crawler für das Erfassen von 10¹² Web-Seiten benötigen?

Der WC führt zwei Listen: eine mit den n Seiten, die für den Suchindex erfasst wurden und eine für die m Seiten, die in den Index-Seiten gefunden wurden und noch selbst indiziert werden müssen. Der Speicherbedarf beträgt also:

Speicherbedarf = n + m Einträge

Da ein Eintrag in diesem primitiven Beispiel-WC keine weiteren Informationen enthält als einen String mit der URL, beträgt der Speicherbedarf also (n+m)*Stringlänge.

Da der Algorithmus quadratische Komplexität hat, werden ca. 10¹⁰⁰ s benötigt, um 10¹² Seiten zu indizieren.

Aufgabe 2 f

Frage: Worin liegt die Schwierigkeit bei der Lösung dieser Fragen und warum sind diese Fragen insbesondere mit einer Schlagwort-basierten Suchmaschine nur schwer zu lösen?

• je mehr und je speziellere Schlagwörter gegeben, desto erfolgreicher die schlagwortbasierte Suche (siehe Aufgaben 1a und 1e)
• Schwierigkeiten bei wenigen sehr allgemeinen Schlagwörtern (Oberbegriffe) in sehr beliebigen Kombinationen (siehe Aufgaben 1b und 1c)
  “Währung”+”Land”+”2000″ => 914.000 Treffer bei google
  “Schweiz”+”Deutschland”+”Lehrerin”+”Fräulein” => 17.000 Treffer bei google