In diesem Beitrag stellen die beiden Gründer Sergej Brin und Larry Page Google vor, einen Prototyp einer groß angelegten Suchmaschine, die die im Hypertext vorhandene Struktur stark nutzt. Google wurde entwickelt, um das Web effizient zu crawlen und zu indizieren und viel zufriedenstellendere Suchergebnisse zu erzielen als bestehende Systeme.

Eine Suchmaschine zu entwickeln ist eine anspruchsvolle Aufgabe. Suchmaschinen indexieren Dutzende bis Hunderte von Millionen von Webseiten mit einer vergleichbaren Anzahl von verschiedenen Begriffen. Sie beantworten täglich mehrere zehn Millionen Anfragen. Trotz der Bedeutung der großen Suchmaschinen im Internet, wurde bisher noch sehr wenig Zeit in die Forschung in diesem Bereich investiert. Zudem haben sich aufgrund der raschen Fortschritte in der Technologie Suchmaschinen in den letzten 3 Jahren extrem weiterentwickelt. Dieses Paper bietet eine ausführliche Beschreibung der Web-Suchmaschine Google.

Abgesehen von den Problemen bei der Skalierung traditioneller Suchtechniken auf Daten dieser Größenordnung gibt es neue technische Herausforderungen bei der Verwendung der im Hypertext enthaltenen Zusatzinformationen, um bessere Suchergebnisse zu erzielen. Dieses Paper befasst sich mit der Frage, wie man ein praktisches Großsystem aufbauen kann, das die zusätzlichen Informationen, die im Hypertext enthalten sind, nutzen kann. Außerdem beschäftigen Brin/Page sich mit dem Problem, wie man effektiv mit unkontrollierten Hypertext-Sammlungen umgeht, in denen jeder alles veröffentlichen kann, was er will.

Einführung.

Das Web stellt neue Herausforderungen an die Informationsbeschaffung. Die Menge an Informationen im Web wächst rasant, ebenso wie die Zahl der neuen Nutzer, die noch keine Erfahrung in der Web-Recherche haben. Es ist wahrscheinlich, dass Nutzer im Internet mit einer Suchmaschine surfen. Von Menschen gepflegten Listen decken populäre Themen effektiv ab, sind aber subjektiv, teuer in der Erstellung und Pflege, langsam in der Verbesserung und können nicht alle esoterischen Themen abdecken. Automatisierte Suchmaschinen, die auf Keyword-Matching angewiesen sind, liefern in der Regel zu viele minderwertige Treffer. Erschwerend kommt hinzu, dass einige Werbetreibende versuchen, die Aufmerksamkeit der Menschen zu gewinnen, indem Sie Maßnahmen ergreifen, die dazu dienen, automatisierte Suchmaschinen in die Irre zu führen. Mit Google wurde eine große Suchmaschine aufgebaut, die viele der Probleme bestehender Systeme anspricht. Besonders stark wird die zusätzliche Struktur des Hypertextes genutzt, um eine wesentlich höhere Qualität der Suchergebnisse zu erzielen. Brin und Page haben den Suchmaschinennamen Google gewählt, weil es eine gängige Schreibweise von googol oder 10100 ist und gut zu ihrem Ziel passt, sehr große Suchmaschinen zu entwickeln.

Die Entwicklung von Websuchmaschinen zwischen 1994 und 2000.

Die Suchmaschinentechnologie musste dramatisch skaliert werden, um mit dem Wachstum des Internets Schritt halten zu können. 1994 hatte eine der ersten Web-Suchmaschinen, der World Wide Web Worm, einen Index von 110.000 Webseiten und webfähigen Dokumenten. Ab November 1997 behaupten die Top-Suchmaschinen, von 2 Millionen (WebCrawler) bis 100 Millionen Webdokumente zu indizieren. Es ist absehbar, dass bis zum Jahr 2000 ein umfassender Index des Webs über eine Milliarde Dokumente erhalten wird. Gleichzeitig ist auch die Anzahl der Anfragen, die von Suchmaschinen bearbeitet werden, enorm gestiegen. Im März und April 1994 erhielt der World Wide Web Worm durchschnittlich etwa 1500 Anfragen pro Tag. Im November 1997 behauptete Altavista, dass es etwa 20 Milliarden Anfragen pro Tag bearbeitet hat. Mit der steigenden Anzahl von Benutzern im Web und automatisierten Systemen, die Suchmaschinen abfragen, ist es wahrscheinlich, dass Top-Suchmaschinen bis zum Jahr 2000 Hunderte von Millionen von Anfragen pro Tag bearbeiten werden. Das Ziel von Google ist es, viele der Probleme in Bezug auf Qualität und Skalierbarkeit zu lösen, die durch die Skalierung der Suchmaschinentechnologie auf solche ungewöhnlichen Zahlen eingeführt worden.

Google: Skalierung mit dem Web.

Die Entwicklung einer Suchmaschine, die sich auch auf das heutige Web skalieren lässt, wirft viele neue Fragen auf. Schnelle Crawling-Technologie ist notwendig, um die Webdokumente zu sammeln und auf dem neuesten Stand zu halten. Der Speicherplatz muss effizient genutzt werden, um Indizes und optional die Dokumente selbst zu speichern. Das Indizierungssystem muss Hunderte von GigByte Daten effizient verarbeiten. Anfragen müssen schnell bearbeitet werden, mit einer Rate von Hunderten bis Tausenden pro Sekunde.

Diese Aufgaben werden mit dem Wachstum des Internets schwieriger. Allerdings haben sich die Leistung und die Kosten der Hardware drastisch verbessert, um die Schwierigkeiten teilweise auszugleichen. Es gibt jedoch einige bemerkenswerte Ausnahmen von diesem Fortschritt wie z.B. die Festplattensuchzeit und die Robustheit des Betriebssystems. Bei der Gestaltung von Google haben wir sowohl die Wachstumsrate des Webs als auch die technologischen Veränderungen berücksichtigt. Google ist so konzipiert, dass es sich gut auf extrem große Datenmengen skalieren lässt. Er nutzt den Speicherplatz für die Speicherung des Index effizient aus. Seine Datenstrukturen sind für einen schnellen und effizienten Zugriff optimiert. Darüber hinaus erwarten Brin und Page, dass die Kosten für die Indizierung und Speicherung von Text oder HTML im Verhältnis zur verfügbaren Menge sinken werden. Dies führt zu günstigen Skalierungseigenschaften für zentrale Systeme wie Google.

Designziele.

Verbesserte Suchqualität.

