資源描述:
《外文翻譯基于網(wǎng)絡(luò)爬蟲的有效url緩存》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、外文原文EfficientURLCachingforWorldWideWebCrawlingAndreiZ.BroderIBMTJWatsonResearchCenter19SkylineDrHawthorne,NY10532abroder@us.ibm.comMarcNajorkMicrosoftResearch1065LaAvenidaMountainView,CA94043najork@microsoft.comJanetL.WienerHewlettPackardLabs1501PageMillRoadPaloAlto,CA94304janet.wiener@hp.com
2、ABSTRACTCrawlingthewebisdeceptivelysimple:thebasicalgorithmis(a)Fetchapage(b)ParseittoextractalllinkedURLs(c)ForalltheURLsnotseenbefore,repeat(a)–(c).However,thesizeoftheweb(estimatedatover4billionpages)anditsrateofchange(estimatedat7%perweek)movethisplanfromatrivialprogrammingexercisetoaseri
3、ousalgorithmicandsystemdesignchallenge.Indeed,thesetwofactorsaloneimplythatforareasonablyfreshandcompletecrawloftheweb,step(a)mustbeexecutedaboutathousandtimespersecond,andthusthemembershiptest(c)mustbedonewellovertenthousandtimespersecondagainstasettoolargetostoreinmainmemory.Thisrequiresadi
4、stributedarchitecture,whichfurthercomplicatesthemembershiptest.Acrucialwaytospeedupthetestistocache,thatis,tostoreinmainmemorya(dynamic)subsetofthe“seen”URLs.ThemaingoalofthispaperistocarefullyinvestigateseveralURLcachingtechniquesforwebcrawling.Weconsiderbothpracticalalgorithms:randomreplace
5、ment,staticcache,LRU,andCLOCK,andtheoreticallimits:clairvoyantcachingandinfinitecache.Weperformedabout1,800simulationsusingthesealgorithmswithvariouscachesizes,usingactuallogdataextractedfromamassive33daywebcrawlthatissuedoveronebillionHTTPrequests.Ourmainconclusionisthatcachingisveryeffectiv
6、e–inoursetup,acacheofroughly50,000entriescanachieveahitrateofalmost80%.Interestingly,thiscachesizefallsatacriticalpoint:asubstantiallysmallercacheismuchlesseffectivewhileasubstantiallylargercachebringslittleadditionalbenefit.Weconjecturethatsuchcriticalpointsareinherenttoourproblemandventurea
7、nexplanationforthisphenomenon.1.INTRODUCTIONArecentPewFoundationstudy[31]statesthat“SearchengineshavebecomeanindispensableutilityforInternetusers”andestimatesthatasofmid-2002,slightlyover50%ofallAmericanshaveusedwebsearchtofindinformation.Hen