Web-Crawler

Das Verhalten eines Web-Crawlers ist das Ergebnis einer Kombination von Richtlinien:

• Eine Auswahl-Richtlinie, die angibt, welche Seiten heruntergeladen werden sollen,
• eine Wiederbesuchs-Richtlinie, die angibt, wann nach Änderungen an den Seiten gesucht werden soll,
• eine Höflichkeits-Richtlinie, die angibt, wie die Überlastung von Websites vermieden werden soll.
• eine Parallelisierungs-Policy, die angibt, wie verteilte Web-Crawler koordiniert werden sollen.

Auswahl-PolicyEdit

Bei der derzeitigen Größe des Webs decken selbst große Suchmaschinen nur einen Teil des öffentlich verfügbaren Teils ab. Eine Studie aus dem Jahr 2009 zeigte, dass selbst große Suchmaschinen nicht mehr als 40-70 % des indizierbaren Webs indizieren; eine frühere Studie von Steve Lawrence und Lee Giles zeigte, dass keine Suchmaschine 1999 mehr als 16 % des Webs indizierte. Da ein Crawler immer nur einen Bruchteil der Webseiten herunterlädt, ist es höchst wünschenswert, dass der heruntergeladene Bruchteil die relevantesten Seiten enthält und nicht nur eine zufällige Stichprobe des Webs.

Dies erfordert eine Metrik der Wichtigkeit für die Priorisierung von Webseiten. Die Wichtigkeit einer Seite ist eine Funktion ihrer intrinsischen Qualität, ihrer Popularität in Bezug auf Links oder Besuche und sogar ihrer URL (letzteres ist der Fall bei vertikalen Suchmaschinen, die auf eine einzige Top-Level-Domain beschränkt sind, oder bei Suchmaschinen, die auf eine feste Website beschränkt sind). Der Entwurf einer guten Auswahlpolitik hat eine zusätzliche Schwierigkeit: Sie muss mit partiellen Informationen arbeiten, da der vollständige Satz von Webseiten während des Crawlings nicht bekannt ist.

Junghoo Cho et al. haben die erste Studie über Richtlinien für die Crawling-Planung durchgeführt. Ihr Datensatz war ein 180.000-Seiten-Crawl von der Domain stanford.edu, bei dem eine Crawling-Simulation mit verschiedenen Strategien durchgeführt wurde. Die getesteten Ordnungsmetriken waren Breadth-First, Backlink-Anzahl und partielle PageRank-Berechnungen. Eine der Schlussfolgerungen war, dass, wenn der Crawler Seiten mit hohem Pagerank früh während des Crawling-Prozesses herunterladen möchte, dann ist die partielle Pagerank-Strategie die bessere, gefolgt von Breadth-First und Backlink-Count. Diese Ergebnisse beziehen sich jedoch nur auf eine einzige Domain. Cho schrieb auch seine Doktorarbeit in Stanford über Web-Crawling.

Najork und Wiener führten einen tatsächlichen Crawl von 328 Millionen Seiten durch und verwendeten dabei die Breadth-First-Reihenfolge. Sie fanden heraus, dass ein Breadth-First-Crawl Seiten mit hohem Pagerank früh im Crawl erfasst (aber sie verglichen diese Strategie nicht mit anderen Strategien). Die Erklärung der Autoren für dieses Ergebnis ist, dass „die wichtigsten Seiten viele Links zu ihnen von zahlreichen Hosts haben, und diese Links werden früh gefunden, unabhängig davon, von welchem Host oder welcher Seite der Crawl ausgeht.“

Abiteboul entwickelte eine Crawling-Strategie, die auf einem Algorithmus namens OPIC (On-line Page Importance Computation) basiert. Bei OPIC erhält jede Seite eine anfängliche Summe „Geld“, die gleichmäßig auf die Seiten verteilt wird, auf die sie zeigt. Es ähnelt einer PageRank-Berechnung, ist aber schneller und wird nur in einem Schritt durchgeführt. Ein OPIC-gesteuerter Crawler lädt zuerst die Seiten in der Crawling-Frontier mit höheren Beträgen an „Cash“ herunter. Die Experimente wurden in einem synthetischen 100.000-Seiten-Graphen mit einer Power-Law-Verteilung der In-Links durchgeführt. Es gab jedoch weder einen Vergleich mit anderen Strategien noch Experimente im realen Web.