Page/Brin`s Hauptziel ist es, die Qualität von Web-Suchmaschinen zu verbessern. Im Jahr 1994 glaubten einige Leute, dass ein vollständiger Suchindex es ermöglichen würde, alles leicht zu finden. Laut Best of the Web 1994, sollte der beste Navigationsdienst es einfach machen, fast alles im Web zu finden. Das Web von 1997 ist jedoch ganz anders. Jeder, der in letzter Zeit eine Suchmaschine benutzt hat, kann leicht bezeugen, dass die Vollständigkeit des Index nicht der einzige Faktor für die Qualität der Suchergebnisse ist. „Junk-Ergebnisse“ waschen oft alle Ergebnisse aus, die einen Benutzer interessieren. Tatsächlich findet sich seit November 1997 nur noch eine der vier besten kommerziellen Suchmaschinen. Einer der Hauptursachen für dieses Problem ist, dass die Anzahl der Dokumente in den Indizes um viele Größenordnungen gestiegen ist, nicht aber die Möglichkeiten des Benutzers, Dokumente anzusehen. Die Menschen sind immer noch bereit, sich nur die ersten paar Dutzend Seiten anzusehen. Aus diesem Grund benötigen wir mit zunehmender Sammlungsgröße Werkzeuge mit sehr hoher Präzision. Tatsächlich wollen wir, dass unser Begriff „relevant“ nur die allerbesten Dokumente umfasst, da es Zehntausende von leicht relevanten Dokumenten geben kann. Diese sehr hohe Präzision ist auch auf Kosten des Rückrufs wichtig. Es gibt in letzter Zeit einen gewissen Optimismus, dass die Verwendung von mehr hypertextuellen Informationen dazu beitragen kann, die Suche und andere Anwendungen zu verbessern und der Linktext liefert viele Informationen zur Relevanzbearbeitung und Qualitäsfilterung. Google verwendet sowohl die Linkstruktur als auch den Ankertext.

Akademische Suchmaschinenforschung.

Neben dem enormen Wachstum ist das Web im Laufe der Zeit auch immer kommerzieller geworden. Im Jahr 1993 waren 1,5% der Webserver auf .com-Domains konfiguriert. Diese Zahl stieg 1997 auf über 60%. Gleichzeitig sind Suchmaschinen aus dem akademischen in den kommerziellen Bereich übergegangen. Bisher wurden die meisten Suchmaschinen in Unternehmen mit wenig technischen Detail entwickelt. Dadurch bleibt die Suchmaschinentechnologie weitgehend eine schwarze Kunst und ist werbeorientiert, Mit Google ist das Ziel verbunden, mehr Entwicklung und Verständnis in den akademischen Bereich zu bringen.

Ein weiteres wichtiges Designziel war es, Systeme zu bauen, die von einer vernünftigen Anzahl von Menschen genutzt werden können. Die Nutzung war Brin und Page wichtig, weil Sie der Meinung waren, dass einige der interessantesten Forschungsarbeiten die Nutzung der riesigen Menge an Nutzungsdaten, die von modernen Websystemen zur Verfügung stehen, beibehalten werden. Zum Beispiel werden täglich mehrere zehn Millionen Suchen durchgeführt. Allerdings ist es sehr schwierig, diese Daten zu erhalten, vor allem, weil sie als kommerziell wertvoll angesehen werden.

Das letzte Designziel war es, eine Architektur zu entwickeln, die neuartige Forschungsaktivitäten auf großformatigen Webdaten unterstützen kann. Um neue Forschungszwecke zu unterstützen, speichert Google alle Dokumente, die es durchsucht, in komprimierter Form. Eines von Brin/Pages Hauptziele bei der Entwicklung von Google war es, eine Umgebung zu schaffen, in der andere Forscher schnell einsteigen, große Teile des Internets verarbeiten und interessante Ergebnisse erzielen können, die sonst nur sehr schwer zu produzieren gewesen wären. In der kurzen Zeit, in der das System in Betrieb war, gab es bereits mehrere Veröffentlichungen mit Hilfe von Datenbanken, die von Google erstellt wurden und viele andere sind im Gange. Ein weiteres Ziel ist es, eine Spacelab-ähnliche Umgebung einzurichten, in der Forscher oder sogar Studenten interessante Experimente mit großformatigen Webdaten vorschlagen und durchführen können.

System Features.

Die Google-Suchmaschine hat zwei wichtige Funktionen, die ihr helfen, hochpräzise Ergebnisse zu liefern. Erstens nutzt es die Linkstruktur des Webs, um ein Qualitätsranking für jede Webseite zu berechnen. Dieses Ranking nennt sich PageRank. Zweitens nutzt Google den Link, um die Suchergebnisse zu verbessern.

PageRank: Ordnung ins Internet bringen.

Das Link-Diagramm des Internets ist eine wichtige Ressource, die in bestehenden Web-Suchmaschinen weitgehend ungenutzt geblieben ist. Brin/Page haben Maps erstellt, die bis zu 518 Millionen dieser Hyperlinks enthalten, eine bedeutende Stichprobe. Diese Maps ermöglichen eine schnelle Berechnung des PageRank einer Website, ein objektives Maß für ihre Verlinkbedeutung, das der subjektiven Vorstellung von Bedeutung entspricht. Aufgrund dieser Korrespondenz ist PageRank eine ausgezeichnete Möglichkeit, die Ergebnisse von Web-Stichwortsuchen zu priorisieren. Für die meisten populären Themen ist eine einfache Textvergleichssuche, die auf Webseiten-Titel beschränkt ist, sehr nützlich, wenn PageRank die Ergebnisse priorisiert. Auch bei der Art der Volltextsuche im Hauptsystem von Google hilft PageRank sehr viel weiter.

Beschreibung der PageRank-Berechnung.

Akademische Zitationsliteratur wurde auf das Web angewandt, vor allem durch das Zählen von Zitaten oder Backlinks zu einer bestimmten Seite. Dies gibt eine gewisse Änderung an die Wichtigkeit oder Qualität einer Seite. PageRank erweitert diese Idee, indem Links von allen Seiten nicht gleich gezählt werden und indem die Anzahl der Links auf einer Seite normalisiert wird.

PageRank ist wie folgt definiert:

„ Brin und Page gehen davon aus, dass Seite A die Seiten T1…Tn hat, die darauf verweisen. Der Parameter d ist ein Dämpfungsfaktor, der zwischen 0 und 1 eingestellt werden kann. D wird üblicherweise auf 0,85 gesetzt. Weitere Details zu d finden Sie im nächsten Abschnitt. Auch C(A) ist definiert als die Anzahl der Links, die von Seite A ausgehen. Der PageRank einer Seite A wird wie folgt angegeben:

PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))

Beachten Sie, dass die PageRanks eine Wahrscheinlichkeitsverteilung über Webseiten bilden, so dass die Summe der PageRanks aller Webseiten 1 ist.“

PageRank oder PR(A) kann mit einem einfachen iterativen Algorithmus berechnet werden und entspricht dem Haupteigenvektor der normalisierten Linkmatrix des Webs. Auch ein PageRank für 26 Millionen Webseiten kann in wenigen Stunden auf einer mittelgroßen Workstation berechnet werden. Es gibt viele weitere Details, die den Rahmen dieses Papers sprengen.

Intuitive Rechtfertigung.

PageRank kann man sich als Modell des Nutzerverhaltens vorstellen. Brin/Page gehen davon aus, dass es einen „zufälligen Surfer“ gibt, der eine Webseite nach dem Zufallsprinzip erhält und immer wieder auf Links klickt, nie zurückschlägt, sich aber schließlich langweilt und auf einer anderen zufälligen Seite beginnt. Die Wahrscheinlichkeit, dass der zufällige Surfer eine Seite besucht, ist der PageRank. Zudem steht der Dämpfungsfaktor d für die Wahrscheinlichkeit, dass sich der „zufällige Surfer“ auf jeder Seite langweilt und eine andere zufällige Seite anfordert. Eine wichtige Variante besteht darin, den Dämpfungsfaktor d nur auf eine einzelne Seite oder eine Gruppe von Seiten zu addieren. Dies ermöglicht eine Personalisierung und kann es nahezu unmöglich machen, das System absichtlich in die Irre zu führen, um ein besseres Ranking zu erhalten.

Eine weitere intuitive Rechtfertigung ist, dass eine Seite einen hohen PageRank haben kann, wenn es viele Seiten gibt, die darauf verweisen oder wenn es einige Seiten gibt, die darauf verweisen und einen hohen PageRank haben. Intuitiv sind Seiten, die an vielen Stellen im Web oft verlinkt werden, einen Blick wert. Auch Seiten, die vielleicht nur einen Link von so etwas wie der YAHOO!-Homepage haben, sind generell einen Blick wert. Wenn eine Seite nicht von hoher Qualität ist oder ein defekter Link vorliegt, ist es sehr wahrscheinlich, dass Yahoo`s Homepage nicht darauf verlinken würde. PageRank behandelt diesen beiden Fälle und alles dazwischen, indem es rekursiv Gewichte durch die Linkstruktur des Webs propagiert.

