5-搜索引擎.ppt
LOGOWeb Mining(5)杨光飞杨光飞系统工程研究所系统工程研究所大连理工大学大连理工大学SearchEngineLOGO搜索引擎概况搜索引擎概况LOGOThesearchenginerankingsforJanuary2012,accordingtocomScore,were:Googlegrewto66.2percent(upfrom65.9percentinDecember2011).Binggrewto15.2percent(upfrom15.1percent).Yahoofellto14.1percent(downfrom14.5percent).Askgrewto3percent(upfrom2.9percent).AOLremainedunchangedat1.6percent.LOGOSearch Engine CharacteristicsUneditedanyonecanentercontentQualityissues;SpamVariedinformationtypesPhonebook,brochures,catalogs,dissertations,newsreports,weather,allinoneplace!DifferentkindsofusersLexis-Nexis:Paying,professionalsearchersOnlinecatalogs:ScholarssearchingscholarlyliteratureWeb:EverytypeofpersonwitheverytypeofgoalScaleHundredsofmillionsofsearches/day;billionsofdocsLOGOWeb Search QueriesWebsearchqueriesareshort:2.4wordsonaverage(Aug2000)Hasincreased,was1.7(1997)UserExpectations:Manysay“ThefirstitemshownshouldbewhatIwanttosee!”Thisworksiftheuserhasthemostpopular/commonnotioninmind,nototherwise.LOGOStandard Web Search Engine Architecturecrawl thewebcreate an invertedindexCheck for duplicates,store the documentsInvertedindexSearchengineserversuserqueryShow results To userDocIdsLOGOLOGOBrin&Page 98LOGOInverted IndexesInvertedindexesarestillused,eventhoughthewebissohugeSomesystemspartitiontheindexesacrossdifferentmachines;eachmachinehandlesdifferentpartsofthedataOthersystemsduplicatethedataacrossmanymachines;queriesaredistributedamongthemachinesMostdoacombinationoftheseLOGOInthisexample,thedataforthepagesispartitionedacrossmachines.Additionally,eachpartitionisallocatedmultiplemachinestohandlethequeries.Eachrowcanhandle120queriespersecondEachcolumncanhandle7MpagesTohandlemorequeries,addanotherrow.LOGOHow Inverted Files Are CreatedPeriodicallyrebuilt,staticotherwise.Documentsareparsedtoextracttokens.ThesearesavedwiththeDocumentID.NowisthetimeforallgoodmentocometotheaidoftheircountryDoc1Itwasadarkandstormynightinthecountrymanor.ThetimewaspastmidnightDoc2LOGOHow Inverted Files are CreatedAfteralldocumentshavebeenparsedtheinvertedfileissortedalphabetically.LOGOHow InvertedFiles are CreatedMultipletermentriesforasingledocumentaremerged.Within-documenttermfrequencyinformationiscompiled.LOGOLOGOGoogles IndexingTheIndexer convertseachdocintoacollectionof“hitlists”andputstheseinto“barrels”,sortedbydocID.Italsocreatesadatabaseof“links”.Hit:Hittype:Plainorfancy.Fancyhit:OccursinURL,title,anchortext,metatag.Optimizedrepresentationofhits(2byteseach).Sorter sortseachbarrelbywordIDtocreatetheinvertedindex.Italsocreatesalexiconfile.Lexicon:Lexiconismostlycachedin-memoryLOGOwordid#docswordid#docswordid#docsLexicon(in-memory)Postings(“Invertedbarrels”,ondisk)Each“barrel”containspostingsforarangeofwordids.Googles Inverted IndexSortedbywordidDocid#hitsHit,hit,hit,hit,hitDocid#hitsHitDocid#hitsHitDocid#hitsHit,hit,hitDocid#hitsHit,hitBarreliBarreli+1SortedbyDocidLOGOGoogleSortedbarrels=invertedindexPagerankcomputedfromlinkstructure;combinedwithIRrankIRrankdependsonTF,typeof“hit”,hitproximity,etc.BilliondocumentsHundredmillionqueriesadayANDqueriesLOGOLink Analysis for Ranking PagesWhydoesthiswork?TheofficialToyotasitewillbelinkedtobylotsofotherofficial(orhigh-quality)sitesThebestToyotafan-clubsiteprobablyalsohasmanylinkspointingtoitLesshigh-qualitysitesdonothaveasmanyhigh-qualitysiteslinkingtothemLOGOPageRankLetA1,A2,AnbethepagesthatpointtopageA.LetC(P)bethe#linksoutofpageP.ThePageRank(PR)ofpageAisdefinedas:PageRankisprincipaleigenvectorofthelinkmatrixoftheweb.Canbecomputedasthefixpointoftheaboveequation.PR(A)=(1-d)+d(PR(A1)/C(A1)+PR(An)/C(An)LOGOPageRank:User ModelPageRanksformaprobabilitydistributionoverwebpages:sumofallpagesranksisone.Usermodel:“Randomsurfer”selectsapage,keepsclickinglinks(never“back”),until“bored”:thenrandomlyselectsanotherpageandcontinues.PageRank(A)istheprobabilitythatsuchauservisitsAdistheprobabilityofgettingboredatapageGooglecomputesrelevanceofapageforagivensearchbyfirstcomputinganIRrelevanceandthenmodifyingthatbytakingintoaccountPageRankforthetoppages.LOGO闲话闲话GoogleLOGO名称渊源名称渊源1938年，美国数学家爱德华卡斯纳Edward Kasner想发明一个单词来表示“10的100次方”这样一个庞大的数字，于是就征询9岁的小侄子米尔顿Sirotta的意见。小米尔顿认真地思索了几分钟，脑子里冒出了一个词googol，叔侄两人击节叫好。10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000LOGO1998年9月7日，24岁的布林和25岁的佩奇决定合伙开个公司，公司提供的唯一服务就是搜索引擎。Google的定位信息处理及分享标志着一个新时代的开始：这意味着信息开始像石油、钢铁一样成为一种资源，也注定了其商业模式不会等同于软件公司。LOGOGoogle搜索引擎源于拉里佩奇和谢尔盖布林在斯坦福大学读书时所做的一个研究项目。更确切地说，他们最开始是在佩奇简陋的宿舍搞研究，没多久搬到车库。两人1995年在斯坦福大学念计算科学博士学位而相识他们开发了一个对网站之间的关系做精确分析为基础的搜寻引擎，他的使用结果上胜于当时使用的基本搜索技术。当时项目被称作BackRub因为系统需要检查backlinks（反向链接）去估计站点的重要性。LOGOPageRank(网页级别)是Google排名运算法则（排名公式）的一部分，是Google用于用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升，从而提高搜索结果的相关性和质量。通过对由超过 50,000 万个变量和 20 亿个词汇组成的方程进行计算，PageRank 能够对网页的重要性做出客观的评价。PageRank 并不计算直接链接的数量，而是将从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票。这样，PageRank 会根据网页 B 所收到的投票数量来评估该页的重要性。LOGOGoogle全球99%的收入都来自网络广告产品AdWords和AdSense。GoogleAdSense，也就是通过为谷歌的广告客户提供广告位获取分成。由于谷歌右栏的赞助商广告平台狭小，不能完全满足广告商的需求，于是Google开发了AdSense，通过这套系统，谷歌能把广告商的广告分配到其他的中小网站上，被分配到这些广告的网站会因为展示或者吸引了顾客下载、注册而获得广告分成。当然，谷歌必须保证分配出去的广告与网站的内容是相匹配的，不会把咖啡广告分配给一个软件下载网站。LOGODont be evil不作恶让Google始终保持反思意识A healthy disregard for the impossible对不可能之事持一种健康的漠视让Google保持着对破坏性创新保持着热情LOGOGoogle成为了硅谷唯一一家用期权招聘厨师的公司。多年来，Google每天为所有员工提供免费的三餐，以及免费的医疗、牙医、美发、洗衣、干衣等服 务；在Google的办公室里，随处可以找到免费的十几种巧克力豆和几十种饮料，台球桌、桌上足球、按摩椅散布于其间，员工可以带狗上班(猫还不行)，每 个员工还能获得100美元布置自己的空间(有人买了星球大战里的机器人R2D2和尤达大师的模型，有人则买了个红绿灯挂在自己脑袋上，还有人买了一座 英式电话厅)。虽然Google的薪水在硅谷并不算顶级，它仍有大量员工一天12小时以上待在办公室。Google员工有20%的自由时间做自己的事情，这也是Google创新思想的源泉，Google50%的产品都是有这20%的自由时间产生的。然而笔者通过研究发现，其实Google的创新不在于“自由”，而在于对创新的“管理”。LOGO
