Het gedrag van een webcrawler is het resultaat van een combinatie van beleidslijnen:
- een selectiebeleid dat aangeeft welke pagina’s moeten worden gedownload,
- een herhalingsbeleid dat aangeeft wanneer moet worden gecontroleerd op wijzigingen in de pagina’s,
- een beleefdheidsbeleid dat aangeeft hoe overbelasting van websites moet worden voorkomen.
- een parallellisatiebeleid dat aangeeft hoe gedistribueerde webcrawlers moeten worden gecoördineerd.
SelectiebeleidEdit
Gezien de huidige omvang van het web, bestrijken zelfs grote zoekmachines slechts een deel van het publiek beschikbare deel. Een studie uit 2009 toonde aan dat zelfs grootschalige zoekmachines niet meer dan 40-70% van het indexeerbare web indexeren; een eerdere studie van Steve Lawrence en Lee Giles toonde aan dat geen enkele zoekmachine in 1999 meer dan 16% van het web indexeerde. Aangezien een crawler altijd slechts een fractie van de webpagina’s downloadt, is het zeer wenselijk dat de gedownloade fractie de meest relevante pagina’s bevat en niet slechts een willekeurige steekproef van het Web.
Dit vereist een metriek van belang voor het prioriteren van webpagina’s. Het belang van een pagina is een functie van zijn intrinsieke kwaliteit, zijn populariteit in termen van links of bezoeken, en zelfs van zijn URL (dit laatste is het geval bij verticale zoekmachines die zich beperken tot een enkel topleveldomein, of bij zoekmachines die zich beperken tot een vaste website). Het ontwerpen van een goed selectiebeleid heeft een extra moeilijkheid: het moet werken met gedeeltelijke informatie, omdat de complete set webpagina’s niet bekend is tijdens het crawlen.
Junghoo Cho et al. deden de eerste studie naar beleid voor crawling scheduling. Hun dataset bestond uit een crawl van 180.000 pagina’s van het domein stanford.edu, waarbij een crawling-simulatie werd gedaan met verschillende strategieën. De geteste ordeningsmetrieken waren breadth-first, backlink count en gedeeltelijke PageRank berekeningen. Een van de conclusies was dat als de crawler pagina’s met een hoge Pagerank vroeg tijdens het crawl proces wil downloaden, de gedeeltelijke Pagerank strategie de beste is, gevolgd door breadth-first en backlink-count. Deze resultaten zijn echter voor slechts één domein. Cho schreef ook zijn proefschrift aan Stanford over web crawling.
Najork en Wiener voerden een echte crawl uit op 328 miljoen pagina’s, waarbij ze een breadth-first volgorde gebruikten. Zij vonden dat een breadth-first crawl pagina’s met een hoge Pagerank vroeg in de crawl vangt (maar zij vergeleken deze strategie niet met andere strategieën). De auteurs geven als verklaring voor dit resultaat dat “de belangrijkste pagina’s veel links van verschillende hosts hebben, en die links worden vroeg gevonden, ongeacht van welke host of pagina de crawl afkomstig is.”
Abiteboul ontwierp een crawlstrategie op basis van een algoritme dat OPIC (On-line Page Importance Computation) wordt genoemd. In OPIC krijgt elke pagina een initiële som “geld” die gelijk wordt verdeeld over de pagina’s waarnaar hij verwijst. Het is vergelijkbaar met een PageRank berekening, maar het is sneller en wordt slechts in één stap uitgevoerd. Een OPIC-gestuurde crawler downloadt eerst de pagina’s in de crawling frontier met een hoger bedrag aan “cash”. De experimenten werden uitgevoerd in een synthetische grafiek van 100.000 pagina’s met een power-law verdeling van in-links. Er was echter geen vergelijking met andere strategieën noch experimenten op het echte Web.
Boldi et al. gebruikten simulatie op subsets van het Web van 40 miljoen pagina’s van het .it domein en 100 miljoen pagina’s van de WebBase crawl, waarbij breadth-first tegen depth-first, random ordening en een omniscient strategie werden getest. De vergelijking was gebaseerd op hoe goed PageRank, berekend op een gedeeltelijke crawl, de echte PageRank waarde benadert. Verrassend genoeg leveren sommige bezoeken die PageRank zeer snel accumuleren (met name breadth-first en de omniscient visit) zeer slechte progressieve benaderingen op.
Baeza-Yates et al. gebruikten simulatie op twee subsets van het Web van 3 miljoen pagina’s van het .gr en .cl domein, waarbij ze verschillende crawlstrategieën testten. Zij toonden aan dat zowel de OPIC-strategie als een strategie die gebruik maakt van de lengte van de wachtrijen per site beter zijn dan breadth-first crawling, en dat het ook zeer effectief is om een eerdere crawl, als die beschikbaar is, te gebruiken om de huidige te begeleiden.
Daneshpajouh et al. ontwierpen een community-based algoritme voor het ontdekken van goede seeds. Hun methode crawls webpagina’s met een hoge PageRank uit verschillende gemeenschappen in minder iteratie in vergelijking met crawl starten vanuit willekeurige zaden. Men kan halen goed zaad van een eerder-crawled-Web grafiek met behulp van deze nieuwe methode. Met behulp van deze zaden kan een nieuwe crawl zeer effectief zijn.
Volgde links beperkenEdit
Een crawler wil misschien alleen HTML-pagina’s zoeken en alle andere MIME-typen vermijden. Om alleen HTML-bronnen op te vragen, kan een crawler een HTTP HEAD-aanvraag doen om het MIME-type van een webbron te bepalen voordat de hele bron met een GET-aanvraag wordt opgevraagd. Om te voorkomen dat er veel HEAD-aanvragen worden gedaan, kan een crawler de URL onderzoeken en alleen een bron aanvragen als de URL eindigt met bepaalde tekens, zoals .html, .htm, .asp, .aspx, .php, .jsp, .jspx of een schuine streep. Deze strategie kan ertoe leiden dat talrijke HTML-webbronnen onbedoeld worden overgeslagen.
Sommige crawlers zullen ook vermijden bronnen op te vragen waar een “?” in voorkomt (dynamisch worden geproduceerd) om spider traps te vermijden die ertoe kunnen leiden dat de crawler een oneindig aantal URL’s van een website downloadt. Deze strategie is onbetrouwbaar als de site URL-herschrijving gebruikt om zijn URL’s te vereenvoudigen.
URL-normalisatieEdit
Crawlers voeren meestal een vorm van URL-normalisatie uit om te voorkomen dat ze dezelfde bron meer dan eens crawlen. De term URL-normalisatie, ook wel URL-canonicalisatie genoemd, verwijst naar het proces van het wijzigen en standaardiseren van een URL op een consistente manier. Er zijn verschillende soorten normalisatie die kunnen worden uitgevoerd, waaronder het omzetten van URL’s naar kleine letters, het verwijderen van “.” en “…” segmenten, en het toevoegen van slashes aan de niet-lege padcomponent.
Path-ascending crawlingEdit
Sommige crawlers hebben de intentie om zoveel mogelijk bronnen van een bepaalde website te downloaden/uploaden. Daarom is er een pad-klimmende crawler geïntroduceerd die naar elk pad in elke URL klimt die hij wil crawlen. Bijvoorbeeld, wanneer een seed URL http://llama.org/hamster/monkey/page.html, zal het proberen om /hamster/monkey/, /hamster/, en / te crawlen. Cothey ontdekte dat een pad-klimmende crawler zeer effectief was in het vinden van geïsoleerde bronnen, of bronnen waarvoor geen inkomende link zou zijn gevonden in reguliere crawling.
Gericht crawlenEdit
Het belang van een pagina voor een crawler kan ook worden uitgedrukt als een functie van de gelijkenis van een pagina met een bepaalde query. Webcrawlers die proberen om pagina’s te downloaden die op elkaar lijken, worden focused crawler of topical crawlers genoemd. De concepten topical en focused crawling zijn voor het eerst geïntroduceerd door Filippo Menczer en door Soumen Chakrabarti et al.
Het belangrijkste probleem bij focused crawling is dat we in de context van een webcrawler de overeenkomst van de tekst van een gegeven pagina met de query willen kunnen voorspellen voordat we de pagina daadwerkelijk downloaden. Een mogelijke voorspeller is de ankertekst van links; dit was de aanpak van Pinkerton in de eerste webcrawler uit de begindagen van het Web. Diligenti e.a. stellen voor de volledige inhoud van de reeds bezochte pagina’s te gebruiken om de overeenkomst af te leiden tussen de zoekopdracht en de pagina’s die nog niet zijn bezocht. De prestatie van een gerichte crawling hangt vooral af van de rijkdom aan links in het specifieke onderwerp dat wordt doorzocht, en een gerichte crawling vertrouwt gewoonlijk op een algemene Web-zoekmachine voor het verschaffen van uitgangspunten.
Academic-focused crawlerEdit
Een voorbeeld van de gerichte crawlers zijn academische crawlers, die vrij toegankelijke academisch gerelateerde documenten crawlen, zoals de citeseerxbot, die de crawler is van de CiteSeerX-zoekmachine. Andere academische zoekmachines zijn Google Scholar en Microsoft Academic Search enz. Omdat de meeste academische papers in PDF-formaat worden gepubliceerd, is zo’n crawler vooral geïnteresseerd in het crawlen van PDF, PostScript-bestanden, Microsoft Word en hun gezipte formaten. Daarom moeten algemene open source crawlers, zoals Heritrix, worden aangepast om andere MIME-types uit te filteren, of er wordt een middleware gebruikt om deze documenten eruit te halen en ze te importeren in de gerichte crawldatabase en repository. Identificeren of deze documenten academisch zijn of niet is een uitdaging en kan een aanzienlijke overhead toevoegen aan het crawlproces, dus dit wordt uitgevoerd als een post-crawlproces met behulp van machine learning of reguliere expressiealgoritmen. Deze academische documenten worden meestal verkregen van homepages van faculteiten en studenten of van publicatiepagina’s van onderzoeksinstituten. Omdat academische documenten slechts een klein deel van alle webpagina’s beslaan, is een goede zaadselectie belangrijk om de efficiëntie van deze webcrawlers te verhogen. Andere academische crawlers kunnen platte tekst- en HTML-bestanden downloaden, die metadata van academische papers bevatten, zoals titels, papers en abstracts. Dit verhoogt het totale aantal papers, maar een aanzienlijk deel biedt geen gratis PDF-downloads.
Semantisch gerichte crawlerEdit
Een ander type gerichte crawlers is de semantisch gerichte crawler, die gebruikmaakt van domeinontologieën om topical maps weer te geven en webpagina’s te koppelen aan relevante ontologische concepten voor de selectie en categorisatiedoeleinden. Bovendien kunnen ontologieën automatisch worden bijgewerkt tijdens het crawlingproces. Dong et al. introduceerden zo’n ontology-learning-based crawler die gebruik maakt van support vector machine om de inhoud van ontologische concepten bij te werken tijdens het crawlen van Web Pages.
Re-visit policyEdit
Het Web heeft een zeer dynamisch karakter, en het crawlen van een fractie van het Web kan weken of maanden duren. Tegen de tijd dat een webcrawler klaar is met zijn crawl, kunnen er al veel gebeurtenissen hebben plaatsgevonden, waaronder creaties, updates en verwijderingen.
Vanuit het oogpunt van de zoekmachine zijn er kosten verbonden aan het niet detecteren van een gebeurtenis, en dus aan het hebben van een verouderde kopie van een bron. De meest gebruikte kostenfuncties zijn versheid en ouderdom.
Versheid: Dit is een binaire maat die aangeeft of de lokale kopie accuraat is of niet. De versheid van een pagina p in het archief op tijdstip t is gedefinieerd als:
F p ( t ) = { 1 i if p i s e q u a l t o e p a s s i n g t 0 o o k w i s e {\displaystyle F_{p}(t)={\begin{cases}1&{\rm {if}}~p~{\rm {~is~equal~to~the~local~copy~at~time}}~t\\0&{\rm {otherwise}}\end{cases}}}
Age: Dit is een maat die aangeeft hoe verouderd de lokale kopie is. De leeftijd van een pagina p in het archief, op tijdstip t, is gedefinieerd als:
A p ( t ) = { 0 als p niet op tijdstip t – m o d i f i c a t i e v a n p o t h e r w i s e {\displaystyle A_{p}(t)={\begin{cases}0&{\rm {if}~p~{\rm {~is~niet~gewijzigd~op~tijd}}~t{\t-{{rm {gewijzigd~op~tijd}~p&{{rm {anders}}}
Coffman et al. werkten met een definitie van de doelstelling van een webcrawler die gelijkwaardig is aan versheid, maar gebruikten een andere formulering: zij stelden voor dat een crawler de fractie van de tijd dat pagina’s verouderd zijn moet minimaliseren. Zij merkten ook op dat het probleem van Web crawling kan worden gemodelleerd als een multiple-queue, single-server polling system, waarbij de Web crawler de server is en de Web sites de queues. Paginawijzigingen zijn de aankomst van de klanten, en wisseltijden zijn het interval tussen paginatoegangen naar een enkele website. In dit model is de gemiddelde wachttijd voor een klant in het pollingsysteem gelijk aan de gemiddelde leeftijd voor de webcrawler.
Het doel van de crawler is de gemiddelde versheid van de pagina’s in zijn verzameling zo hoog mogelijk te houden, of de gemiddelde leeftijd van de pagina’s zo laag mogelijk te houden. Deze doelstellingen zijn niet gelijkwaardig: in het eerste geval gaat het de crawler alleen om hoeveel pagina’s verouderd zijn, terwijl het in het tweede geval de crawler erom gaat hoe oud de lokale kopieën van pagina’s zijn.
Twee eenvoudige herbezichtigingsbeleidslijnen werden bestudeerd door Cho en Garcia-Molina:
- Uniform beleid: Hierbij worden alle pagina’s in de collectie even vaak opnieuw bezocht, ongeacht de mate van verandering.
- Proportioneel beleid: Hierbij worden de pagina’s die vaker veranderen vaker opnieuw bezocht. De bezoekfrequentie is recht evenredig met de (geschatte) veranderingsfrequentie.
In beide gevallen kan de herhaalde crawlvolgorde van pagina’s zowel in een willekeurige als in een vaste volgorde plaatsvinden.
Cho en Garcia-Molina bewezen het verrassende resultaat dat, in termen van gemiddelde versheid, het uniforme beleid beter presteert dan het proportionele beleid, zowel in een gesimuleerd web als in een echte webcrawl. Intuïtief is de redenering dat, aangezien webcrawlers een limiet hebben op het aantal pagina’s dat zij in een bepaald tijdsbestek kunnen crawlen, (1) zij te veel nieuwe crawls zullen toewijzen aan snel veranderende pagina’s ten koste van minder frequent veranderende pagina’s, en (2) de versheid van snel veranderende pagina’s korter duurt dan die van minder frequent veranderende pagina’s. Met andere woorden, een proportioneel beleid wijst meer middelen toe aan het crawlen van vaak bijgewerkte pagina’s, maar ondervindt minder totale versheidstijd van hen.
Om de versheid te verbeteren, moet de crawler de elementen straffen die te vaak veranderen. Het optimale her-bezoek-beleid is noch het uniforme beleid, noch het proportionele beleid. De optimale methode om de gemiddelde versheid hoog te houden omvat het negeren van de pagina’s die te vaak veranderen, en de optimale methode om de gemiddelde ouderdom laag te houden is het gebruik van toegangsfrequenties die monotoon (en sub-lineair) toenemen met de veranderingssnelheid van elke pagina. In beide gevallen ligt het optimum dichter bij het uniforme beleid dan bij het proportionele beleid: zoals Coffman et al. opmerken, “om de verwachte verouderingstijd zo klein mogelijk te houden, moeten de toegangen tot een bepaalde pagina zo gelijkmatig mogelijk gespreid worden”. Expliciete formules voor het herbezoekbeleid zijn in het algemeen niet haalbaar, maar ze worden wel numeriek verkregen, aangezien ze afhangen van de verdeling van de paginawijzigingen. Cho en Garcia-Molina tonen aan dat de exponentiële verdeling goed geschikt is om paginaveranderingen te beschrijven, terwijl Ipeirotis et al. laten zien hoe statistische hulpmiddelen kunnen worden gebruikt om parameters te ontdekken die deze verdeling beïnvloeden. Merk op dat de hier beschouwde re-visiting policies alle pagina’s als homogeen beschouwen in termen van kwaliteit (“alle pagina’s op het Web zijn hetzelfde waard”), iets wat geen realistisch scenario is, dus er zou meer informatie over de kwaliteit van de webpagina moeten worden opgenomen om tot een beter crawlingbeleid te komen.
PolitiekbeleidEdit
Crawlers kunnen veel sneller en diepgaander gegevens opvragen dan menselijke zoekers, zodat ze een verlammende invloed kunnen hebben op de prestaties van een site. Als een enkele crawler meerdere verzoeken per seconde uitvoert en/of grote bestanden downloadt, kan een server het moeilijk krijgen om de verzoeken van meerdere crawlers bij te houden.
Zoals Koster opmerkt, is het gebruik van webcrawlers nuttig voor een aantal taken, maar komt het met een prijs voor de algemene gemeenschap. De kosten van het gebruik van Web crawlers omvatten:
- netwerkbronnen, aangezien crawlers aanzienlijke bandbreedte vereisen en gedurende een lange periode met een hoge mate van parallellisme werken;
- serveroverbelasting, vooral als de frequentie van toegang tot een bepaalde server te hoog is;
- slecht geschreven crawlers, die servers of routers kunnen laten crashen, of die pagina’s downloaden die ze niet aankunnen; en
- persoonlijke crawlers die, als ze door te veel gebruikers worden ingezet, netwerken en webservers kunnen ontregelen.
Een gedeeltelijke oplossing voor deze problemen is het robots exclusion protocol, ook bekend als het robots.txt protocol, dat een standaard is voor beheerders om aan te geven welke delen van hun webservers niet door crawlers mogen worden geraadpleegd. Deze standaard bevat geen suggestie voor het interval tussen bezoeken aan dezelfde server, ook al is dit interval de meest effectieve manier om overbelasting van de server te voorkomen. Sinds kort kunnen commerciële zoekmachines als Google, Ask Jeeves, MSN en Yahoo! Search een extra “Crawl-delay:” parameter in het robots.txt bestand gebruiken om het aantal seconden aan te geven dat tussen verzoeken moet worden gewacht.
Het eerste voorgestelde interval tussen opeenvolgende pageloads was 60 seconden. Als echter in dit tempo pagina’s zouden worden gedownload van een website met meer dan 100.000 pagina’s via een perfecte verbinding met nul latency en oneindige bandbreedte, zou het meer dan 2 maanden duren om alleen die hele website te downloaden; ook zou dan slechts een fractie van de bronnen van die webserver worden gebruikt. Dit lijkt niet acceptabel.
Cho gebruikt 10 seconden als interval voor de toegang, en de WIRE crawler gebruikt 15 seconden als standaard. De crawler van MercatorWeb volgt een adaptief beleefdheidsbeleid: als het t seconden heeft geduurd om een document van een bepaalde server te downloaden, wacht de crawler 10t seconden voordat hij de volgende pagina downloadt. Dill et al. gebruiken 1 seconde.
Voor degenen die webcrawlers voor onderzoeksdoeleinden gebruiken, is een meer gedetailleerde kosten-batenanalyse nodig en moet rekening worden gehouden met ethische overwegingen bij de beslissing waar te crawlen en hoe snel te crawlen.
Anecdotisch bewijs uit de toegangslogs laat zien dat de toegangsintervallen van bekende crawlers variëren tussen 20 seconden en 3-4 minuten. Het is de moeite waard op te merken dat zelfs wanneer men zeer beleefd is, en alle voorzorgsmaatregelen neemt om overbelasting van webservers te voorkomen, er toch klachten van webserverbeheerders binnenkomen. Brin en Page merken op dat: “… het uitvoeren van een crawler die verbinding maakt met meer dan een half miljoen servers (…) een behoorlijke hoeveelheid e-mail en telefoontjes genereert. Vanwege het grote aantal mensen dat online komt, zijn er altijd mensen die niet weten wat een crawler is, omdat dit de eerste is die ze zien.”
ParallelisatiebeleidEdit
Een parallelle crawler is een crawler die meerdere processen parallel uitvoert. Het doel is om de downloadsnelheid te maximaliseren terwijl de overhead van parallellisatie wordt geminimaliseerd en om herhaalde downloads van dezelfde pagina te voorkomen. Om te voorkomen dat dezelfde pagina meer dan eens wordt gedownload, heeft het crawling-systeem een beleid nodig voor het toewijzen van de nieuwe URL’s die tijdens het crawling-proces worden ontdekt, omdat dezelfde URL door twee verschillende crawling-processen kan worden gevonden.