Ankertext.

Der Text von Links wird in Google besonders behandelt. Die meisten Suchmaschinen verbinden den Text eines Links mit der Seite, auf der sich der Link befindet. Außerdem verknüpfen wir sie mit der Seite, auf die der Link verweist. Dies hat mehrere Vorteile. Erstens bieten Anker oft genauere Beschreibungen von Webseiten als die Seiten selbst. Zweitens können Anker für Dokumente existieren, die nicht von einer textbasierten Suchmaschine indiziert werden können, wie z.B. Bilder, Programme und Datenbanken. Dadurch ist es möglich, nicht gecrawlte Webseiten zurückzugeben. Beachten Sie, dass Seiten, die nicht gecrawlt wurden, Probleme verursachen können, da sie nie auf Gültigkeit geprüft werden, bevor sie an den Benutzer zurückgegeben werden. In diesem Fall kann die Suchmaschine sogar eine Seite zurückgeben, die nie existiert hat, auf die aber Hyperlinks verweisen. Es ist jedoch möglich, die Ergebnisse zu sortieren, so dass dieses spezielle Problem selten auftritt.

Diese Idee, Ankertexte auf die Seite zu übertragen, auf die sie sich bezieht, wurde im World Wide Web Worm implementiert, vor allem, weil die Suche nach Nicht-Text-Informationen erleichtert und den Suchbereich mit weniger heruntergeladenen Dokumenten erweitert. Brin/Page verwenden die Ankerausbreitung hauptsächlich deshalb, weil der Ankertext dazu beitragen kann, bessere Ergebnisse zu erzielen. Der effiziente Einsatz von Ankertext ist aufgrund der großen Datenmengen, die verarbeitet werden müssen, technisch schwierig. In unserem aktuellen Crawling von 24 Millionen Seiten hatte Google über 259 Millionen Anker, die indiziert wurden.

Andere Features.

Neben PageRank und der Verwendung von Ankertext hat Google noch einige andere Funktionen. Erstens verfügt es über Standortinformationen für alle Treffer und nutzt daher die Nähe bei der Suche ausgiebig. Zweitens verfolgt Google einige visuelle Präsentationsdetails wie die Schriftgröße der Wörter. Wörter in einer größeren oder fetteren Schrift werden höher gewichtet als andere Wörter. Drittens ist vollständiges HTML der Seiten in einem Repository verfügbar.

Weiterführende Arbeiten.

Die Suchforschung im Web hat eine kurze und prägnante Geschichte. Der World Wide Web Worm war eine der ersten Web-Suchmaschinen. Es folgten mehrere andere akademische Suchmaschinen, von denen viele heute kommerzielle Unternehmen sind. Verglichen mit dem Wachstum des Internets und der Bedeutung von Suchmaschinen gibt es nur wenige Dokumente über aktuelle Suchmaschinen. Laut Michael Mauldin „bewachen die verschiedenen Dienste die Details dieser Datenbanken“. Allerdings gab es eine Menge Arbeit über spezifische Funktionen von Suchmaschinen. Besonders gut vertreten sind Arbeiten, die durch Nachbearbeitung der Ergebnisse bestehender kommerzieller Suchmaschinen oder durch die Erstellung kleinerer „individualisierter“ Suchmaschinen zu Ergebnissen führen können. Schließlich gab es eine Menge Forschung über Information Retrieval Systeme, vor allem über gut kontrollierte Sammlungen. In den nächsten beiden Abschnitten diskutieren wir einige Bereiche, in denen diese Forschung weiter vorangetrieben werden kann.

Informationsbeschaffung.

Die Arbeit in Information Retrieval Systemen reicht viele Jahre zurück und ist gut entwickelt. Der größte Teil der Forschung zu Information Retrieval Systemen konzentriert sich jedoch auf kleine, gut kontrollierte, homogene Sammlungen wie z.B. Sammlungen von wissenschaftlichen Arbeiten oder Nachrichten zu einem verwandten Thema. Der wichtigste Maßstab für die Informationsbeschaffung, die Text Retrieval Conference, verwendet eine relativ kleine, gut kontrollierte Sammlung für ihre Benchmarks. Der „Very Large Corpus“ Benchmark beträgt nur 20 GN im Vergleich zu den 147 GB aus Googles Crawling von 24 Millionen Webseiten. Dinge, die auf TREC gut funktionieren, führen oft nicht zu guten Ergebnissen im Web. Beispielsweise versucht das Standard-Vektorraummodell, das Dokument zurückzugeben, das der Abfrage am nächsten kommt, da sowohl Abfrage als auch Dokument Vektoren sind, die durch ihr Wortvorkommen definiert sind. Im Web gibt diese Strategie oft sehr kurze Dokumente zurück, die die Abfrage plus ein paar Worte sind. Zum Beispiel haben Page/Brin gesehen, wie eine große Suchmaschine eine Seite mit nur „Bill Clinton sucks“ und einem Bild aus einer „Bild Clinton“-Abfrage zurückgibt. Einige argumentieren, dass Benutzer im Web genauer angeben sollten, was sie wollen und mehr Wörter zu ihrer Anfrage hinzufügen sollten. Page/Brin sind mit dieser Position vehement nicht einverstanden. Wenn ein Benutzer eine Anfrage wie „Bill Clinton“ stellt, sollte er vernünftige Ergebnisse erzielen, da es eine enorme Menge an qualitativ hochwertigen Informationen zu diesem Thema gibt. Aufgrund solcher Beispiele sind Brin/Page der Meinung, dass die Standard-informationsbeschaffung erweitert werden muss, um effektiv mit dem Web umgehen zu können.

Unterschiede zwischen dem Web und gut kontrollierten Sammlungen.

Das Web ist eine riesige Sammlung völlig unkontrollierter heterogener Dokumente. Dokumente im Web haben extreme Variationen innerhalb der Dokumente und auch in den externen Metainformationen, die verfügbar sein könnten. Zum Beispiel unterscheiden sich Dokumente intern in ihrer Sprache, ihrem Wortschatz, ihrem Typ oder Format und können sogar maschinell erzeugt werden. Andererseits definieren wir externe Metainformationen als Informationen, die über ein Dokument abgeleitet werden können, aber nicht darin enthalten sind. Beispiele für externe Metainformationen sind z.B. Reputation der Quelle, Aktualsierungshäufigkeit, Qualität, Beliebtheit oder Links. Nicht nur die möglichen Quellen für externe Metainformationen sind vielfältig, sondern auch die Dinge, die gemessen werden, variieren in vielen Größenordnungen. Vergleichen Sie zum Beispiel die Nutzungsinformationen einer großen Homepage wie Yahoo, die derzeit jeden Tag Millionen von Seitenaufrufen enthält, mit einem obskuren historischen Artikel, der alle zehn Jahre eine Ansicht erhalten könnte. Natürlich müssen diese beiden Punkte von einer Suchmaschine sehr unterschiedlich behandelt werden.