Boldi et al. verwendeten Simulationen auf Teilmengen des Webs von 40 Millionen Seiten aus der .it-Domäne und 100 Millionen Seiten aus dem WebBase-Crawl und testeten Breadth-First gegen Depth-First, Random-Ordering und eine allwissende Strategie. Der Vergleich basierte darauf, wie gut der auf einem partiellen Crawl berechnete PageRank den wahren PageRank-Wert approximiert. Überraschenderweise liefern einige Besuche, die den PageRank sehr schnell akkumulieren (vor allem Breadth-First und der allwissende Besuch), sehr schlechte progressive Annäherungen.

Baeza-Yates et al. verwendeten Simulationen auf zwei Teilmengen des Webs von 3 Millionen Seiten aus der .gr- und .cl-Domäne und testeten verschiedene Crawling-Strategien. Sie zeigten, dass sowohl die OPIC-Strategie als auch eine Strategie, die die Länge der Pro-Site-Warteschlangen nutzt, besser sind als das Breadth-First-Crawling, und dass es auch sehr effektiv ist, einen früheren Crawl, wenn er verfügbar ist, als Leitfaden für den aktuellen Crawl zu verwenden.

Daneshpajouh et al. entwarfen einen Community-basierten Algorithmus zur Entdeckung guter Seeds. Ihre Methode crawlt Webseiten mit hohem PageRank aus verschiedenen Communities in weniger Iterationen im Vergleich zum Crawlen ausgehend von zufälligen Seeds. Mit dieser neuen Methode kann man gute Seeds aus einem zuvor gecrawlten Web-Graphen extrahieren. Mit diesen Seeds kann ein neuer Crawl sehr effektiv sein.

Einschränkung von gefolgten LinksBearbeiten

Ein Crawler möchte vielleicht nur HTML-Seiten suchen und alle anderen MIME-Typen vermeiden. Um nur HTML-Ressourcen anzufordern, kann ein Crawler eine HTTP HEAD-Anfrage stellen, um den MIME-Typ einer Webressource zu ermitteln, bevor er die gesamte Ressource mit einer GET-Anfrage anfordert. Um zahlreiche HEAD-Anfragen zu vermeiden, kann ein Crawler die URL untersuchen und eine Ressource nur anfordern, wenn die URL mit bestimmten Zeichen wie .html, .htm, .asp, .aspx, .php, .jsp, .jspx oder einem Schrägstrich endet. Diese Strategie kann dazu führen, dass zahlreiche HTML-Webressourcen unbeabsichtigt übersprungen werden.

Einige Crawler vermeiden es auch, Ressourcen anzufordern, die ein „?“ enthalten (dynamisch erzeugt werden), um Spider-Fallen zu vermeiden, die dazu führen können, dass der Crawler eine unendliche Anzahl von URLs von einer Website herunterlädt. Diese Strategie ist unzuverlässig, wenn die Site URL-Rewriting verwendet, um ihre URLs zu vereinfachen.

URL-NormalisierungBearbeiten

Crawler führen in der Regel eine Art von URL-Normalisierung durch, um zu vermeiden, dass dieselbe Ressource mehrmals gecrawlt wird. Der Begriff URL-Normalisierung, auch URL-Kanonisierung genannt, bezieht sich auf den Prozess der Modifizierung und Standardisierung einer URL in einer konsistenten Weise. Es gibt verschiedene Arten der Normalisierung, die durchgeführt werden können, einschließlich der Umwandlung von URLs in Kleinbuchstaben, der Entfernung von „.“- und „..“-Segmenten und dem Hinzufügen von abschließenden Schrägstrichen zur nicht leeren Pfadkomponente.

Pfadaufsteigendes Crawling

