De anatomie van een zoekmachine
De anatomie van een grootschalige hypertextual Web Search Engine
Abstract
In dit artikel presenteren we Google, een prototype van een grootschalige zoekmachine die veel gebruik maakt van de structuur die in hypertekst aanwezig is. Google is ontworpen om het web efficiënt te crawlen en te indexeren en veel bevredigendere zoekresultaten te produceren dan bestaande systemen. Het prototype met een volledige tekst- en hyperlinkdatabase van minstens 24 miljoen pagina's is beschikbaar op http://google.stanford.edu/
Het engineeren van een zoekmachine is een uitdagende taak. Zoekmachines index tientallen tot honderden miljoenen webpagina's met een vergelijkbaar aantal verschillende voorwaarden. Ze beantwoorden elke dag tientallen miljoenen vragen. Ondanks het belang van grootschalige zoekmachines op het web, is er heel weinig wetenschappelijk onderzoek naar gedaan. Bovendien, als gevolg van de snelle vooruitgang in technologie en webproliferatie, is het tegenwoordig heel anders om een webzoekmachine te maken dan drie jaar geleden. Dit artikel bevat een uitgebreide beschrijving van onze grootschalige webzoekmachine, de eerste tot dusverre gedetailleerde openbare beschrijving die we tot nu toe kennen.
Afgezien van de problemen van het schalen van traditionele zoektechnieken tot gegevens van deze omvang, zijn er nieuwe technische uitdagingen bij het gebruik van de aanvullende informatie die aanwezig is in hypertext om betere zoekresultaten te produceren. Dit artikel gaat in op deze vraag hoe een praktisch grootschalig systeem kan worden gebouwd dat de aanvullende informatie die in hypertekst aanwezig is, kan exploiteren. We kijken ook naar het probleem hoe effectief om te gaan met ongecontroleerde hypertext-collecties, waar iedereen alles kan publiceren wat ze willen.Trefwoorden : World Wide Web, zoekmachines, Information Retrieval, PageRank, Google
1. Inleiding
(Opmerking: er zijn twee versies van dit papier - een langere volledige versie en een kortere gedrukte versie.De volledige versie is beschikbaar op het web en de conferentie-cd-rom.)Het web creëert nieuwe uitdagingen voor het ophalen van informatie. De hoeveelheid informatie op het web groeit snel, evenals het aantal nieuwe gebruikers dat onervaren is in de kunst van webonderzoek. Mensen surfen waarschijnlijk op het web met behulp van de linkgrafiek, vaak beginnend met menselijke indices van hoge kwaliteit zoals Yahoo!of met zoekmachines. Menselijk onderhouden lijsten behandelen populaire onderwerpen effectief, maar zijn subjectief, duur om te bouwen en te onderhouden, traag te verbeteren en kunnen niet alle esoterische onderwerpen dekken. Geautomatiseerde zoekmachines die afhankelijk zijn van keyword-matching retourneren meestal te veel overeenkomsten van lage kwaliteit. Om de zaken nog erger te maken, proberen sommige adverteerders de aandacht van mensen te trekken door maatregelen te nemen die bedoeld zijn om geautomatiseerde zoekmachines te misleiden. We hebben een grootschalige zoekmachine gebouwd die veel van de problemen van bestaande systemen aanpakt. Het maakt vooral veel gebruik van de extra structuur die aanwezig is in hypertekst om zoekresultaten van veel hogere kwaliteit te bieden. We kozen onze systeemnaam, Google, omdat het een gebruikelijke spelling van googol of 10 100 is en goed past bij ons doel om zeer grootschalige zoekmachines te bouwen.
1.1 Web Search Engines - Schaalvergroting: 1994 - 2000
Zoekmachine-technologie moest drastisch opschalen om de groei van het web bij te houden. In 1994 had een van de eerste internetzoekmachines, de World Wide Web Worm (WWWW) [McBryan 94] , een index van 110.000 webpagina's en webtoegankelijke documenten. Vanaf november 1997 claimen de topzoekers een index van 2 miljoen (WebCrawler) tot 100 miljoen webdocumenten (van Search Engine Watch). Het is te voorzien dat tegen het jaar 2000 een uitgebreide index van het web meer dan een miljard documenten zal bevatten. Tegelijkertijd is het aantal zoekopdrachten dat door zoekmachines wordt afgehandeld ook ongelooflijk gegroeid. In maart en april 1994 ontving de World Wide Web Worm gemiddeld ongeveer 1500 zoekopdrachten per dag. In november 1997 beweerde Altavista dat het ongeveer 20 miljoen zoekopdrachten per dag afhandelde. Met het toenemende aantal gebruikers op het web en geautomatiseerde systemen die zoekmachines bevragen, is het waarschijnlijk dat topzoekmachines tegen het jaar 2000 honderden miljoenen zoekopdrachten per dag afhandelen. Het doel van ons systeem is veel van de problemen, zowel in kwaliteit als schaalbaarheid, geïntroduceerd door zoekmachine-technologie te schalen naar dergelijke buitengewone aantallen.1.2. Google: Scaling met het web
Het creëren van een zoekmachine die zelfs schalen naar het web van vandaag presenteert vele uitdagingen. Snelle crawltechnologie is nodig om de webdocumenten te verzamelen en up-to-date te houden. Opslagruimte moet efficiënt worden gebruikt om indices en, eventueel, de documenten zelf op te slaan. Het indexeringssysteem moet honderden gigabytes aan gegevens efficiënt verwerken. Zoekopdrachten moeten snel worden afgehandeld, met een snelheid van honderden tot duizenden per seconde.Deze taken worden steeds moeilijker naarmate het web groeit. De hardwareprestaties en kosten zijn echter drastisch verbeterd om de moeilijkheid gedeeltelijk te compenseren. Er zijn echter enkele opmerkelijke uitzonderingen op deze vooruitgang, zoals zoektijd naar schijven en robuustheid van het besturingssysteem. Bij het ontwerpen van Google hebben we zowel rekening gehouden met de groeisnelheid van het web als met technologische veranderingen. Google is ontworpen om goed te schalen naar extreem grote gegevenssets. Het maakt efficiënt gebruik van opslagruimte om de index op te slaan. De datastructuren zijn geoptimaliseerd voor snelle en efficiënte toegang (zie paragraaf 4.2 ). Verder verwachten we dat de kosten voor het indexeren en opslaan van tekst of HTML uiteindelijk zullen afnemen in verhouding tot het bedrag dat beschikbaar zal zijn (zie bijlage B)). Dit resulteert in gunstige schalingseigenschappen voor gecentraliseerde systemen zoals Google.
1.3 Ontwerpdoelen
1.3.1 Verbeterde zoekkwaliteit
Ons belangrijkste doel is om de kwaliteit van webzoekmachines te verbeteren. In 1994 geloofden sommige mensen dat een complete zoekindex het mogelijk zou maken om alles gemakkelijk te vinden. Volgens Best of the Web 1994 - Navigators, "De beste navigatiedienst zou het gemakkelijk moeten maken om bijna alles op het web te vinden (nadat alle gegevens zijn ingevoerd)." Het web van 1997 is echter heel anders. Iedereen die onlangs een zoekmachine heeft gebruikt, kan gemakkelijk getuigen dat de volledigheid van de index niet de enige factor is in de kwaliteit van zoekresultaten. "Ongewenste resultaten" verwijderen vaak de resultaten waar een gebruiker in geïnteresseerd is. Eigenlijk is er vanaf november 1997 slechts één van de vier beste commerciële zoekmachines (retourneert zijn eigen zoekpagina als antwoord op zijn naam in de top tien) resultaten). Een van de hoofdoorzaken van dit probleem is dat het aantal documenten in de indexen in veel ordes van grootte is toegenomen, maar dat de gebruiker niet in staat is om naar documenten te kijken. Mensen zijn nog steeds alleen bereid om naar de eerste paar tientallen resultaten te kijken. Daarom hebben we, als de verzamelgrootte groter wordt, instrumenten nodig met een zeer hoge nauwkeurigheid (aantal relevante documenten geretourneerd, bijvoorbeeld in de top tientallen resultaten). We willen inderdaad dat onze notie van 'relevant' alleen de allerbeste documenten bevat, aangezien er mogelijk tienduizenden lichtelijk relevante documenten zijn. Deze zeer hoge precisie is belangrijk, zelfs ten koste van recall (het totale aantal relevante documenten dat het systeem kan retourneren). Er is vrij recent optimisme dat het gebruik van meer hypertextuele informatie kan helpen bij het verbeteren van zoek- en andere toepassingen [ om alleen de allerbeste documenten op te nemen, omdat er mogelijk tienduizenden licht relevante documenten zijn. Deze zeer hoge precisie is belangrijk, zelfs ten koste van recall (het totale aantal relevante documenten dat het systeem kan retourneren). Er is vrij recent optimisme dat het gebruik van meer hypertextuele informatie kan helpen bij het verbeteren van zoek- en andere toepassingen [ om alleen de allerbeste documenten op te nemen, omdat er mogelijk tienduizenden licht relevante documenten zijn. Deze zeer hoge precisie is belangrijk, zelfs ten koste van recall (het totale aantal relevante documenten dat het systeem kan retourneren). Er is vrij recent optimisme dat het gebruik van meer hypertextuele informatie kan helpen bij het verbeteren van zoek- en andere toepassingen [Marchiori 97 ] [ Spertus 97 ] [ Weiss 96 ] [ Kleinberg 98 ]. In het bijzonder, linkstructuur [ Pagina 98 ] en linktekst bieden veel informatie voor het maken van relevantie oordelen en kwaliteit filtering. Google maakt gebruik van zowel linkstructuur als ankertekst (zie secties 2.1 en 2.2 ).1.3.2 Academisch onderzoek van zoekmachines
Afgezien van enorme groei, is het internet ook steeds commerciëler geworden in de loop van de tijd. In 1993 was 1,5% van de webservers op .com-domeinen. Dit aantal groeide in 1997 tot meer dan 60%. Tegelijkertijd zijn zoekmachines gemigreerd van het academische domein naar de commercial. Tot nu toe is de meeste ontwikkeling van zoekmachines doorgegaan bij bedrijven met weinig technische details. Dit zorgt ervoor dat zoekmachine-technologie grotendeels een zwarte kunst blijft en reclame-gericht is (zie appendix A ). Met Google hebben we een sterk doel om meer ontwikkeling en begrip in de academische wereld te duwen.Een ander belangrijk ontwerpdoel was om systemen te bouwen die redelijk aantal mensen daadwerkelijk kunnen gebruiken. Het gebruik was belangrijk voor ons, omdat we denken dat een van de meest interessante onderzoeken erin bestaat gebruik te maken van de enorme hoeveelheid gebruiksgegevens die beschikbaar is via moderne websystemen. Er worden bijvoorbeeld dagelijks tientallen miljoenen zoekopdrachten uitgevoerd. Het is echter erg moeilijk om deze gegevens te krijgen, voornamelijk omdat het commercieel waardevol wordt geacht.
Ons uiteindelijke ontwerpdoel was om een architectuur te bouwen die nieuwe onderzoeksactiviteiten op grote webgegevens kan ondersteunen. Om nieuwe onderzoeksdoelen te ondersteunen, slaat Google alle feitelijke documenten op die het in gecomprimeerde vorm crawlt. Een van onze belangrijkste doelen bij het ontwerpen van Google was om een omgeving te creëren waarin andere onderzoekers snel kunnen komen, grote delen van het web kunnen verwerken en interessante resultaten kunnen produceren die anders moeilijk te produceren waren. In de korte tijd dat het systeem is opgestart, zijn er al verschillende papieren met behulp van door Google gegenereerde databases en vele andere zijn onderweg. Een ander doel dat we hebben is om een Spacelab-achtige omgeving te creëren waarin onderzoekers of zelfs studenten interessante experimenten kunnen voorstellen en uitvoeren op onze grootschalige webgegevens.
2. Systeemfuncties
De Google-zoekmachine heeft twee belangrijke functies die helpen bij het produceren van nauwkeurige resultaten. Ten eerste maakt het gebruik van de linkstructuur van het web om een kwaliteitsbeoordeling voor elke webpagina te berekenen. Deze rangschikking wordt de PageRank genoemd en wordt in detail beschreven in [Pagina 98]. Ten tweede gebruikt Google een link om de zoekresultaten te verbeteren.2.1 PageRank: Bestelling naar het web brengen
De citatie (link) grafiek van het web is een belangrijke bron die grotendeels ongebruikt is gebleven in bestaande webzoekmachines. We hebben kaarten gemaakt met maar liefst 518 miljoen van deze hyperlinks, een belangrijk voorbeeld van het totaal. Deze kaarten maken een snelle berekening van de 'PageRank' van een webpagina mogelijk, een objectieve maatstaf voor het belang van citaten die goed overeenkomt met het subjectieve idee van belang van mensen. Vanwege deze correspondentie is PageRank een uitstekende manier om de resultaten van zoekopdrachten op het web met zoekwoorden te prioriteren. Voor de meeste populaire onderwerpen presteert een eenvoudige zoekactie naar tekst die beperkt is tot titels van webpagina's bewonderenswaardig wanneer PageRank de resultaten prioriteert (demo beschikbaar op google.stanford.edu ). Voor het type fulltext-zoekopdrachten in het hoofdsysteem van Google helpt PageRank ook veel.2.1.1 Beschrijving van PageRank-berekening
Academische citatie literatuur is op het web toegepast, grotendeels door citaties of backlinks naar een gegeven pagina te tellen. Dit geeft enige benadering van het belang of de kwaliteit van een pagina. PageRank breidt dit idee uit door links van alle pagina's gelijk te tellen en door te normaliseren op basis van het aantal links op een pagina. PageRank is als volgt gedefinieerd:We gaan ervan uit dat pagina A pagina's T1 ... Tn heeft die erop wijzen (dwz citaten zijn). De parameter d is een dempingsfactor die kan worden ingesteld tussen 0 en 1. Gewoonlijk stellen we d in op 0,85. Er zijn meer details over d in de volgende sectie. C (A) wordt ook gedefinieerd als het aantal links dat van pagina A uitgaat. De PageRank van een pagina A wordt als volgt gegeven:PageRank of PR (A) kan worden berekend met behulp van een eenvoudig iteratief algoritme en komt overeen met de belangrijkste eigenvector van de genormaliseerde koppelingsmatrix van het web. Ook kan een PageRank voor 26 miljoen webpagina's binnen een paar uur worden berekend op een werkstation van gemiddelde grootte. Er zijn veel andere details die buiten het bestek van dit document vallen.PR (A) = (1-d) + d (PR (T1) / C (T1) + ... + PR (Tn) / C (Tn))
Merk op dat de PageRanks een kansverdeling vormen over webpagina's, dus de som van de PageRanks van alle webpagina's zal een zijn.
2.1.2 Intuïtieve rechtvaardiging
PageRank kan worden gezien als een model van gebruikersgedrag. We gaan ervan uit dat er een "willekeurige surfer" is die willekeurig een webpagina krijgt en steeds op links klikt, nooit "terug" raakt, maar zich uiteindelijk verveelt en op een andere willekeurige pagina begint. De kans dat de willekeurige surfer een pagina bezoekt, is de PageRank. En de d dempingsfactor is de kans dat op elke pagina de "willekeurige surfer" zich zal vervelen en een andere willekeurige pagina zal aanvragen. Een belangrijke variatie is om de dempingsfactor d alleen aan een enkele pagina of een groep pagina's toe te voegen . Dit maakt personalisatie mogelijk en kan het bijna onmogelijk maken om opzettelijk het systeem te misleiden om een hogere ranking te krijgen. We hebben verschillende andere uitbreidingen van PageRank, zie opnieuw [ pagina 98 ].Een andere intuïtieve rechtvaardiging is dat een pagina een hoge PageRank kan hebben als er veel pagina's naar verwijzen, of als er pagina's zijn die erop wijzen en een hoge PageRank hebben. Intuïtief zijn pagina's die goed worden geciteerd uit vele plaatsen op internet, het bekijken waard. Ook pagina's die misschien maar één citaat bevatten van zoiets als de Yahoo! homepage zijn ook over het algemeen de moeite van het bekijken waard. Als een pagina niet van hoge kwaliteit was of een verbroken link was, is het vrij waarschijnlijk dat de startpagina van Yahoo er niet naar zou linken. PageRank behandelt zowel deze gevallen als alles daartussenin door recursief gewichten te propageren via de linkstructuur van het web.
2.2 Ankertekst
De tekst van links wordt op een speciale manier behandeld in onze zoekmachine. De meeste zoekmachines associëren de tekst van een link met de pagina waarop de link staat. Daarnaast associëren we het met de pagina waarnaar de link verwijst. Dit heeft verschillende voordelen. Ten eerste bieden ankers vaak nauwkeuriger beschrijvingen van webpagina's dan de pagina's zelf. Ten tweede kunnen ankers bestaan voor documenten die niet kunnen worden geïndexeerd door een op tekst gebaseerde zoekmachine, zoals afbeeldingen, programma's en databases. Dit maakt het mogelijk om webpagina's te retourneren die niet echt zijn gecrawld. Houd er rekening mee dat pagina's die niet zijn gecrawld problemen kunnen veroorzaken, omdat ze nooit worden gecontroleerd op geldigheid voordat ze worden teruggestuurd naar de gebruiker. In dit geval kan de zoekmachine zelfs een pagina retourneren die nooit echt heeft bestaan, maar waarnaar hyperlinks verwijzen. Echter,Dit idee om ankertekst te verspreiden naar de pagina waarnaar het verwijst, werd geïmplementeerd in de World Wide Web Worm [ McBryan 94 ], vooral omdat het helpt bij het zoeken naar niet-tekstinformatie en de zoekdekking vergroot met minder gedownloade documenten. We gebruiken ankerverspreiding meestal omdat ankertekst kan bijdragen aan betere kwaliteitsresultaten. Het efficiënt gebruiken van ankertekst is technisch moeilijk vanwege de grote hoeveelheden gegevens die moeten worden verwerkt. In onze huidige crawl van 24 miljoen pagina's hadden we meer dan 259 miljoen ankers die we hebben geïndexeerd.
2.3 Andere functies
Afgezien van PageRank en het gebruik van ankertekst, Google heeft verschillende andere functies. Ten eerste heeft het locatie-informatie voor alle hits en dus maakt het veelvuldig gebruik van nabijheid bij het zoeken. Ten tweede houdt Google bepaalde visuele presentatiedetails bij, zoals de lettergrootte van woorden. Woorden in een groter of krachtiger lettertype worden gewogen dan andere woorden. Ten derde is volledige onbewerkte HTML van pagina's beschikbaar in een repository.3 Gerelateerd werk
Zoekonderzoek op het web heeft een korte en beknopte geschiedenis. De World Wide Web Worm (WWWW) [McBryan 94] was een van de eerste webzoekmachines . Het werd vervolgens gevolgd door verschillende andere academische zoekmachines, waarvan er veel nu openbare bedrijven zijn. Vergeleken met de groei van het internet en het belang van zoekmachines zijn er maar weinig documenten over recente zoekmachines [ Pinkerton 94 ]. Volgens Michael Mauldin (hoofdwetenschapper, Lycos Inc) [Mauldin], "de verschillende diensten (waaronder Lycos) bewaken de details van deze databases nauwlettend". Er is echter behoorlijk wat werk aan specifieke kenmerken van zoekmachines gedaan. Vooral goed vertegenwoordigd is werk dat resultaten kan krijgen door de resultaten van bestaande commerciële zoekmachines na te bewerken of kleine "geïndividualiseerde" zoekmachines te produceren. Ten slotte is er veel onderzoek gedaan naar systemen voor het ophalen van informatie, vooral over goed gecontroleerde collecties. In de volgende twee secties bespreken we enkele gebieden waar dit onderzoek moet worden uitgebreid om beter te kunnen werken op internet.3.1 Informatie ophalen
Het werken in informatiezoeksystemen gaat vele jaren terug en is goed ontwikkeld [ Witten 94 ]. Het grootste deel van het onderzoek naar systemen voor het vinden van informatie gaat echter over kleine, goed gecontroleerde homogene collecties zoals verzamelingen wetenschappelijke artikelen of nieuwsverhalen over een verwant onderwerp. Inderdaad, de belangrijkste benchmark voor het ophalen van informatie, de Text Retrieval Conference [ TREC 96], gebruikt een vrij kleine, goed gecontroleerde verzameling voor hun benchmarks. De benchmark "Very Large Corpus" is slechts 20 GB in vergelijking met de 147 GB van onze crawl van 24 miljoen webpagina's. Zaken die goed werken op TREC leveren vaak geen goede resultaten op internet. Het standaard vectorruimtemodel probeert bijvoorbeeld het document terug te geven dat het meest de vraag benadert, aangezien zowel de query als het document vectoren zijn die worden gedefinieerd door hun woordoccurentie. Op het web retourneert deze strategie vaak zeer korte documenten die de zoekopdracht plus enkele woorden zijn. We hebben bijvoorbeeld gezien dat een grote zoekmachine een pagina retourneert met alleen 'Bill Clinton Sucks' en een foto van een 'Bill Clinton'-zoekopdracht. Sommigen beweren dat gebruikers op het web nauwkeuriger moeten specificeren wat ze willen en meer woorden aan hun zoekopdracht kunnen toevoegen. We zijn het oneens met deze stellingname. Als een gebruiker een zoekopdracht als "Bill Clinton" uitbrengt, moeten deze redelijke resultaten behalen, omdat er een enorme hoeveelheid hoogwaardige informatie over dit onderwerp beschikbaar is. Gegeven voorbeelden zoals deze, zijn wij van mening dat de standaardinformatieherwinning moet worden uitgebreid om effectief met het web om te gaan.3.2 Verschillen tussen het web en goed beheerde collecties
Het web is een uitgebreide verzameling van volledig ongecontroleerde heterogene documenten. Documenten op internet hebben een extreme variatie binnen de documenten, en ook in de externe meta-informatie die mogelijk beschikbaar is. Documenten verschillen bijvoorbeeld intern in hun taal (zowel mensen als programmeren), woordenschat (e-mailadressen, links, postcodes, telefoonnummers, productnummers), type of indeling (tekst, HTML, PDF, afbeeldingen, geluiden), en kunnen zelfs machinegegenereerd worden (logbestanden of uitvoer vanuit een database). Aan de andere kant definiëren we externe meta-informatie als informatie die kan worden afgeleid over een document, maar daarin niet is opgenomen. Voorbeelden van externe meta-informatie zijn zaken als reputatie van de bron, updatefrequentie, kwaliteit, populariteit of gebruik en citaten. Niet alleen zijn de mogelijke bronnen van externe meta-informatie gevarieerd, maar de dingen die worden gemeten, variëren ook vele ordes van grootte. Vergelijk bijvoorbeeld de gebruiksinformatie van een belangrijke startpagina, zoals Yahoo's, die momenteel dagelijks miljoenen pageviews ontvangt met een obscuur historisch artikel dat elke tien jaar één weergave zou kunnen ontvangen. Het is duidelijk dat deze twee items zeer verschillend moeten worden behandeld door een zoekmachine.Een ander groot verschil tussen het web en traditionele, goed gecontroleerde collecties is dat er vrijwel geen controle is over wat mensen op internet kunnen zetten. Koppel deze flexibiliteit om alles te publiceren met de enorme invloed van zoekmachines om verkeer te routeren en bedrijven die opzettelijk zoekmachines manipuleren voor winst worden een serieus probleem. Dit probleem is niet aan de orde geweest in traditionele systemen voor het ophalen van gesloten informatie. Het is ook interessant om op te merken dat inspanningen met metadata grotendeels mislukt zijn met webzoekmachines, omdat elke tekst op de pagina die niet direct wordt weergegeven aan de gebruiker, wordt misbruikt om zoekmachines te manipuleren. Er zijn zelfs tal van bedrijven die zijn gespecialiseerd in het manipuleren van zoekmachines voor winst.
4 Systeemanatomie
Eerst zullen we een bespreking op hoog niveau van de architectuur geven. Vervolgens zijn er enkele gedetailleerde beschrijvingen van belangrijke gegevensstructuren. Ten slotte zullen de belangrijkste toepassingen: crawlen, indexeren en zoeken grondig worden onderzocht.
 |
4.1 Google Architectuuroverzicht
In deze sectie geven we een overzicht op hoog niveau van hoe het hele systeem werkt zoals afgebeeld in Figuur 1. Verdere secties zullen de toepassingen en gegevensstructuren bespreken die niet in deze sectie worden genoemd. Het grootste deel van Google is geïmplementeerd in C of C ++ voor efficiëntie en kan worden uitgevoerd in Solaris of Linux.In Google wordt het web gecrawld (het downloaden van webpagina's) door verschillende verspreide crawlers. Er is een URL-server die lijsten met URL's verzendt die moeten worden opgehaald bij de crawlers. De webpagina's die worden opgehaald, worden vervolgens naar de winkelserver verzonden. De opslagserver comprimeert vervolgens en slaat de webpagina's op in een repository. Elke webpagina heeft een bijbehorend ID-nummer, een document dat wordt toegewezen wanneer een nieuwe URL wordt geparseerd op een webpagina. De indexeerfunctie wordt uitgevoerd door de indexeereenheid en de sorteerder. De indexeereenheid voert een aantal functies uit. Het leest de repository, decomprimeert de documenten en parseert ze. Elk document wordt omgezet in een reeks woordvoorvallen die hits worden genoemd. De hits registreren het woord, de positie in het document, een benadering van de tekengrootte en hoofdletters. De indexeerder verdeelt deze hits in een set "vaten", een gedeeltelijk gesorteerde forward-index maken. De indexeerfunctie voert nog een belangrijke functie uit. Het parseert alle links in elke webpagina en slaat belangrijke informatie over hen op in een ankerbestand. Dit bestand bevat voldoende informatie om te bepalen waar elke koppeling naartoe wijst en de tekst van de link.
De URLresolver leest het ankerbestand en converteert relatieve URL's in absolute URL's en vervolgens in docID's. Het plaatst de ankertekst in de voorwaartse index, gekoppeld aan de docID waarnaar het anker verwijst. Het genereert ook een database van koppelingen die paren van docID's zijn. De koppelingsdatabase wordt gebruikt om PageRanks voor alle documenten te berekenen.
De sorteerder neemt de vaten, die worden gesorteerd op docID (dit is een vereenvoudiging, zie Paragraaf 4.2.5 ) en plaatst ze op basis van woord-ID om de geïnverteerde index te genereren. Dit gebeurt op zijn plaats, zodat er weinig tijdelijke ruimte nodig is voor deze operatie. De sorteerder produceert ook een lijst met woord-ID's en verschuivingen in de geïnverteerde index. Een programma genaamd DumpLexicon neemt deze lijst samen met het lexicon geproduceerd door de indexeereenheid en genereert een nieuw lexicon dat door de zoeker moet worden gebruikt. De zoeker wordt gerund door een webserver en gebruikt het lexicon van DumpLexicon samen met de geïnverteerde index en de PageRanks om vragen te beantwoorden.
4.2 Belangrijke datastructuren
De datastructuren van Google zijn geoptimaliseerd, zodat een grote documentenverzameling met weinig kosten kan worden gecrawld, geïndexeerd en doorzocht. Hoewel de outputsnelheden van CPU's en bulkinput in de loop der jaren dramatisch zijn verbeterd, duurt het nog ongeveer 10 ms om een schijfzoekopdracht uit te voeren. Google is ontworpen om te voorkomen dat schijf waar mogelijk wordt gezocht, en dit heeft een aanzienlijke invloed gehad op het ontwerp van de gegevensstructuren.4.2.1 BigFiles
BigFiles zijn virtuele bestanden die meerdere bestandssystemen omspannen en kunnen worden geadresseerd met 64-bits gehele getallen. De toewijzing tussen meerdere bestandssystemen wordt automatisch afgehandeld. Het BigFiles-pakket behandelt ook de toewijzing en de toewijzing van bestandsdescriptoren, omdat de besturingssystemen niet voldoende zijn voor onze behoeften. BigFiles ondersteunt ook rudimentaire compressie-opties.4.2.2 Repository
 |
4.2.3 Documentindex
De documentindex houdt informatie bij over elk document. Het is een ISAM-index (indexsequentiële toegangsmodus) met een vaste breedte, gesorteerd op document. De informatie die in elk item is opgeslagen, omvat de huidige documentstatus, een verwijzing naar de repository, een documentcontrolesom en verschillende statistieken. Als het document is gecrawld, bevat het ook een verwijzing naar een bestand met variabele breedte genaamd docinfo, dat de URL en titel bevat. Anders wijst de aanwijzer naar de URL-lijst die alleen de URL bevat. Deze ontwerpbeslissing werd gedreven door de wens om een redelijk compacte gegevensstructuur te hebben en de mogelijkheid om een record op één schijf op te halen tijdens een zoekopdrachtBovendien is er een bestand dat wordt gebruikt om URL's in docID's te converteren. Het is een lijst met URL-checksums met bijbehorende docID's en wordt gesorteerd op checksum. Om de document-ID van een bepaalde URL te vinden, wordt de controlesom van de URL berekend en wordt er een binaire zoekopdracht uitgevoerd op het controlesom-bestand om de bijbehorende document-ID te vinden. URL's kunnen in batch worden omgezet in docID's door een samenvoeging met dit bestand te maken. Dit is de techniek die de URLresolver gebruikt om URL's in docID's om te zetten. Deze batch-modus van update is van cruciaal belang, anders moeten we voor elke link één zoekopdracht uitvoeren waarbij aangenomen wordt dat een schijf meer dan een maand nodig zou hebben voor onze 322 miljoen-koppelingsgegevensset.
4.2.4 Lexicon
Het lexicon heeft verschillende vormen. Een belangrijke verandering ten opzichte van eerdere systemen is dat het lexicon voor een redelijke prijs in het geheugen kan worden opgeslagen. In de huidige implementatie kunnen we het lexicon in het geheugen bewaren op een machine met 256 MB hoofdgeheugen. Het huidige lexicon bevat 14 miljoen woorden (hoewel enkele zeldzame woorden niet aan het lexicon zijn toegevoegd). Het is geïmplementeerd in twee delen: een lijst met woorden (samengevoegd maar gescheiden door nullen) en een hash-tabel met aanwijzers. Voor verschillende functies bevat de woordenlijst wat hulpinformatie die buiten het bestek van dit document valt om volledig uit te leggen.4.2.5 Hitlijsten
Een trefferlijst komt overeen met een lijst van voorkomens van een bepaald woord in een bepaald document, inclusief positie-, lettertype- en hoofdletterinformatie. Hitlijsten zijn verantwoordelijk voor het grootste deel van de ruimte die wordt gebruikt in zowel de voorwaartse als de omgekeerde index. Daarom is het belangrijk om hen zo efficiënt mogelijk te vertegenwoordigen. We hebben verschillende alternatieven overwogen voor het coderen van positie, lettertype en hoofdlettergebruik: eenvoudige codering (een drievoud van gehele getallen), een compacte codering (een handgeoptimaliseerde toewijzing van bits) en Huffman-codering. Uiteindelijk hebben we gekozen voor een handgeoptimaliseerde, compacte codering, omdat er veel minder ruimte nodig was dan de eenvoudige codering en veel minder bitmanipulatie dan Huffman-codering. De details van de treffers worden getoond in figuur 3.Onze compacte codering gebruikt twee bytes voor elke hit. Er zijn twee soorten hits: fraaie hits en gewone hits. Fancy-hits zijn treffers die voorkomen in een URL, titel, ankertekst of metatag. Effen hits omvatten al het andere. Een gewone hit bestaat uit een hoofdletter, lettergrootte en 12 bits woordpositie in een document (alle posities hoger dan 4095 zijn gemarkeerd met 4096). Lettergrootte wordt ten opzichte van de rest van het document weergegeven met behulp van drie bits (alleen 7 waarden worden feitelijk gebruikt omdat 111 de vlag is die een fraaie treffer meldt). Een mooie hit bestaat uit een kapitalisatiebit, de lettergrootte is ingesteld op 7 om aan te geven dat het een mooie hit is, 4 bits om het type fancy hit te coderen en 8 bits positie. Voor anker treffers worden de 8 bits van positie gesplitst in 4 bits voor positie in anker en 4 bits voor een hash van de docID waar het anker in voorkomt. Dit geeft ons een beperkte zoekzin, zolang er niet zoveel ankers zijn voor een bepaald woord. We verwachten dat de manier wordt bijgewerkt waarop ankerhits worden opgeslagen om een grotere resolutie toe te staan in de positie- en docIDhash-velden. We gebruiken de tekengrootte ten opzichte van de rest van het document, omdat u tijdens het zoeken niet anders identieke documenten anders wilt rangschikken alleen omdat een van de documenten een groter lettertype heeft.
 |
De lengte van een hitlijst wordt opgeslagen vóór de hits zelf. Om ruimte te besparen, wordt de lengte van de hitlijst gecombineerd met de woord-ID in de voorwaartse index en de document-ID in de geïnverteerde index. Dit beperkt het tot respectievelijk 8 en 5 bits (er zijn enkele tricks waarmee 8 bits van de wordID kunnen worden geleend). Als de lengte langer is dan in dat aantal bits past, wordt in die bits een escape-code gebruikt en bevatten de volgende twee bytes de werkelijke lengte.
4.2.6 Doorstuurindex
De voorwaartse index is eigenlijk al gedeeltelijk gesorteerd. Het wordt opgeslagen in een aantal vaten (we gebruikten 64). Elk vat bevat een reeks woord-id's. Als een document woorden bevat die in een bepaald vat vallen, wordt de document-id opgenomen in het vat, gevolgd door een lijst met woord-ID's met hitlijsten die overeenkomen met die woorden. Dit schema vereist iets meer opslag vanwege gedupliceerde docID's, maar het verschil is erg klein voor een redelijk aantal buckets en bespaart veel tijd en coderingscomplexiteit in de laatste indexeringsfase van de sorteerder. Bovendien slaan we, in plaats van het opslaan van werkelijke woord-id's, elk woord-ID op als een relatief verschil met het minimale woord-ID dat in het vat valt dat het woord-ID bevat. Op deze manier kunnen we slechts 24 bits gebruiken voor de woord-id's in de ongesorteerde vaten,4.2.7 Omgekeerde index
De geïnverteerde index bestaat uit dezelfde vaten als de voorwaartse index, behalve dat ze door de sorteerder zijn verwerkt. Voor elke geldige woord-id bevat het lexicon een aanwijzer in de loop waar het woordID in valt. Het verwijst naar een doclist van docID's samen met hun bijbehorende hitlijsten. Deze doclist geeft alle voorkomens van dat woord in alle documenten weer.Een belangrijk probleem is in welke volgorde de docID's in de documentenlijst moeten verschijnen. Een eenvoudige oplossing is om ze op te slaan gesorteerd op docID. Dit maakt snelle samenvoeging van verschillende doclists voor zoekopdrachten van meerdere woorden mogelijk. Een andere optie is om ze op te slaan gesorteerd op een rangorde van het voorkomen van het woord in elk document. Dit maakt het beantwoorden van één woord quigiaal en maakt het waarschijnlijk dat de antwoorden op vragen van meerdere woorden bijna bij het begin liggen. Samenvoegen is echter veel moeilijker. Ook maakt dit de ontwikkeling veel moeilijker omdat een wijziging van de ranglijstfunctie een heropbouw van de index vereist. We kozen voor een compromis tussen deze opties, waarbij we twee sets omgekeerde vaten behouden - één set voor hitlijsten met titel- of ankerhits en een andere set voor alle hitlijsten. Op deze manier
4.3 Het web crawlen
Het runnen van een webcrawler is een uitdagende taak. Er zijn lastige problemen met de prestaties en betrouwbaarheid en nog belangrijker, er zijn sociale problemen. Crawling is de meest kwetsbare applicatie omdat het gaat om interactie met honderdduizenden webservers en verschillende nameservers die allemaal buiten de controle van het systeem vallen.Om te schalen naar honderden miljoenen webpagina's, heeft Google een snel verdeeld crawlsysteem. Een enkele URL-server biedt lijsten met URL's voor een aantal crawlers (we hebben meestal ongeveer 3). Zowel de URLserver als de crawlers zijn geïmplementeerd in Python. Elke crawler houdt ruwweg 300 verbindingen tegelijk open. Dit is nodig om webpagina's snel genoeg op te halen. Bij pieksnelheden kan het systeem meer dan 100 webpagina's per seconde crawlen met behulp van vier crawlers. Dit komt neer op ongeveer 600K per seconde aan gegevens. Een belangrijke prestatiestress is DNS-lookup. Elke crawler onderhoudt een eigen DNS-cache, zodat het niet nodig is om een DNS-lookup uit te voeren voordat elk document wordt gecrawld. Elk van de honderden verbindingen kan in een aantal verschillende toestanden zijn: DNS opzoeken, verbinding maken met host, verzoek verzenden en antwoord ontvangen. Deze factoren maken de crawler een complex onderdeel van het systeem. Het gebruikt asynchrone IO om gebeurtenissen te beheren, en een aantal wachtrijen om paginaophalingen van status naar staat te verplaatsen.
Het blijkt dat het runnen van een crawler die verbinding maakt met meer dan een half miljoen servers en tientallen miljoenen logboekinvoeren genereert, een behoorlijke hoeveelheid e-mail en telefoontjes genereert. Vanwege het enorme aantal mensen dat online komt, zijn er altijd mensen die niet weten wat een crawler is, omdat dit de eerste is die ze hebben gezien. Bijna dagelijks ontvangen we een e-mail in de trant van: "Wauw, je hebt veel pagina's bekeken van mijn website." Hoe vond je het? " Er zijn ook enkele mensen die niet weten wat het uitsluitingsprotocol voor robots isen denk dat hun pagina moet worden beschermd tegen indexering door een verklaring als: "Deze pagina is auteursrechtelijk beschermd en mag niet worden geïndexeerd", wat uiteraard voor webcrawlers moeilijk te begrijpen is. Vanwege de enorme hoeveelheid gegevens die worden gebruikt, zullen er onverwachte dingen gebeuren. Ons systeem probeerde bijvoorbeeld een online game te crawlen. Dit resulteerde in het midden van hun spel in heel wat afvalberichten! Het bleek een eenvoudig probleem om op te lossen. Maar dit probleem was niet opgetreden voordat we tientallen miljoenen pagina's hadden gedownload. Vanwege de immense variatie in webpagina's en servers, is het vrijwel onmogelijk om een crawler te testen zonder deze op een groot deel van internet te gebruiken. Steevast zijn er honderden obscure problemen die alleen op één pagina uit het hele web kunnen voorkomen en ervoor zorgen dat de crawler vastloopt of, erger nog, onvoorspelbaar of onjuist gedrag veroorzaken. Systemen die toegang hebben tot grote delen van het internet moeten zeer robuust en zorgvuldig getest zijn. Omdat grote complexe systemen zoals crawlers altijd problemen zullen veroorzaken, moeten er aanzienlijke middelen worden besteed aan het lezen van de e-mail en het oplossen van deze problemen wanneer ze zich voordoen.
4.4 Het internet indexeren
- Parsing: elke parser die is ontworpen om op het hele web te worden uitgevoerd, moet een groot aantal mogelijke fouten verwerken. Deze variëren van typfouten in HTML-tags tot kilobytes van nullen in het midden van een tag, niet-ASCII-tekens, HTML-tags die honderden diep genest zijn en een grote verscheidenheid aan andere fouten die de verbeelding van iemand uitdagen om met even creatieve degenen te komen. Voor maximale snelheid gebruiken we, in plaats van YACC te gebruiken om een CFG-parser te genereren, flex om een lexicale analysator te genereren die we met een eigen stack uitrusten. Het ontwikkelen van deze parser, die redelijk snel draait en erg robuust is, bracht behoorlijk wat werk met zich mee.
- Documenten indexeren in vaten - Nadat elk document is geparseerd, is het gecodeerd in een aantal vaten. Elk woord wordt omgezet in een woord-ID met behulp van een in-memory hashtabel - het lexicon. Nieuwe toevoegingen aan de hash-tabel in het lexicon worden in een bestand vastgelegd. Nadat de woorden in woord-id's zijn omgezet, worden hun occurrences in het huidige document vertaald naar hitlijsten en in de voorwaartse vaten geschreven. De grootste moeilijkheid met parallellisatie van de indexeringsfase is dat het lexicon moet worden gedeeld. In plaats van het lexicon te delen, hebben we de logica genomen om een logboek te schrijven van alle extra woorden die niet in een basislexicon stonden, die we met 14 miljoen woorden hebben opgelost. Op die manier kunnen meerdere indexers parallel lopen en dan kan het kleine logbestand van extra woorden door een laatste indexer worden verwerkt.
- Sorteren - Om de geïnverteerde index te genereren, neemt de sorteerder elk van de voorwaartse vaten en sorteert deze op basis van woord-ID om een omgekeerd vat te produceren voor titel- en ankertreffers en een omgekeerd vat met volledige tekst. Dit proces gebeurt één vat per keer, waardoor er weinig tijdelijke opslag vereist is. We parallelliseren ook de sorteerfase om zo veel machines te gebruiken als we hebben door simpelweg meerdere sorteerders te gebruiken, die verschillende buckets tegelijkertijd kunnen verwerken. Omdat de vaten niet in het hoofdgeheugen passen, verdeelt de sorteerder ze verder in manden die wel in het geheugen passen op basis van woord-ID en document-ID. Vervolgens laadt de sorteerder elke mand in het geheugen, sorteert deze en schrijft zijn inhoud in de korte omgekeerde loop en de volledig omgekeerde loop.
4.5 Zoeken
Het doel van zoeken is om efficiënte zoekresultaten te leveren. Veel van de grote commerciële zoekmachines leken grote vooruitgang te hebben geboekt op het gebied van efficiëntie. Daarom hebben we ons in ons onderzoek meer gericht op zoekkwaliteit, hoewel we van mening zijn dat onze oplossingen met een beetje meer inspanning schaalbaar zijn naar commerciële volumes. Het evaluatieproces van de google-vraag is weergegeven in afbeelding 4.
Sorteer de documenten die op rangorde hebben gematcht en geef de top k terug. |
Om een limiet op de responstijd te stellen, gaat een gebruiker, nadat een bepaald aantal (momenteel 40.000) overeenkomende documenten zijn gevonden, automatisch naar stap 8 in figuur 4. Dit betekent dat het mogelijk is dat niet-optimale resultaten worden geretourneerd. We onderzoeken momenteel andere manieren om dit probleem op te lossen. In het verleden sorteerden we de hits volgens PageRank, wat de situatie leek te verbeteren.
4.5.1 Het rangschikkingssysteem
Google onderhoudt veel meer informatie over webdocumenten dan gewone zoekmachines. Elke hitlijst bevat informatie over positie, lettertype en hoofdlettergebruik. Daarnaast tellen we treffers op uit ankertekst en de PageRank van het document. Het combineren van al deze informatie tot een rang is moeilijk. We hebben onze rangschikkingsfunctie zo ontworpen dat geen bepaalde factor te veel invloed kan hebben. Overweeg eerst de eenvoudigste zaak - een enkele woordquery. Om een document te rangschikken met een enkele woordquery, kijkt Google naar de hitlijst van dat document voor dat woord. Google beschouwt elke hit als een van de verschillende typen (titel, anker, URL, platte tekst groot lettertype, platte tekst klein lettertype, ...), die elk hun eigen soortgewicht hebben. De typegewichten vormen een vector, geïndexeerd per type. Google telt het aantal hits van elk type in de trefferlijst. Vervolgens wordt elke telling omgezet in een telgewicht. De telgewichten worden lineair verhoogd met tellingen, maar worden snel kleiner, zodat meer dan een bepaalde telling niet helpt. We nemen het puntproduct van de vector van telgewichten met de vector van type-gewichten om een IR-score voor het document te berekenen. Ten slotte wordt de IR-score gecombineerd met PageRank om een laatste rang te geven aan het document.Voor een zoekopdracht van meerdere woorden is de situatie gecompliceerder. Nu moeten meerdere hitlijsten tegelijk worden gescand, zodat hits die dicht bij elkaar in een document staan, hoger worden gewogen dan hits die ver uit elkaar liggen. De treffers van de meerdere hitlijsten zijn op elkaar afgestemd, zodat hits in de buurt op elkaar worden afgestemd. Voor elke overeenkomende reeks treffers wordt een nabijheid berekend. De nabijheid is gebaseerd op hoe ver de treffers zich in het document (of anker) van elkaar bevinden, maar is geclassificeerd in 10 "bins" met verschillende waarden, gaande van een phrase-match tot "not-even-dichtbij". Tellingen worden niet alleen voor elk type treffer berekend, maar voor elk type en nabijheid. Elk type en nabijheidspaar heeft een type-prox-gewicht. De tellingen worden omgezet in telgewichten en we nemen het puntproduct van de telgewichten en de type prox-gewichten om een IR-score te berekenen. Al deze getallen en matrices kunnen allemaal met de zoekresultaten worden weergegeven met behulp van een speciale debug-modus. Deze schermen zijn zeer nuttig geweest bij het ontwikkelen van het classificatiesysteem.
4.5.2 Feedback
De rangordefunctie heeft veel parameters zoals de typegewichten en de type prox-gewichten. Het uitzoeken van de juiste waarden voor deze parameters is iets van een zwarte kunst. Om dit te doen, hebben we een gebruikersfeedback-mechanisme in de zoekmachine. Een vertrouwde gebruiker kan optioneel alle geretourneerde resultaten evalueren. Deze feedback wordt opgeslagen. Wanneer we vervolgens de rangschikkingsfunctie wijzigen, kunnen we de impact van deze wijziging op alle eerdere zoekopdrachten zien die gerangschikt waren. Hoewel verre van perfect, geeft dit ons een idee van hoe een verandering in de rangschikkingsfunctie de zoekresultaten beïnvloedt.5 Resultaten en prestaties
| Zoekopdracht: bill clinton
http://www.whitehouse.gov/ 100.00%  
(geen datum) (0K)
http://www.whitehouse.gov/ Kabinet van de president 99.67%
(23 december 1996) (2K)
http: / /www.whitehouse.gov/WH/EOP/OP/html/OP_Home.html Welkom bij The White House 99,98% (Nov 09 1997) (5K) http://www.whitehouse.gov/WH/Welcome.html Send Electronic Mail naar de president 99,86% (14 juli 1997) (5K) http://www.whitehouse.gov/WH/Mail/html/Mail_President.html mailto: president@whitehouse.gov 99,98% mailto: President@whitehouse.gov 99.27 %
De "onofficiële" Bill Clinton 94,06%
(11 november 1997) (14K)
http://zpub.com/un/un-bc.html Bill Clinton ontmoet The Shrinks 86,27% (29 juni 1997) (63K) http: // zpub.com/un/un-bc9.html President Bill Clinton - The Dark Side 97,27% (10 november 1997) (15K) http://www.realchange.org/clinton.htm $ 3 Bill Clinton 94,73% (geen datum) (4K) http://www.gatewy.net/~tjohnson/clinton1.html
|
Alle resultaten zijn pagina's van redelijk hoge kwaliteit en, ten laatste controle, geen ervan waren verbroken koppelingen. Dit komt grotendeels omdat ze allemaal een hoge PageRank hebben. De PageRanks zijn de percentages in rood samen met staafdiagrammen. Ten slotte zijn er geen resultaten over een andere Bill dan Clinton of over een andere Clinton dan Bill. Dit komt omdat we veel belang hechten aan de nabijheid van woordvoorvallen. Natuurlijk zou een echte test van de kwaliteit van een zoekmachine gepaard gaan met een uitgebreide gebruikersstudie of resultatenanalyse waar we hier geen ruimte voor hebben. In plaats daarvan nodigen we de lezer uit om Google zelf te proberen op http://google.stanford.edu .
5.1 Opslagvereisten
Afgezien van de zoekkwaliteit, is Google ontworpen om kostenefficiënt te schalen naar de grootte van het internet terwijl het groeit. Een aspect hiervan is om opslag efficiënt te gebruiken. Tabel 1 bevat een overzicht van enkele statistieken en opslagvereisten van Google. Vanwege de compressie is de totale grootte van de repository ongeveer 53 GB, iets meer dan een derde van de totale gegevens die worden opgeslagen. Met de huidige schijfprijzen maakt dit de repository een relatief goedkope bron van bruikbare gegevens. Nog belangrijker is dat het totaal van alle gegevens die door de zoekmachine worden gebruikt een vergelijkbare hoeveelheid opslag vereist, ongeveer 55 GB. Bovendien kunnen de meeste vragen worden beantwoord met alleen de korte geïnverteerde index. Met betere codering en compressie van de documentindex kan een hoogwaardige webzoekmachine passen op een 7-Gb-schijf van een nieuwe pc.
|
||||||||||||||||||||||
|
||||||||||||||||||||||
|
|
||||||||||||||||||||||
5.2 Systeemprestaties
Het is belangrijk dat een zoekmachine efficiënt crawlt en indexeert. Op deze manier kan informatie up-to-date worden gehouden en kunnen belangrijke wijzigingen in het systeem relatief snel worden getest. Voor Google zijn de belangrijkste bewerkingen Crawling, Indexing en Sorting. Het is moeilijk om te meten hoe lang crawlen in totaal in beslag heeft genomen, omdat schijven zijn opgevuld, naamservers zijn gecrasht of een aantal andere problemen waardoor het systeem is gestopt. In totaal duurde het ongeveer 9 dagen om de 26 miljoen pagina's (inclusief fouten) te downloaden. Zodra het systeem soepel draaide, draaide het echter veel sneller, waarbij de laatste 11 miljoen pagina's in slechts 63 uur werden gedownload, gemiddeld iets meer dan 4 miljoen pagina's per dag of 48,5 pagina's per seconde. We hebben de indexer en de crawler gelijktijdig uitgevoerd. De indexer liep net sneller dan de crawlers. Dit komt grotendeels omdat we precies genoeg tijd hebben besteed aan het optimaliseren van de indexeerinrichting zodat het geen bottleneck zou zijn. Deze optimalisaties omvatten bulkupdates voor de documentindex en de plaatsing van kritieke gegevensstructuren op de lokale schijf. De indexer werkt met ongeveer 54 pagina's per seconde. De sorteerders kunnen volledig parallel worden uitgevoerd; met vier machines duurt het hele sorteerproces ongeveer 24 uur.5.3 Zoekprestaties
Verbetering van de prestaties van het zoeken was tot nu toe niet de belangrijkste focus van ons onderzoek. De huidige versie van Google beantwoordt de meeste vragen tussen 1 en 10 seconden. Deze tijd wordt meestal gedomineerd door schijf-IO ten opzichte van NFS (aangezien schijven over een aantal machines zijn verspreid). Verder heeft Google geen optimalisaties zoals query-caching, subindices op basis van algemene termen en andere veelvoorkomende optimalisaties. We willen Google aanzienlijk versnellen via distributie en hardware, software en algoritmische verbeteringen. Ons doel is om honderden vragen per seconde te kunnen verwerken. Tabel 2 bevat enkele voorbeeldzoektijden van de huidige versie van Google. Ze worden herhaald om de versnellingen weer te geven die resulteren uit de IO in de cache.
|
||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||
6. Conclusies
Google is ontworpen om een schaalbare zoekmachine te zijn. Het primaire doel is om zoekresultaten van hoge kwaliteit te leveren op een snelgroeiend World Wide Web. Google gebruikt een aantal technieken om de zoekkwaliteit te verbeteren, waaronder paginarang, ankertekst en informatie over de nabijheid. Verder is Google een complete architectuur voor het verzamelen van webpagina's, het indexeren ervan en het uitvoeren van zoekopdrachten daarover.6.1 Toekomstig werk
Een grootschalige webzoekmachine is een complex systeem en er moet nog veel worden gedaan. Onze onmiddellijke doelen zijn om de zoekefficiëntie te verbeteren en te schalen naar ongeveer 100 miljoen webpagina's. Enkele eenvoudige efficiëntieverbeteringen zijn query-caching, toewijzing van smart-schijven en subindices. Een ander gebied dat veel onderzoek vereist zijn updates. We moeten slimme algoritmen hebben om te beslissen welke oude webpagina's opnieuw moeten worden gecrawld en welke nieuwe moeten worden gecrawld. Werk in de richting van dit doel is gedaan in [ Cho 98]. Een veelbelovend onderzoeksgebied is het gebruik van proxy-caches om zoekdatabases te bouwen, omdat deze vraaggestuurd zijn. We zijn van plan om eenvoudige functies toe te voegen die worden ondersteund door commerciële zoekmachines zoals booleaanse operatoren, negatie en afstemming. Andere functies beginnen echter pas te worden onderzocht, zoals relevantie feedback en clustering (Google ondersteunt momenteel een eenvoudige hostnaam gebaseerde clustering). We zijn ook van plan om de gebruikerscontext (zoals de locatie van de gebruiker) en de resultaatsamenvatting te ondersteunen. We werken ook aan het uitbreiden van het gebruik van linkstructuur en linktekst. Eenvoudige experimenten duiden erop dat PageRank kan worden gepersonaliseerd door het gewicht van de startpagina of bladwijzers van een gebruiker te vergroten. Wat linktekst betreft, experimenteren we met het gebruik van tekstomringende links naast de linktekst zelf. Een webzoekmachine is een zeer rijke omgeving voor onderzoeksideeën. We hebben hier veel te veel om op te noemen, dus we verwachten niet dat dit Future Work-gedeelte in de nabije toekomst veel korter wordt.6.2 Zoeken van hoge kwaliteit
Het grootste probleem voor gebruikers van zoekmachines op dit moment is de kwaliteit van de resultaten die ze terugkrijgen. Hoewel de resultaten vaak amusant zijn en de horizon van gebruikers vergroten, zijn ze vaak frustrerend en kost het kostbare tijd. Het belangrijkste resultaat voor een zoekopdracht naar "Bill Clinton" op een van de meest populaire commerciële zoekmachines was bijvoorbeeld de Bill Clinton Joke of the Day: 14 april 1997. Google is ontworpen om zoekresultaten van hogere kwaliteit te bieden, zodat het internet snel blijft groeien en informatie gemakkelijk kan worden gevonden. Om dit te bereiken maakt Google intensief gebruik van hypertextuele informatie bestaande uit linkstructuur en link (anker) tekst. Google maakt ook gebruik van proximity- en lettertype-informatie. Hoewel de evaluatie van een zoekmachine moeilijk is, hebben we subjectief vastgesteld dat Google zoekresultaten van hogere kwaliteit retourneert dan de huidige commerciële zoekmachines. De analyse van de linkstructuur via PageRank stelt Google in staat om de kwaliteit van webpagina's te evalueren. Het gebruik van linktekst als een beschrijving van waarnaar de link verwijst, helpt de zoekmachine om relevante (en tot op zekere hoogte hoge kwaliteit) resultaten te retourneren. Ten slotte helpt het gebruik van proximity-informatie de relevantie van veel vragen enorm te vergroten.6.3 Schaalbare architectuur
Afgezien van de kwaliteit van zoeken, is Google ontworpen om te schalen. Het moet efficiënt zijn in zowel ruimte als tijd, en constante factoren zijn erg belangrijk bij het omgaan met het hele web. Bij de implementatie van Google hebben we knelpunten gezien in CPU, geheugentoegang, geheugencapaciteit, schijf zoekt, schijfdoorvoer, schijfcapaciteit en IO van het netwerk. Google is geëvolueerd om een aantal van deze knelpunten te overwinnen tijdens verschillende operaties. De belangrijkste gegevensstructuren van Google maken efficiënt gebruik van de beschikbare opslagruimte. Bovendien zijn de crawling-, indexerings- en sorteerbewerkingen efficiënt genoeg om een index van een aanzienlijk deel van het web te kunnen bouwen - 24 miljoen pagina's, in minder dan een week. We verwachten in minder dan een maand een index van 100 miljoen pagina's te kunnen bouwen.6.4 Een onderzoekstool
Google is niet alleen een zoekmachine van hoge kwaliteit, maar ook een onderzoekstool. De gegevens die Google heeft verzameld, hebben al geresulteerd in veel andere documenten die zijn ingezonden voor conferenties en nog veel meer op komst. Recent onderzoek zoals [ Abiteboul 97 ] heeft een aantal beperkingen aan vragen over het web laten zien die beantwoord kunnen worden zonder dat het web lokaal beschikbaar is. Dit betekent dat Google (of een vergelijkbaar systeem) niet alleen een waardevol onderzoeksinstrument is, maar ook noodzakelijk voor een breed scala aan toepassingen. We hopen dat Google een bron zal zijn voor onderzoekers en onderzoekers over de hele wereld en de volgende generatie zoekmachine-technologie zal stimuleren.7 Erkenningen
Scott Hassan en Alan Steremberg zijn cruciaal geweest voor de ontwikkeling van Google. Hun getalenteerde bijdragen zijn onvervangbaar en de auteurs danken hen veel dankbaarheid. We willen ook Hector Garcia-Molina, Rajeev Motwani, Jeff Ullman en Terry Winograd en de hele WebBase-groep bedanken voor hun steun en hun inzichtelijke discussies. Tot slot willen we de genereuze steun van onze apparatuurdonoren IBM, Intel en Sun en onze financiers erkennen. Het hier beschreven onderzoek werd uitgevoerd als onderdeel van het Stanford Integrated Digital Library Project, ondersteund door de National Science Foundation onder samenwerkingsovereenkomst IRI-9411306. Financiering voor deze samenwerkingsovereenkomst wordt ook geboden door DARPA en NASA, en door Interval Research en de industriële partners van het Stanford Digital Libraries Project.Referenties
- Best of the Web 1994 - Navigators http://botw.org/1994/awards/navigators.html
- Bill Clinton Joke of the Day: 14 april 1997. http://www.io.com/~cjburke/clinton/970414.html.
- Bzip2 Homepage http://www.muraroa.demon.co.uk/
- Google-zoekmachine http://google.stanford.edu/
- Oogst http://harvest.transarc.com/
- Mauldin, Michael L. Lycos Design Choices in een Internet Search Service, IEEE Expert Interview http://www.computer.org/pubs/expert/1997/trends/x1008/mauldin.htm
- Het effect van mobiel telefoneren op stuurprogramma Aandacht http://www.webfirst.com/aaa/text/cell/cell0toc.htm
- Zoekmachine Kijk http://www.searchenginewatch.com/
- RFC 1950 (zlib) ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html
- Robots Exclusion Protocol: http://info.webcrawler.com/mak/projects/robots/exclusion.htm
- Webgroei Samenvatting: http://www.mit.edu/people/mkgray/net/web-growth-summary.html
- Yahoo! http://www.yahoo.com/
- [Abiteboul 97] Serge Abiteboul en Victor Vianu, Queries and Computation op het web . Proceedings of the International Conference on Database Theory. Delphi, Griekenland 1997.
- [Bagdikian 97] Ben H. Bagdikian. Het mediaponopolie . 5e editie. Uitgever: Beacon, ISBN: 0807061557
- [Chakrabarti 98] S.Chakrabarti, B.Dom, D.Gibson, J.Kleinberg, P. Raghavan en S. Rajagopalan. Automatische resourcecompilatie door Hyperlink-structuur en bijbehorende tekst te analyseren. Zevende internationale webconferentie (WWW 98). Brisbane, Australië, 14 - 18 april 1998.
- [Cho 98] Junghoo Cho, Hector Garcia-Molina, Lawrence Page. Efficiënt crawlen via URL-bestelling. Zevende internationale webconferentie (WWW 98). Brisbane, Australië, 14 - 18 april 1998.
- [Gravano 94] Luis Gravano, Hector Garcia-Molina en A. Tomasic. De effectiviteit van GlOSS voor het ontdekkingsprobleem met tekstdatabase. Proc. van de 1994 ACM SIGMOD Internationale Conferentie over het beheer van gegevens, 1994.
- [Kleinberg 98] Jon Kleinberg, gezaghebbende bronnen in een hypergelinkte omgeving , Proc. ACM-SIAM Symposium over discrete algoritmen, 1998.
- [Marchiori 97] Massimo Marchiori. De zoektocht naar juiste informatie op het web: hyperzoekmachines. De zesde internationale WWW-conferentie (WWW 97). Santa Clara, VS, 7 - 11 april 1997.
- [McBryan 94] Oliver A. McBryan. GENVL en WWWW: Tools voor het temmen van het web. Eerste internationale conferentie op het World Wide Web. CERN, Genève (Zwitserland), 25-26-27 mei 1994. http://www.cs.colorado.edu/home/mcbryan/mypapers/www94.ps
- [Pagina 98] Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd. De PageRank Citation Ranking: Order brengen naar het web. Manuscript aan de gang. http://google.stanford.edu/~backrub/pageranksub.ps
- [Pinkerton 94] Brian Pinkerton, vinden wat mensen willen: ervaringen met de WebCrawler. The Second International WWW Conference Chicago, VS, 17-20 oktober 1994. http://info.webcrawler.com/bp/WWW94.html
- [Spertus 97] Ellen Spertus. Parasite: structurele informatie op het web verzamelen. De zesde internationale WWW-conferentie (WWW 97). Santa Clara, VS, 7 - 11 april 1997.
- [TREC 96] Proceedings van de vijfde tekstretrieval-conferentie (TREC-5). Gaithersburg, Maryland, 20- 22 november 1996. Uitgever: Department of Commerce, National Institute of Standards and Technology. Redactie: DK Harman en EM Voorhees. Volledige tekst op: http://trec.nist.gov/
- [Witten 94] Ian H Witten, Alistair Moffat en Timothy C. Bell. Gigabytes beheren: documenten en afbeeldingen comprimeren en indexeren. New York: Van Nostrand Reinhold, 1994.
- [Weiss 96] Ron Weiss, Bienvenido Velez, Mark A. Sheldon, Chanathip Manprempre, Peter Szilagyi, Andrzej Duda en David K. Gifford. HyPursuit: een hiërarchische netwerkzoekmachine die gebruikmaakt van hypertextclustering via content-link. Proceedings of the 7th ACM Conference on Hypertext. New York, 1996.
vitae
Sergey Brin behaalde zijn licentiaat in wiskunde en computerwetenschappen aan de University of Maryland in College Park in 1993. Momenteel is hij een Ph.D. kandidaat in computerwetenschappen aan de Stanford University, waar hij in 1995 zijn MS ontving. Hij is ontvanger van een National Science Foundation Graduate Fellowship. Zijn onderzoeksinteresses omvatten zoekmachines, extractie van informatie van ongestructureerde bronnen en data mining van grote tekstverzamelingen en wetenschappelijke gegevens.
Lawrence Page werd geboren in East Lansing, Michigan, en ontving in 1995 een BSE in Computer Engineering aan de University of Michigan Ann Arbor. Hij is momenteel een Ph.D. kandidaat in Computer Science aan de Stanford University. Enkele van zijn onderzoeksinteresses omvatten de linkstructuur van het web, menselijke computerinteractie, zoekmachines, schaalbaarheid van interfaces voor informatie-toegang en persoonlijke datamining.
8 Bijlage A: Reclame en gemengde motieven
Het overheersende bedrijfsmodel voor commerciële zoekmachines is momenteel reclame. De doelstellingen van het bedrijfsmodel voor reclame komen niet altijd overeen met het bieden van kwaliteitsonderzoek aan gebruikers. In onze prototype-zoekmachine is een van de beste resultaten voor mobiele telefoons bijvoorbeeld ' Het effect van mobiel telefoongebruik op bestuurdersattentie ', een onderzoek waarin de afleiding en het risico van het bellen op een mobiele telefoon tot in detail worden uitgelegd. Dit zoekresultaat kwam als eerste naar voren vanwege het grote belang ervan, beoordeeld aan de hand van het PageRank-algoritme, een benadering van het belang van citatie op het web [ Pagina, 98]. Het is duidelijk dat een zoekmachine die geld aan het nemen was voor het weergeven van mobiele-telefoonadvertenties, moeite zou hebben om de pagina te rechtvaardigen die ons systeem aan zijn betalende adverteerders heeft teruggegeven. Om dit type reden en historische ervaring met andere media [ Bagdikian 83 ] verwachten we dat door advertenties gefinancierde zoekmachines inherent bevooroordeeld zijn jegens de adverteerders en weg van de behoeften van de consumenten.Omdat het erg moeilijk is, zelfs voor experts om zoekmachines te evalueren, is het vooroordeel van zoekmachines bijzonder verraderlijk. Een goed voorbeeld was OpenText, dat naar verluidt de verkoop van bedrijven het recht gaf om aan de top van de zoekresultaten te worden vermeld voor specifieke vragen [ Marchiori 97]. This type of bias is much more insidious than advertising, because it is not clear who "deserves" to be there, and who is willing to pay money to be listed. This business model resulted in an uproar, and OpenText has ceased to be a viable search engine. But less blatant bias are likely to be tolerated by the market. For example, a search engine could add a small factor to search results from "friendly" companies, and subtract a factor from results from competitors. This type of bias is very difficult to detect but could still have a significant effect on the market. Furthermore, advertising income often provides an incentive to provide poor quality search results. For example, we noticed a major search engine would not return a large airline's homepage when the airline's name was given as a query. It so happened that the airline had placed an expensive ad, linked to the query that was its name. A better search engine would not have required this ad, and possibly resulted in the loss of the revenue from the airline to the search engine. In general, it could be argued from the consumer point of view that the better the search engine is, the fewer advertisements will be needed for the consumer to find what they want. This of course erodes the advertising supported business model of the existing search engines. However, there will always be money from advertisers who want a customer to switch products, or have something that is genuinely new. But we believe the issue of advertising causes enough mixed incentives that it is crucial to have a competitive search engine that is transparent and in the academic realm.
9 Appendix B: Scalability
9. 1 Scalability of Google
We hebben Google zo ontworpen dat het op korte termijn schaalbaar is naar een doel van 100 miljoen webpagina's. We hebben zojuist schijf en machines ontvangen om ongeveer dat bedrag te verwerken. Alle tijdrovende delen van het systeem zijn parallel en ongeveer lineaire tijd. Hieronder vallen zaken als de crawlers, indexeerders en sorteerders. We denken ook dat de meeste datastructuren sierlijk omgaan met de uitbreiding. Op 100 miljoen webpagina's zullen we echter zeer close zijn tegen allerlei soorten besturingssysteemlimieten in de algemene besturingssystemen (momenteel draaien we zowel op Solaris als Linux). Deze omvatten zaken als adresseerbaar geheugen, aantal open bestandsbeschrijvingen, netwerkaansluitingen en bandbreedte en vele andere. We denken dat het uitbreiden van meer dan 100 miljoen pagina's de complexiteit van ons systeem aanzienlijk zou vergroten.9.2 Scalability of Centralized Indexing Architectures
Naarmate de mogelijkheden van computers toenemen, wordt het mogelijk om een zeer grote hoeveelheid tekst te indexeren voor een redelijke prijs. Natuurlijk zullen andere, meer bandbreedte-intensieve media zoals video waarschijnlijk alomtegenwoordiger worden. Maar omdat de productiekosten van tekst laag zijn in vergelijking met media zoals video, blijft de tekst waarschijnlijk zeer doordringend. Het is ook waarschijnlijk dat we binnenkort spraakherkenning zullen hebben die een redelijke klus is om spraak in tekst om te zetten, waardoor de hoeveelheid beschikbare tekst wordt uitgebreid. Dit alles biedt geweldige mogelijkheden voor gecentraliseerde indexering. Hier is een illustratief voorbeeld. We gaan ervan uit dat we alles willen indexeren wat iedereen in de VS een jaar heeft geschreven. We nemen aan dat er 250 miljoen mensen in de VS zijn en ze schrijven gemiddeld 10.000 per dag. Dat is ongeveer 850 terabytes. Stel ook dat het indexeren van een terabyte nu voor een redelijke prijs kan worden gedaan. We nemen ook aan dat de indexeringsmethoden die in de tekst worden gebruikt lineair of bijna lineair in hun complexiteit zijn. Met al deze aannames kunnen we berekenen hoe lang het zou duren voordat we onze 850 terabytes voor een redelijke prijs zouden indexeren, uitgaande van bepaalde groeifactoren. De wet van Moore werd in 1965 gedefinieerd als een verdubbeling om de 18 maanden in processorkracht. Het is opvallend waar geweest, niet alleen voor processors, maar ook voor andere belangrijke systeemparameters zoals disk. Als we aannemen dat de wet van Moore geldt voor de toekomst, hebben we slechts 10 verdubbelingen of 15 jaar nodig om ons doel te bereiken, namelijk het indexeren van alles wat iedereen in de VS een jaar lang heeft geschreven voor een prijs die een klein bedrijf zich kan veroorloven. Natuurlijk zijn hardware-experts enigszins bezorgd over Moore 'Of course a distributed systems like Gloss [Gravano 94] or Harvest will often be the most efficient and elegant technical solution for indexing, but it seems difficult to convince the world to use these systems because of the high administration costs of setting up large numbers of installations. Of course, it is quite likely that reducing the administration cost drastically is possible. If that happens, and everyone starts running a distributed indexing system, searching would certainly improve drastically.
Omdat mensen slechts een eindige hoeveelheid kunnen typen of spreken, en naarmate computers zich blijven verbeteren, zal het indexeren van teksten nog beter scoren dan nu het geval is. Natuurlijk kan er een oneindige hoeveelheid machinegegenereerde inhoud zijn, maar het indexeren van enorme hoeveelheden door de mens gegenereerde inhoud lijkt enorm nuttig. We zijn dan ook optimistisch dat onze gecentraliseerde webzoekmachine-architectuur zal verbeteren in zijn mogelijkheid om de relevante tekstinformatie in de loop van de tijd te behandelen en dat er een mooie toekomst is voor zoeken.