Ein weitere großer Unterschied zwischen dem Web und traditionellen, gut kontrollierten Sammlungen ist, dass es praktisch keine Kontrolle darüber gibt, was die Leute auf das Web stellen können. Koppeln Sie diese Flexibilität, um alles mit dem enormen Einfluss von Suchmaschinen zu veröffentlichen und Unternehmen, die bewusst Suchmaschinen für den Profit manipulieren, werden zu einem ernsthaften Problem. Dieses Problem, das in herkömmlichen geschlossenen Information Retrieval Systemen nicht gelöst wurde. Interessant ist auch, dass Metadaten-Bemühungen bei Web-Suchmaschinen weitgehend fehlgeschlagen sind, da jeder Text auf der Seite, der nicht direkt für den Benutzer dargestellt wird, missbraucht wird, um Suchmaschinen zu manipulieren. Es gibt sogar zahlreiche Unternehmen, die sich darauf spezialisiert haben, Suchmaschinen gewinnbringend zu manipulieren.

System Anatomie.

Zuerst werden wir die Architektur auf hohem Niveau diskutieren. Dann gibt es einige detaillierte Beschreibungen wichtiger Datenstrukturen. Schließlich werden die wichtigsten Anwendungen wie Crawlen, Indizieren und Suchen eingehend untersucht.

Überblick über die Google Architektur.

In diesem Abschnitt gehen Page/Brin einen Überblick darüber, wie das gesamte System funktioniert. In weiteren Abschnitten werden die in diesem Abschnitt nicht genannten Anwendungen und Datenstrukturen behandelt. Der Großteil von Google ist aus Effizienzgründen in C oder C++ implementiert und kann entweder in Solaris oder Linux ausgeführt werden.

In Google wird das Webcrawing von mehreren verteilten Crawlern durchgeführt. Es gibt einen URL-Server, der Listen von URLs an die Crawler sendet. Die abgerufenen Webseiten werden dann an den Storeserver gesendet. Der Storageserver komprimiert und speichert die Webseiten in einem Repository. Jede Webseite hat eine zugehörige ID-Nummer, die docID genannt wird, die immer dann vergeben wird, wenn eine neue URL aus einer Webseite geparst wird. Die Indizierung erfolgt durch den Indexer und den Sorter. Der Indexer führt eine Reihe von Funktionen aus. Es liest das Repository, entpackt die Dokumente und analysiert diese. Jedes Dokument wird in eine Menge von Wortvorkommen umgewandelt, die als Treffer bezeichnet werden. Die Treffer erfassen das Wort, die Position im Dokument, eine Annäherung der Schriftgröße und die Groß-/Kleinschreibung. Der Indexer verteilt diese Treffer in eine Reihe von „Fässern“ und erzeugt so einen teilweise sortierten Vorwärtsindex. Der Indexer erfüllt eine weitere wichtige Funktion. Es analysiert alle Links in jeder Webseite und speichert wichtige Informationen über sie in einer Ankerdatei. Diese Datei enthält genügend Informationen, um zu bestimmen, woher und wohin jeder Link zeigt und den Text des Links.

Der URLresolver liest die anchors-Datei und wandelt relative URLs in absolute URLs und damit in docIDs um. Er setzt den Ankertext in den Vorwärtsindex, der mit der docID verknüpft ist, auf die der Anker zeigt. Es erzeugt auch eine Datenbank von Links, die Paare von docIDs sind. Die Link-Datenbank wird verwendet, um PageRanks für alle Dokumente zu berechnen.

Der Sorter nimmt die Barrels, die nach docID sortiert sind und sortiert diese nach wordID, um den invertierten Index zu erzeugen. Dies geschieht an Ort und Stelle, so dass nur wenig Platz für diesen Vorgang benötigt wird. Der Sorter erzeugt auch eine Liste von wordIDs und Offsets in den invertierten Index. Ein Programm mit der Bezeichnung DumpLexicon nimmt diese Liste zusammen mit dem vom Indexer erzeugten Lexikon und generiert ein neues Lexikon, das vom Suchenden verwendet wird. Der Sucher wird von einem Webserver betrieben und verwendet das von DumpLexicon erstellte Lexikon zusammen mit dem invertierten Index und den PageRanks zur Beantwortung von Anfragen.

Wichtige Datenstrukturen.

Die Datenstrukturen von Google sind so optimiert, dass eine große Dokumentensammlung mit geringem Aufwand crawlt, indiziert und durchsucht werden kann. Obwohl sich die CPUs und die Bulk-Input-Ausgaberaten im Laufe der Jahre drastisch verbessert haben, benötigt ein Disk-Suchlauf immer noch etwa 10 ms, um abgeschlossen zu werden. Google ist so konzipiert, dass Disk-Suchvorgänge nach Möglichkeit vermieden werden, was einen erheblichen Einfluss auf die Gestaltung der Datenstrukturen hatte.

BigFiles.

BigFiles sind virtuelle Dateien, die sich über mehrere Dateisysteme erstrecken und über 64 Bit Ganzzahlen adressierbar sind. Die Zuordnung zwischen mehreren Dateisystemen erfolgt automatisch. Das BigFiles-Paket übernimmt auch die Zuweisung und Deallokation von Datei-Deskriptoren, da die Betriebssysteme nicht genug für unsere Bedürfnisse bieten. BigFiles unterstützt auch rudimentäre Komprimierungsoptionen.

Repository.

Das Repository enthält das komplette HTML jeder Webseite. Jede Seite wird mit zlib komprimiert. Die Wahl der Kompressionstechnik ist ein Kompromiss zwischen Geschwindigkeit und Kompressionsverhältnis. Wir haben die Geschwindigkeit von zlib gegenüber einer signifikanten Verbesserung der Komprimierung durch bzip gewählt. Die Kompressionsrate von bzip betrug etwa 4 zu 1 auf dem Repository im Vergleich zu zlibs 3 zu 1 Kompression. Im Repository werden die Dokumente nacheinander abgelegt und mit docID, Länge und URL vorangestellt. Das Repository benötigt keine weiteren Datenstrukturen, um darauf zugreifen zu können. Dies hilft bei der Datenkonsistenz und erleichert die Entwicklung. Wir können alle anderen Datenstrukturen nur aus dem Repository und einer Datei, die Crawler-Fehler auflistet, neu aufbauen.

Dokument Index.

Der Dokumentenindex enthält Informationen über jedes Dokument. Es handelt sich um einen ISAM-Index mit fester Breite, zugeordnet nach docID. Die in jedem Eintrag gespeicherten Informationen umfassen den aktuellen Dokumentenstatus, einen Zeiger auf das Repository, eine Dokumentprüfsumme und verschiedene Statistiken. Wenn das Dokument gecrawlt wurde, enthält es auch einen Zeiger auf eine Datei mit variabler Breite mit der Bezeichnung docinfo, die seine URL und seinen Titel enthält. Ansonsten zeigt der Zeiger in die URL-Liste, die nur die URL enthält. Diese Design-Entscheidung wurde durch den Wunsch nach einer relativ kompakten Datenstruktur und der Möglichkeit, einen Datensatz während einer Suche auf einer Festplatte abzurufen, getrieben.

Zusätzlich gibt es eine Datei, die verwendet wird, um URLs in docIDs zu konvertieren. Es ist eine Liste von URL-Prüfsummen mit den entsprechenden docIDs und ist nach Prüfsumme sortiert. Um die docID einer bestimmten URL zu finden, wird die Prüfsumme der URL berechnet und eine binäre Suche in der Prüfsummendatei durchgeführt, um deren docID zu finden. URLs können im Batch in docIDs konvertiert werden, indem mit dieser Datei zusammengeführt wird. Dies ist die Technik, mit der der URL-Resolver URLs in docIDs umwandelt. Dieser Batch-Modus der Aktualisierung ist entscheidend, da wir sonst für jeden Link einen Suchlauf durchführen müssen, der mehr als einen Monat für Googles 332 Millionen Link-Datensatz in Anspruch nehmen würde.