Einige Crawler beabsichtigen, so viele Ressourcen wie möglich von einer bestimmten Website herunter- bzw. hochzuladen. Daher wurde ein pfadaufsteigender Crawler eingeführt, der zu jedem Pfad in jeder URL aufsteigt, die er zu crawlen beabsichtigt. Wenn zum Beispiel eine Start-URL von http://llama.org/hamster/monkey/page.html angegeben wird, versucht er, /hamster/monkey/, /hamster/ und / zu crawlen. Cothey fand heraus, dass ein pfadaufsteigender Crawler sehr effektiv darin war, isolierte Ressourcen zu finden oder Ressourcen, für die beim normalen Crawling kein eingehender Link gefunden worden wäre.

Fokussiertes CrawlingBearbeiten

Die Wichtigkeit einer Seite für einen Crawler kann auch als Funktion der Ähnlichkeit einer Seite zu einer bestimmten Anfrage ausgedrückt werden. Web-Crawler, die versuchen, Seiten herunterzuladen, die einander ähnlich sind, werden fokussierte Crawler oder thematische Crawler genannt. Die Konzepte des topischen und fokussierten Crawlings wurden zuerst von Filippo Menczer und von Soumen Chakrabarti et al. eingeführt.

Das Hauptproblem beim fokussierten Crawling ist, dass wir im Kontext eines Web-Crawlers in der Lage sein möchten, die Ähnlichkeit des Textes einer gegebenen Seite mit der Anfrage vorherzusagen, bevor wir die Seite tatsächlich herunterladen. Ein möglicher Prädiktor ist der Ankertext von Links; dies war der Ansatz, der von Pinkerton im ersten Web-Crawler der frühen Tage des Webs verfolgt wurde. Diligenti et al. schlagen vor, den kompletten Inhalt der bereits besuchten Seiten zu verwenden, um die Ähnlichkeit zwischen der fahrenden Anfrage und den noch nicht besuchten Seiten abzuleiten. Die Leistung eines fokussierten Crawlings hängt hauptsächlich von der Reichhaltigkeit der Links in dem spezifischen Thema ab, das gesucht wird, und ein fokussiertes Crawling verlässt sich normalerweise auf eine allgemeine Web-Suchmaschine, um Startpunkte zu liefern.

Akademisch-fokussierter Crawler

Ein Beispiel für fokussierte Crawler sind akademische Crawler, die frei zugängliche akademische Dokumente crawlen, wie z. B. der citeseerxbot, der Crawler der Suchmaschine CiteSeerX. Andere akademische Suchmaschinen sind Google Scholar und Microsoft Academic Search usw. Da die meisten akademischen Arbeiten in PDF-Formaten veröffentlicht werden, ist diese Art von Crawler besonders daran interessiert, PDF-, PostScript- und Microsoft Word-Dateien einschließlich ihrer gezippten Formate zu crawlen. Aus diesem Grund müssen allgemeine Open-Source-Crawler, wie z. B. Heritrix, angepasst werden, um andere MIME-Typen herauszufiltern, oder es wird eine Middleware verwendet, um diese Dokumente zu extrahieren und in die fokussierte Crawl-Datenbank und das Repository zu importieren. Die Identifizierung, ob es sich bei diesen Dokumenten um akademische Dokumente handelt oder nicht, ist eine Herausforderung und kann einen erheblichen Overhead zum Crawling-Prozess hinzufügen, daher wird dies als Post-Crawling-Prozess unter Verwendung von Algorithmen für maschinelles Lernen oder reguläre Ausdrücke durchgeführt. Diese akademischen Dokumente stammen in der Regel von Homepages von Fakultäten und Studenten oder von Publikationsseiten von Forschungsinstituten. Da akademische Dokumente nur einen kleinen Teil der gesamten Webseiten ausmachen, ist eine gute Auswahl der Seeds wichtig, um die Effizienz dieser Webcrawler zu erhöhen. Andere akademische Crawler können einfache Text- und HTML-Dateien herunterladen, die Metadaten von akademischen Papieren enthalten, wie z. B. Titel, Papiere und Abstracts. Dies erhöht die Gesamtzahl der Papiere, aber ein signifikanter Anteil bietet möglicherweise keine kostenlosen PDF-Downloads an.