Lexicon.

Das Lexicon hat verschiedene Formen. Eine wichtige Änderung gegenüber früheren Systemen ist, dass das Lexikon zu einem vernünftigen Preis in den Speicher passen kann. In der aktuellen Implementierung können wir das Lexicon auf einer Maschine mit 256 MB Hauptspeicher im Speicher halten. Das aktuelle Lexikon enthält 14 Millionen Wörter. Es ist in zwei Teilen implementiert – eine Liste der Wörter und eine Hash-Tabelle von Zeigern. Für verschiedene Funktionen enthält die Wortliste einige Zusatzinformationen, die den Rahmen dieses Papers sprengen.

Hit Lists.

Eine Trefferliste entspricht einer Liste von Vorkommen eines bestimmten Wortes in einem bestimmten Dokument einschließlich Position, Schriftart und Groß-/Kleinschreibung. Trefferlisten machen den größten Teil des Platzbedarfs sowohl im Forward- als auch um invertierten Index aus. Aus diesem Grund ist es wichtig, sie so effizient wie möglich zu repräsentieren. Wir haben mehrere Alternativen für die Kodierung von Position, Schriftart und Großschreibung in Betracht gezogen – einfache Kodierung und Huffman-Kodierung. Am Ende haben sich Page/Brin für eine handoptimierte Kompaktkodierung entschieden, da sie weitaus weniger Platz als die einfache Kodierung und weitaus weniger Bitmanipulation benötigt als die Huffman-Kodierung.

Unsere kompakte Kodierung verwendet zwei Bytes für jeden Treffer. Es gibt zwei Arten von Treffern: Fancy Hits und Plain Hits. Zu den ausgefallenen Treffern gehören Treffer, die in einer URL, einem Titel, einem Ankertext oder einem Meta-Tag vorkommen. Einfache Treffer beinhalten alles andere. Ein einfacher Treffer besteht aus einem Großbuchstabenbit, Schriftgröße und 12 Bit Wortposition in einem Dokument. Die Schriftgröße wird relativ zum Rest des Dokuments mit drei Bits dargestellt. Ein ausgefallener Treffer besteht aus einem Großbuchstabenbit, der Schriftgröße 7, um anzuzeigen, dass es sich um einen ausgefallenen Treffer handelt, 4 Bits, um den Typ des ausgefallenen Treffers zu kodieren und 8 Bits Position. Für Ankertexte werden die 8 Bits der Position in 4 Bits für die Position im Anker und 4 Bits für einen Hash der docID, in der der Anker vorkommt, aufgeteilt. Dies gibt uns einige begrenzte Phrasensuche, solange es nicht so viele Anker für ein bestimmtes Wort gibt. Wir erwarten, dass die Art und Weise, wie die Anker-Treffer gespeichert werden, aktualisiert wird, um eine höhere Auflösung in den Feldern Position und docIDhash zu ermöglichen. Wir verwenden die Schriftgröße im Verhältnis zum Rest des Dokuments, da Sie bei der Suche nicht die sonst gleichen Dokumente unterschiedlich bewerten wollen, nur weil eines der Dokumente in einer größeren Schriftart vorliegen.

Die Länge einer Trefferliste wird vor den Treffern selbst gespeichert. Um Platz zu sparen, wird die Länge der Trefferliste mit der WortID im Vorwärtsindex und der docID im invertierten Index kombiniert. Dies begrenzt es auf 8 bzw. 5 Bits. Wenn die Länge länger ist, als in so viele Bits passen würde, wird ein Escape-Code in diesen Bits verwendet und die nächsten zwei Bytes enthalten die tatsächliche Länge.

Forward Index.

Der Forward-Index ist eigentlich schon teilweise sortiert. Es wird in mehreren Fässern gelagert. Jedes Fass enthält eine Reihe von WordID`s. Wenn ein Dokument Wörter enthält, die in eine bestimmte Tonne fallen, wird die docID in die Tonne aufgenommen, gefolgt von einer Liste von WordID`s mit Trefferlisten, die diesen Wörtern entsprechen. Dieses Schema erfordert etwas mehr Speicherplatz wegen doppelter docIDs, aber der Unterschied ist sehr gering für eine vernünftige Anzahl von Buckets und spart viel Zeit und Programmieraufwand in der letzten Indizierungsphase, die der Sorter durchführt. Darüber hinaus speichern Page/Brin jede WordID als relative Differenz zu der minimalenWordID, die in den Zylinder fällt, in dem sich die WordID befindet. Auf diese Weise können Brin/Page nur 24 Bit für die WordID`s in den unsortierten Fässern verwenden, wobei 8 Bit für die Länge der Trefferliste übrig bleiben.

Invertierter Index.

Der invertierte Index besteht aus den gleichen Fässern wie der Forward Index, nur dass sie vom Sorter verarbeitet wurden. Für jede gültige wordID enthält das Lexicon einen Zeiger in den Lauf, in den die wordID fällt. Es zeigt auf eine Dokumentenliste von docID`s zusammen mit den entsprechenden Trefferlisten. Diese Dokumentliste stellt alle Vorkommen dieses Wortes in allen Dokumenten dar.

Eine wichtige Frage ist, in welcher Reihenfolge die docID`s in der Dokumentenliste erscheinen sollen. Eine einfache Lösung besteht darin, sie nach docID sortiert abzulegen. Dies ermöglicht ein schnelles Zusammenführen verschiedener Dokumentenlisten für Mehrwortabfragen. Eine weitere Möglichkeit besteht darin, sie sortiert nach dem Vorkommen des Wortes in jedem Dokument zu speichern. Dies macht die Beantwortung von Ein-Wort-Abfragen trivial und macht es wahrscheinlich, dass die Antworten auf Mehrwortabfragen am Anfang stehen. Das Zusammenführen ist jedoch viel schwieriger. Außerdem wird die Entwicklung dadurch erschwert, dass eine Änderung der Ranking-Funktion einen Neuaufbau des Index erfordert. Page/Brin haben einen Kompromiss zwischen diesen Optionen gewählt, indem Sei zwei Sätze von umgekehrten Läufen beibehalten – einen Satz für Trefferlisten, die Titel- und Ankertreffer enthalten und einen anderen Satz für alle Trefferlisten. Auf diese Weise überprüfen wir zuerst den ersten Satz Fässer und wenn es nicht genügend Übereinstimmung in diesen Fässern gibt, prüfen wir die größeren.

Das Web crawlen.

Das Ausführen eines Webcrawlers ist eine anspruchsvolle Aufgabe. Es gibt knifflige Leistungs- und Reliabilitätsprobleme und noch wichtiger, es gibt soziale Probleme. Crawling ist die anfälligste Anwendung, da sie mit Hunderttausenden von Webservern und verschiedenen Nameservern interagiert, die alle außerhalb der Kontrolle des Systems liegen.

Um auf Hunderte von Millionen von Webseiten zu skalieren, verfügt Google über ein schnelles, verteiltes Crawling-System. Ein einziger URL-Server dient einer Reihe von Crawlern als Liste von URLs. Sowohl der URL-Server als auch die Crawler sind in Python implementiert. Jeder Crawler hät etwa 300 Verbindungen gleichzeitig offen. Dies ist notwendig, um Webseiten schnell genug abzurufen. Bei Spitzengeschwindigkeiten kann das System mit vier Crawlern über 100 Webseiten pro Sekunde crawlen. Das sind etwa 600K Daten pro Sekunde. Ein großer Leistungsstress ist die DNS-Suche. Jeder Crawler unterhält einen eigenen DNS-Cache, so dass er vor dem Crawlen jedes Dokuments keinen DNS-Lookup durchführen muss. Jeder der Hunderte von Verbindungen kann sich in verschiedenen Zuständen befinden: DNS suchen, Verbindung zum Host herstellen, Anfrage senden und Antwort empfangen. Diese Faktoren machen den Crawler zu einem komplexen Bestandteil des Systems. Es verwendet asynchrone IO, um Ereignisse zu verwalten und eine Reihe von Warteschlangen, um Seitenabrufe von Status zu Status zu verschieben.

Es stellt sich heraus, dass der Betrieb eines Crawlers, der eine Verbindung zu mehr als einer halben Million Servern herstellt und zig Millionen von Log-Einträgen erzeugt, eine beträchtliche Anzahl von E-Mails und Telefonaten erzeugt. Wegen der großen Anzahl von Leuten, die online gehen, gibt es immer diejenigen, die nicht wissen, was ein Crawler ist, denn dies ist der erste, den Sie gesehen haben. Fast täglich erhalten Brin/Page E-Mails wie „Wow, du hast dir viele Seiten von meiner Website angesehen. Wie hat es dir gefallen? Es gibt auch einige Leute, die nicht über das Robots-Anschlussprotokoll Bescheid wissen und denken, dass ihre Seiten durch eine Aussage wie „Diese Seite ist urheberrechtlich geschützt und sollte nicht indiziert werden“ geschützt werden sollte, was für Webcrawler natürlich schwer zu verstehen ist. Auch wegen der enormen Datenmenge werden unerwartete Dinge passieren. Zum Beispiel hat unser System versucht, ein Online-Spiel zu crawlen. Dies führte zu vielen Spamnachrichten in der Mitte des Spiels. Es stellte sich heraus, dass dies ein leicht zu behebendes Problem war. Aber dieses Problem trat erst auf, als Brin/Page zig Millionen Seiten heruntergeladen hatten. Aufgrund der immensen Unterschiede bei Webseiten und Servern ist es praktisch unmöglich, einen Crawler zu testen, ohne ihn auf einen großen Teil des Internets laufen zu lassen. Ausnahmslos gibt es Hunderte von obskuren Programmen, die nur auf einer Seite des gesamten Webs auftreten können und den Crawler zum Absturz bringen oder schlimmer noch, unvorhersehbares oder falsches Verhalten verursachen. Systeme, die auf große Teile des Internets zugreifen, müssen sehr robust und sorgfältig getestet sein. Da große komplexe Systeme wie Crawler immer Probleme verursachen, müssen erhebliche Ressourcen für das Lesen der E-Mail und die Lösung dieser Probleme aufgewendet werden.

Das Web indexieren.

  • Parsen – Jeder Parser, der für das gesamte Web ausgelegt ist, muss mit einer Vielzahl möglicher Fehler umgehen. Diese reichen von Tippfehlern in HTML-Tags bis hin zu Kilobytes von Nullen in der Mitte eines Tags, Nicht ASCII-Zeichen, HTML-Tags, die Hunderte tief verschachtelt sind und einer Vielzahl anderer Fehler, die die Phantasie eines jeden herausfordern, ebenso kreative zu entwickeln. Für maximale Geschwindigkeit verwenden Brin/Page nicht YACC, um einen CFG-Parser zu generieren, sondern Flex, um einen lexikalischen Analysator zu generieren, den Brin/Page mit einem eigenen Stack ausstatten. Die Entwicklung dieses Parsers, der mit einer vernünftigen Geschwindigkeit läuft und sehr robust ist, war mit viel Arbeit verbunden.
  • Indizierung von Dokumenten in Fässern – Nachdem jedes Dokument analysiert wurde, wird es in eine Anzahl von Fässern kodiert. Jedes Word wird mit Hilfe einer In-Memory-Hash-Tabelle in eine WordID umgewandelt. Neuzugänge in der Lexikon-Hash-Tabelle werden in einer Datei protokolliert. Sobald die Wörter in WordID`s umgewandelt sind, werden ihre Vorkommen im aktuellen Dokument in Trefferlisten übersetzt und in die vorderen Fässer geschrieben. Die Hauptschwierigkeit bei der Parallelisierung der Indizierungsphase besteht darin, dass das Lexikon geteilt werden muss. Anstatt das Lexikon zu teilen, haben Brin/Page ein Protokoll aller zusätzlichen Wörter geschrieben, die nicht in einem Basislexikon waren, das Brin/Page auf 14 Millionen Wörter festgelegt haben. Auf diese Weise können mehrere Indexer parallel laufen und dann kann die kleine Logdatei mit zusätzlichen Wörtern von einem finalen Indexer verarbeitet werden.
  • Sortierung – Um den invertierten Index zu erzeugen, nimmt der Sorter jedes der vorderen Fässer und sortiert es nach wordID, um ein invertiertes Fass für Titel- und Ankertreffer und ein invertiertes Faß mit Volltext zu erzeugen. Dieser Vorgang erfolgt für jeweils ein Fass nach dem anderen, so dass nur wenig Zwischenlagerung erforderlich ist. Außerdem parallelisieren wir die Sortierphase, um so viele Maschinen wie möglich einzusetzen, indem wir einfach mehrere Sortieranlagen betreiben, die verschiedene Eimer gleichzeitig verarbeiten können. Da die Fässer nicht in den Hauptspeicher passen, unterteilt der Sorter sie weiter in Körbe, die auf Basis von wordID und docID in den Speicher passen. Dann lädt der Sortierer jeden Korb in den Speicher, sortiert ihn und schreibt seinen Inhalt in den kurzen invertierten und den voll invertierten Lauf.

Suchen.

Das Ziel der Suche ist es, qualitativ hochwertige Suchergebnisse effizient zu liefern. Viele der großen kommerziellen Suchmaschinen schienen große Fortschritte in Sachen Effizienz gemacht zu haben. Deshalb haben Brin/Page sich in ihrer Forschung mehr auf die Qualität der Suche konzentriert, obwohl Sie glauben, dass ihre Lösungen mit etwas mehr Aufwand auf kommerzielle Volumina skalierbar sind. Die Auswertung der Google-Abfrage finden Sie unten:

  1. Analysieren Sie die Abfrage.
  2. Wörter in wordIDs umwandeln.
  3. Suchen Sie für jedes Wort an den Anfang der Dokumentliste im kurzen Lauf.
  4. Durchsuchen Sie die Dokumentenlisten, bis ein Dokument vorhanden ist, das allen Suchbegriffen entspricht.
  5. Berechnen Sie den Rang dieses Dokuments für die Abfrage.
  6. Wenn wir uns in den kurzen Fässern und am Ende einer Dokumentenliste befinden, suchen Sie den Anfang der Dokumentenliste im vollen Faß für jedes Wort und gehen Sie zu Schritt 4.
  7. Wenn wir uns nicht am Ende einer Dokumentenliste befinden, gehen Sie zu Schritt 4.

Sortieren Sie die Dokumente, die nach Rang sortiert wurden und geben Sie das oberste K zurück.

Um die Antwortzeit zu begrenzen, geht der Sucher automatisch zu Schritt 8 über, sobald eine bestimmte Anzahl passender Dokumente gefunden wurde. Dies bedeutet, dass es möglich ist, dass suboptimale Ergebnisse zurückgegeben werden. Brin/Page untersuchen derzeit andere Wege, um dieses Problem zu lösen. In der Vergangenheit haben Brin/Page die Treffer nach PageRank sortiert, was die Situation zu verbessern schien.

Das Ranking-System.