Semantisch fokussierter Crawler

Ein anderer Typ von fokussierten Crawlern ist der semantisch fokussierte Crawler, der Domänen-Ontologien verwendet, um thematische Karten darzustellen und Webseiten mit relevanten ontologischen Konzepten für die Auswahl und Kategorisierung zu verknüpfen. Außerdem können Ontologien während des Crawling-Prozesses automatisch aktualisiert werden. Dong et al. stellten einen solchen auf Ontologie-Lernen basierenden Crawler vor, der eine Support-Vektor-Maschine verwendet, um den Inhalt der ontologischen Konzepte beim Crawlen von Webseiten zu aktualisieren.

Re-visit policyEdit

Das Web ist sehr dynamisch, und das Crawlen eines Teils des Webs kann Wochen oder Monate dauern. Bis ein Web-Crawler seinen Crawl beendet hat, können viele Ereignisse stattgefunden haben, einschließlich Erstellungen, Aktualisierungen und Löschungen.

Aus Sicht der Suchmaschine ist es mit Kosten verbunden, ein Ereignis nicht zu erkennen und somit eine veraltete Kopie einer Ressource zu haben. Die am häufigsten verwendeten Kostenfunktionen sind Frische und Alter.

Frische: Dies ist ein binäres Maß, das angibt, ob die lokale Kopie korrekt ist oder nicht. Die Frische einer Seite p im Repository zum Zeitpunkt t ist definiert als:

F p ( t ) = { 1, wenn p zum Zeitpunkt t korrekt ist, und 0, wenn sie nicht korrekt ist {\displaystyle F_{p}(t)={\begin{cases}1&{\rm {if}}~p~{\rm {~is~equal~to~the~local~copy~at~time}}~t\\0&{\rm {otherwise}}\end{cases}}}

Age: Dies ist ein Maß, das angibt, wie veraltet die lokale Kopie ist. Das Alter einer Seite p im Repository, zum Zeitpunkt t, ist definiert als:

A p ( t ) = { 0, wenn p zum Zeitpunkt t nicht m o d i f i z i e r t ist – m o d i f i z i e r t e s Alter der Seite w i s e {\displaystyle A_{p}(t)={\begin{cases}0&{\rm {if}~p~{\rm {~ist~nicht~geändert~zum~Zeitpunkt}}~t\\t-{\rm {~modification~time~of}~p&{\rm {~otherwise}}\end{cases}}}

Coffman et al. arbeiteten mit einer Definition des Ziels eines Web-Crawlers, die äquivalent zu Freshness ist, verwenden aber eine andere Formulierung: Sie schlagen vor, dass ein Crawler den Anteil der Zeit, in der Seiten veraltet sind, minimieren muss. Sie stellten außerdem fest, dass das Problem des Web-Crawlings als ein Multiple-Queue-, Single-Server-Polling-System modelliert werden kann, bei dem der Web-Crawler der Server und die Websites die Warteschlangen sind. Seitenänderungen sind die Ankunft der Kunden, und Umschaltzeiten sind das Intervall zwischen Seitenzugriffen auf eine einzelne Website. Unter diesem Modell ist die mittlere Wartezeit für einen Kunden im Abrufsystem äquivalent zum durchschnittlichen Alter des Web-Crawlers.

Das Ziel des Crawlers ist es, die durchschnittliche Frische der Seiten in seiner Sammlung so hoch wie möglich zu halten, oder das durchschnittliche Alter der Seiten so niedrig wie möglich zu halten. Diese Ziele sind nicht äquivalent: Im ersten Fall geht es dem Crawler nur darum, wie viele Seiten veraltet sind, während es ihm im zweiten Fall darum geht, wie alt die lokalen Kopien der Seiten sind.

Zwei einfache Re-Visiting-Policies wurden von Cho und Garcia-Molina untersucht:

• Uniform policy: Hierbei werden alle Seiten der Sammlung mit der gleichen Häufigkeit erneut besucht, unabhängig von ihrer Änderungsrate.
• Proportionale Politik: Hierbei werden die Seiten, die sich häufiger ändern, häufiger besucht. Die Besuchshäufigkeit ist direkt proportional zur (geschätzten) Änderungshäufigkeit.

In beiden Fällen kann die wiederholte Crawling-Reihenfolge der Seiten entweder in einer zufälligen oder in einer festen Reihenfolge erfolgen.

Cho und Garcia-Molina bewiesen das überraschende Ergebnis, dass die einheitliche Richtlinie in Bezug auf die durchschnittliche Frische die proportionale Richtlinie sowohl in einem simulierten Web als auch in einem realen Web-Crawl übertrifft. Intuitiv ist die Argumentation, dass Web-Crawler eine Grenze haben, wie viele Seiten sie in einem gegebenen Zeitrahmen crawlen können, (1) dass sie zu viele neue Crawls schnell wechselnden Seiten auf Kosten von weniger häufig aktualisierten Seiten zuweisen, und (2) dass die Frische von schnell wechselnden Seiten kürzer anhält als die von weniger häufig wechselnden Seiten. Mit anderen Worten, eine proportionale Richtlinie weist mehr Ressourcen für das Crawlen von sich häufig aktualisierenden Seiten zu, erfährt aber insgesamt weniger Frischezeit von ihnen.

Um die Frische zu verbessern, sollte der Crawler die Elemente bestrafen, die sich zu oft ändern. Die optimale Re-Visiting-Policy ist weder die Uniform-Policy noch die Proportional-Policy. Die optimale Methode, um die durchschnittliche Frische hoch zu halten, beinhaltet das Ignorieren der Seiten, die sich zu oft ändern, und die optimale Methode, um das durchschnittliche Alter niedrig zu halten, besteht darin, Zugriffshäufigkeiten zu verwenden, die monoton (und sublinear) mit der Änderungsrate jeder Seite ansteigen. In beiden Fällen liegt das Optimum näher an der gleichmäßigen Politik als an der proportionalen Politik: wie Coffman et al. anmerken, „um die erwartete Veralterungszeit zu minimieren, sollten die Zugriffe auf eine bestimmte Seite so gleichmäßig wie möglich gehalten werden“. Explizite Formeln für die Re-Visit-Policy sind im Allgemeinen nicht erreichbar, aber man erhält sie numerisch, da sie von der Verteilung der Seitenwechsel abhängen. Cho und Garcia-Molina zeigen, dass die Exponentialverteilung eine gute Anpassung für die Beschreibung von Seitenwechseln ist, während Ipeirotis et al. zeigen, wie man mit statistischen Werkzeugen Parameter entdeckt, die diese Verteilung beeinflussen. Beachten Sie, dass die hier betrachteten Wiederbesuchsrichtlinien alle Seiten als homogen in Bezug auf die Qualität betrachten („alle Seiten im Web sind gleich viel wert“), was kein realistisches Szenario ist, so dass weitere Informationen über die Qualität der Webseiten einbezogen werden sollten, um eine bessere Crawling-Richtlinie zu erreichen.

HöflichkeitsrichtlinieBearbeiten

Crawler können Daten viel schneller und in größerer Tiefe abrufen als menschliche Sucher, so dass sie einen lähmenden Einfluss auf die Leistung einer Website haben können. Wenn ein einzelner Crawler mehrere Anfragen pro Sekunde durchführt und/oder große Dateien herunterlädt, kann ein Server Schwierigkeiten haben, mit den Anfragen von mehreren Crawlern Schritt zu halten.

Wie Koster anmerkt, ist der Einsatz von Web-Crawlern für eine Reihe von Aufgaben nützlich, hat aber für die Allgemeinheit seinen Preis. Zu den Kosten für die Verwendung von Web-Crawlern gehören:

• Netzwerkressourcen, da Crawler eine erhebliche Bandbreite benötigen und über einen langen Zeitraum mit einem hohen Grad an Parallelität arbeiten;
• Serverüberlastung, insbesondere wenn die Häufigkeit der Zugriffe auf einen bestimmten Server zu hoch ist;
• schlecht geschriebene Crawler, die Server oder Router zum Absturz bringen können oder die Seiten herunterladen, die sie nicht verarbeiten können; und
• persönliche Crawler, die, wenn sie von zu vielen Benutzern eingesetzt werden, Netzwerke und Webserver stören können.

Eine Teillösung für diese Probleme ist das Robots-Exclusion-Protokoll, auch bekannt als robots.txt-Protokoll, das ein Standard ist, mit dem Administratoren angeben können, auf welche Teile ihrer Webserver Crawler keinen Zugriff haben sollen. Dieser Standard enthält keinen Vorschlag für das Intervall der Besuche auf demselben Server, obwohl dieses Intervall die effektivste Methode ist, um eine Überlastung des Servers zu vermeiden. Seit kurzem können kommerzielle Suchmaschinen wie Google, Ask Jeeves, MSN und Yahoo! Search einen zusätzlichen „Crawl-delay:“-Parameter in der robots.txt-Datei verwenden, um die Anzahl der Sekunden anzugeben, die zwischen den Anfragen gewartet werden sollen.

Das erste vorgeschlagene Intervall zwischen aufeinanderfolgenden Seitenladungen betrug 60 Sekunden. Wenn jedoch Seiten mit dieser Rate von einer Website mit mehr als 100.000 Seiten über eine perfekte Verbindung mit null Latenz und unendlicher Bandbreite heruntergeladen würden, würde es mehr als 2 Monate dauern, nur diese gesamte Website herunterzuladen; außerdem würde nur ein Bruchteil der Ressourcen dieses Webservers verwendet werden. Das erscheint nicht akzeptabel.

Cho verwendet 10 Sekunden als Intervall für Zugriffe, der WIRE-Crawler verwendet 15 Sekunden als Standard. Der MercatorWeb-Crawler folgt einer adaptiven Höflichkeitspolitik: Wenn es t Sekunden dauerte, ein Dokument von einem bestimmten Server herunterzuladen, wartet der Crawler 10t Sekunden, bevor er die nächste Seite herunterlädt. Dill et al. verwenden 1 Sekunde.

Für diejenigen, die Web-Crawler zu Forschungszwecken einsetzen, ist eine detailliertere Kosten-Nutzen-Analyse erforderlich, und ethische Erwägungen sollten bei der Entscheidung, wo gecrawlt werden soll und wie schnell gecrawlt werden soll, berücksichtigt werden.

Anekdotische Belege aus Zugriffsprotokollen zeigen, dass die Zugriffsintervalle bekannter Crawler zwischen 20 Sekunden und 3-4 Minuten variieren. Es ist erwähnenswert, dass selbst wenn man sehr höflich ist und alle Sicherheitsvorkehrungen trifft, um eine Überlastung der Webserver zu vermeiden, einige Beschwerden von Webserver-Administratoren eingehen. Brin und Page stellen fest, dass: „… einen Crawler laufen zu lassen, der sich mit mehr als einer halben Million Servern verbindet (…) erzeugt eine ordentliche Menge an E-Mails und Telefonanrufen. Wegen der riesigen Anzahl von Leuten, die online gehen, gibt es immer welche, die nicht wissen, was ein Crawler ist, weil es der erste ist, den sie gesehen haben.“

ParallelisierungsrichtlinieBearbeiten

Ein paralleler Crawler ist ein Crawler, der mehrere Prozesse parallel ausführt. Ziel ist es, die Download-Rate zu maximieren und gleichzeitig den Overhead durch die Parallelisierung zu minimieren und wiederholte Downloads der gleichen Seite zu vermeiden. Um zu vermeiden, dass dieselbe Seite mehrmals heruntergeladen wird, benötigt das Crawling-System eine Richtlinie für die Zuweisung der neuen URLs, die während des Crawling-Prozesses entdeckt werden, da dieselbe URL von zwei verschiedenen Crawling-Prozessen gefunden werden kann.