Google verwaltet viel mehr Informationen über Web-Dokumente als typische Suchmaschinen. Jede Trefferliste enthält Informationen zu Position, Schriftart und Großschreibung. Zusätzlich berücksichtigen Page/Brin Treffer aus dem Ankertext und dem PageRank des Dokuments. All diese Informationen zu einem Rang zusammenzufassen ist schwierig. Page/Brin haben ihre Ranking-Funktion so gestaltet, dass kein bestimmter Faktor zu viel Einfluss haben kann. Zuerst bertrachten Sie den einfachsten Fall – eine einzelne Wortabfrage. Um ein Dokument mit einer einzelnen Wortabfrage zu bewerten, betrachtet Google die Trefferliste dieses Dokuments für dieses Wort. Google betrachtet jeden Treffer als einen von mehreren verschiedenen Typen (Titel, Anker, URL, Klartext große Schriftart, Klartext kleine Schriftart …) von denen jeder seine eigene Schriftart hat. Die Typ-Gewichte bilden einen nach Typ indizierten Vektor. Google zählt die Anzahl der Treffer jedes Typs in der Trefferliste. Dann wird jede Zählung in ein Zählgewicht umgerechnet. Zählgewichte steigen zunächst linear mit den Zählungen an, verjüngen sich aber schnell, so dass mehr als eine bestimmte Anzahl nicht hilft. Wir nehmen das Punktprodukt aus dem Vektor der Zählgewichte mit dem Vektor der Typgewichte, um einen IR-Score für das Dokument zu berechnen. Schließlich wird der IR-Score mit dem PageRank kombiniert, um dem Dokument einen endgültigen Rang zu geben.

Bei einer Mehrwortsuche ist die Situation komplizierter. Nun müssen mehrere Trefferlisten gleichzeitig durchsucht werden, so dass Treffer, die in einem Dokument eng beieinander liegen, höher gewichtet werden als Treffer, die weit auseinander liegen. Die Treffer aus den mehreren Trefferlisten werden so abgeglichen, dass benachbarte Treffer miteinander abgeglichen werden. Für jede Textmenge wird eine Nähe berechnet. Die Nähe hängt davon ab, wie weit die Treffer im Dokument entfernt sind, wird aber in 10 verschiedene „Bins“ eingeteilt, die von einer Phrasenübereinstimmung bis zu „nicht einmal nahe“ reichen. Zählungen werden nicht nur für jede Art von Treffer, sondern auch für jede Art und Nähe berechnet. Jedes Typ- und Näherungspaar hat ein Typ-Prox-Gewicht. Die Zählungen werden in Zählgewichte umgerechnet und Brin/Page nehmen das Punktprodukt aus den Zählgewichten und den Typ-Prox-Gewichten, um einen IR-Score zu berechnen. Alle diese Zahlen und Matrizen können mit den Suchergebnissen in einem speziellen Debug-Modus angezeigt werden. Diese Anzeigen waren sehr hilfreich bei der Entwicklung des Ranking-Systems.

Feedback.

Die Ranking- Funktion hat viele Parameter wir die Typ-Gewichte und die Typ-Prox-Gewichte. Die richtigen Werte für diese Parameter herauszufinden, ist so etwas wie eine schwarze Kunst. Um dies zu erreichen, haben Brin/Page einen Benutzer-Feedback-Mechanismus in der Suchmaschine. Ein vertrauenswürdiger Benutzer kann optional alle zurückgegebenen Ergebnisse auswerten. Diese Rückmeldung wird gespeichert. Wenn wir dann die Ranking-Funktion ändern, können wir die Auswirkungen dieser Änderung auf alle früheren Suchvorgänge sehen, die geordnet wurden. Dies gibt uns eine Vorstellung davon, wie sich eine Änderung der Ranking-Funktion auf die Suchergebnisse auswirkt.

Ergebnisse und Leistungen.

Das wichtigste Maß einer Suchmaschine ist die Qualität ihrer Suchergebnisse. Während eine vollständige Nutzerbewertung den Rahmen dieses Papers sprengt, hat Brin/Page`s eigene Erfahrung mit Google gezeigt, dass sie bei den meisten Suchanfragen bessere Ergebnisse liefert als die großen kommerziellen Suchmaschinen.

Wenn man einen Suchbegriff bei Google wie z.B. „Trump“ eingibt, zeigen sich einige Funktionen von Google. Diese Ergebnisse werden nach Server geclustert. Dies hilft bei der Durchsicht von Ergebnismengen erheblich. Eine Reihe von Ergebnissen stammen von der whitehouse-gov-Domain, was man auch von einer derartigen Suche erwarten kann. Derzeit liefern die meisten großen kommerziellen Suchmaschinen keine Ergebnisse von whitehouse.gov, geschweige denn die richtigen. Beachten Sie, dass es keinen Titel für das erste Ergebnis gibt. Das liegt daran, dass es nicht gekrabbelt wurde. Stattdessen verließ sich Google auf Ankertext, um festzustellen, dass dies eine gute Antwort auf die Anfrage war. Ebenso ist das fünfte Ergebnis eine E-Mail-Adresse, die natürlich nicht crawlbar ist. Es ist auch als ein Ergebnis vom Ankertext zu werten.

Alle Ergebnisse sind von relativ hoher Qualität und bei der letzten Überprüfung waren keine Links defekt. Dies liegt vor allem daran, dass sie alle einen hohen PageRank haben. Die PageRanks sind die Prozentangaben in rot zusammen mit den Balkendiagrammen. Schließlich gibt es keine Ergebnisse über Donald Trump oder über einen anderen Trump als Donald. Denn Brin/Page legen großen Wert auf die Nähe der Wordvorkommen. Ein echter Test der Qualität einer Suchmaschine würde natürlich eine umfangreiche Nutzerstudie ohne Ergebnisanalyse erfordern, für die wir hier keinen Platz haben. Stattdessen laden Bring/Page den Leser ein, Google selbst über http://google.standford.edu auszuprobieren.

Speicheranforderungen.

Abgesehen von der Suchqualität ist Google so konzipiert, dass es kostengünstig an die Größe des Internets angepasst werden kann, wenn es wächst. Ein Aspekt dabei ist die effiziente Nutzung des Speichers. Durch die Komprimierung beträgt die Gesamtgröße des Repositorys etwa 53 GB, etwas mehr als ein Drittel der gesamten Daten, die es speichert. Dies macht das Repository bei den aktuellen Preisen zu einer relativ günstigen Quelle für nützliche Daten. Noch wichtiger ist, dass die Summe aller von der Suchmaschine verwendeten Daten einen vergleichbaren Speicherplatz von ca. 55 GB benötigt. Außerdem können die meisten Anfragen nur mit dem kurzen invertierten Index beantwortet werden. Mit einer besseren Kodierung und Komprimierung des Dokumentenindex kann eine hochwertige Web-Suchmaschine auf ein 7 GB-Laufwerk eines neuen PCs passen.

Systemleistung.

Für eine Suchmaschine ist es wichtig, effizient zu crawlen und zu indizieren. So können Informationen auf dem neuesten Stand gehalten und größere Änderungen am System relativ schnell getestet werden. Für Google sind die Hauptoperationen Crawling, Indexing und Sorting. Es ist schwierig zu messen, wie lange das Crawlen insgesamt dauerte, weil die Speicher voll waren, Nameserver abstürzten oder anderen andere Probleme entstanden, die das System zum Stillstand brachten. Insgesamt dauerte der Download der 26 Millionen Seiten etwa 9 Tage. Sobald das System jedoch reibungslos lief, ging es deutlich schneller und lud die letzten 11 Millionen Seiten in nur 63 Sekunden herunter, durchschnittlich etwas mehr als 4 Millionen Seiten pro Tag oder 48,5 Seiten pro Sekunde. Brin/Page haben den Indexer und den Crawler gleichtzeitig ausgeführt. Der Indexer lief einfach schneller als die Crawler. Das liegt vor allem daran, dass Brin/Page gerade genug Zeit damit verbracht haben, den Indexer so zu optimieren, dass er nicht zum Flaschenhals wird. Diese Optimierungen umfassten Massenaktualisierungen des Dokumentenindex und die Platzierung kritischer Datenstrukturen auf der lokalen Festplatte. Der Indexer läuft mit etwa 54 Seiten pro Sekunde. Sorter können komplett parallel betrieben werden, mit 4 Maschinen dauerte der gesamte Sortierprozess ca. 24 Stunden.

Suchleistung.

Die Verbesserung der Such-Performance stand bisher nicht im Vordergrund von Brin und Page`s Forschung. Die aktuelle Version von Google beantwortet die meisten Anfragen in 1 bis 10 Sekunden. Diese Zeitb wird meist von Disk IO über NFS dominiert. Darüber hinaus hat Google keine Optimierungen wie Query-Caching, Subindizes zu allgemeinen Begriffen und andere allgemeine Optimierungen. Brin/Page beabsichtigen, Google durch Distribution und Hardware, Software- und Algorithmenverbesserungen erheblich zu beschleunigen. Unser Ziel ist es, mehrere hundert Anfragen pro Sekunde bearbeiten zu können.

Schlußfolgerungen.

Google ist eine skalierbare Suchmaschine. Das primäre Ziel ist es, qualitativ hochwertige Suchergebnisse über ein schnell wachsendes World Wide Web bereitzustellen. Google verwendet eine Reihe von Techniken zur Verbesserung der Suchqualität, einschließlich PageRank, Ankertext und Proximity-Informationen. Darüber hinaus ist Google eine komplette Architektur, um Webseiten zu sammeln, zu indexieren und Suchanfragen über sie durchzuführen.

Zukünftige Arbeit.

Eine große Web-Suchmaschine ist ein komplexes System und es bleibt noch viel zu tun. Brin/Page`s unmittelbaren Ziele sind die Verbesserung der Sucheffizienz und die Skalierung auf ca. 100 Millionen Webseiten. Einige einfache Effizienzverbesserungen sind das Abfrage-Caching, die intelligente Speicher-Allokation und Subindizes. Ein weiterer Bereich, der viel Forschung erfordert, sind Updates. Page/Brin benötigen intelligente Algorithmen, um zu entscheiden, welche alten Webseiten neu gecrawlt une welche neuen gecrawlt werden sollen. Ein vielversprechendes Forschungsgebiet ist die Verwendung von Proxy-Caches zum Aufbau von Suchdatenbanken, da diese nachfrageorientiert sind. Brin/Page planen, einfache Funktionen hinzuzufügen, die von kommerziellen Suchmaschinen wie boolesche Operatoren, Negation und Stemming unterstützt werden. Andere Funktionen wie Relevanz-Feedback und Clustering werden jedoch gerade erst erforscht. Brin/Page planen auch die Unterstützung des Benutzerkontextes und die Zusammenfassung der Ergebnisse. Brin/Page arbeiten auch daran, die Verwendung von Linkstruktur und -text zu erweitern. Einfache Experimente zeigen, dass PageRank personalisiert werden kann, indem das Gewicht der Homepage oder der Lesezeichen eines Benutzers erhöht wird. Was den Linktext betrifft, so experimentieren Brin/Page mit der Verwendung von Text, der Links umgibt, zusätzlich zum Linktext selbst. Eine Web-Suchmaschine ist eine sehr reichhaltige Umgebung für Forschungsideen. Brin/Page haben viel zubviele, um sie hier aufzulisten, so dass sie nicht erwarten, dass diese Sektion in naher Zukunft viel kürzer wird.

Qualitativ hochwertige Suche.

Das größte Problem, mit dem die Nutzer von Web-Suchmaschinen heute konfrontriert sind, ist die Qualität der Ergebnisse, die sie zurückhalten. Während die Ergebnisse oft amüsant sind und den Horizont der Nutzer erweitern, sind sie oft frustrierend und verbrauchen wertvolle Zeit. Das beste Ergebnis für eine Suche nach „Donald Trump“ auf einer der beliebtesten kommerziellen Suchmaschinen war beispielsweise die Trump-Wahl. Google wurde entwickelt, um eine qualitativ hochwertigere Suche zu ermöglichen, so dass das Web weiterhin schnell wächst und Informationen leicht gefunden werden können. Um dies zu erreichen, verwendet Google stark hypertextuelle Informationen, die aus Linkstruktur und Link (Anker) Text bestehen. Google verwendet auch Näherungs- und Schriftinformationen. Während die Bewertung einer Suchmaschine schwierig ist, haben Brin/Page subjektiv festgestelltm dass Google bessere Suchergebnisse liefert als kommerzielle Suchmaschinen. Die Analyse der Linkstruktur über PageRank ermöglicht es Google, die Qualität von Webseiten zu bewerten. Die Verwendung von Linktext als Beschreibung dessen, worauf der Link verweist, hilft der Suchmaschine, relevante Ergebnisse zu erhalten. Schließlich trägt die Verwendung von Proximity-Informationen dazu bei, die Relevanz für viele Anfragen zu erhöhen.

Skalierbare Architektur.

Abgesehen von der Qualität der Suche ist Google skalierbar. Es muss sowohl räumlich als auch zeitlich effizient sein und konstante Faktoren sind sehr wichtig im Umgang mit dem gesamten Web. Bei der Implementierung von Google haben Brin/Page Engpässe bei CPU, Speicherzugriff und -kapazität, Diskdurchsatz, -kapazität und -suche sowie Netzwerk-IO gesehen. Google hat sich entwickelt, um eine Reihe dieser Engpässe bei verschiedenen Operationen ui überwinden. Die wichtigsten Datenstrukturen von Google nutzen den verfügbaren Speicherplatz effizient. Darüber hinaus sind die Crawling-, Indexierungs- und Sortieroperationen effizient genug, um in weniger als einer Woche einen Index für einen wesentlichen Teil des Webs zu erstellen – 24 Millionen Seiten. Brin/Page erwarten, dass Sie in weniger als einem Monat einen Index von 100 Millionen Seiten aufbauen können.

Ein Recherche-Tool.

Google ist nicht nur eine qualitativ hochwertige Suchmaschine, sondern auch ein Recherche-Tool. Die von Google gesammelten Daten haben bereits zu vielen anderen Vorträgen geführt, die auf Konferenzen eingereicht wurden. Jüngste Forschungen haben eine Reihe von Einschränkungen bei der Beantwortung von Anfragen über das Web ergeben, ohne dass das Web lokal verfügbar ist. Dies bedeutet, dass Google nicht nur ein wertvolles, sonder auch ein notwendiges Werkzeug für eine Vielzahl von Anwendungen ist. Brin/Page hoffen, dass Google eine Ressource für Sucher und Forscher auf der ganzen Welt sein wird und die nächste Generation der Suchmaschinentechnologie anregen wird.

Mittlerweise wurde Google immer weiterentwickelt und ist heute die größte Suchmaschine der Welt. Alle SEOs sollten sich immer vor Augen halten, was der ursprüngliche Gedanke hinter Google war. Es geht um die Ausgabe von möglichst qualitativ hochwertigen Suchergebnissen. Dieser Tatsache sollten sich alle SEOs bewusst sein.