天网搜索平台PARADISE

天网搜索平台PARADISE闫宏飞北京大学计算机系网络实验室2009/4/24信息检索前沿概述闫宏飞北京大学计算机系网络实验室2009/4/24345OutlineIssues:searchengineandwebminingGoal:FrameworkPrinciples:Relatedcomponents(照应任务各部分关联)Implementation:Achievements（应用成果）Casestudy（具体到一事）6SearchEngineandWebMiningCrawlingFull-textindexingRetrievingWebarchivingandMining7WebGraph:bowtieteapotModel:bagofwordsInfomall,CDAL:archivehistraceEvaluation:manualautomaticPlatform:proprietaryopen89OutlineMotivationtoBuildPARADISEDesignandImplementPARADISEResearchIssuesofConcern10Corpus(1/3)Shakespeare’scollectedworksAgzippedtar-file[2039k]http://www.cs.su.oz.au/~matty/Shakespeare/shakespeare.tar.gzRCV1,ReutersCorpusVolume1.oneyearofReutersnewswire1996-08-20to1997-08-19containsabout810,000ReutersEnglishLanguageNewsstories.requiresabout2.5GBforstorageoftheuncompressedfiles./data/reuters/reuters.html

11Corpus(2/3)CWT100GB,ChineseWebTestcollection2004年6月搜集，有5,712,710个网页，解压容量为90GB。CWT200GB2005年11月搜集，有37,482,913个网页，压缩容量为197GB/12Corpus(3/3)2008/10/1513Hardwareassumptionssymbol statistic values averageseektime 5ms=5x10−3sb transfertimeperbyte 0.02μs=2x10−8s processor’sclockrate 10−9sp lowleveloperation 0.01μs=10−8s(e.g.,compare&swapaword) sizeofmainmemory severalGB sizeofdiskspace 1TBormore14ReutersRCV1statisticssymbol statistic valueN documents 800,000L avg.#tokensperdoc 200M terms(=wordtypes) 400,000avg.#bytespertoken 6(incl.spaces/punct.)avg.#bytespertoken 4.5(withoutspaces/punct.)avg.#bytesperterm 7.5tokens 100,000,0004.5bytesperwordtokenvs.7.5bytesperwordtype:why?15DocumentsareparsedtoextractwordsandthesearesavedwiththeDocumentID.IdidenactJuliusCaesarIwaskilledi'theCapitol;Brutuskilledme.Doc1SoletitbewithCaesar.ThenobleBrutushathtoldyouCaesarwasambitiousDoc2Indexconstruction16KeystepAfteralldocumentshavebeenparsed,theinvertedfileissortedbyterms.Wefocusonthissortstep.Wehave100Mitemstosort.17ScalingindexconstructionIn-memoryindexconstructiondoesnotscale.Howcanweconstructanindexforverylargecollections?TakingintoaccountthehardwareconstraintsMemory,disk,speedetc.18Sort-basedIndexconstructionAswebuildtheindex,weparsedocsoneatatime.Whilebuildingtheindex,wecannoteasilyexploitcompressiontricks(youcan,butmuchmorecomplex)Thefinalpostingsforanytermareincompleteuntiltheend.At12bytesperpostingsentry,demandsalotofspaceforlargecollections.T=100,000,000inthecaseofRCV1So…wecandothisinmemoryin2008,buttypicalcollectionsaremuchlarger.E.g.NewYorkTimesprovidesindexof>150yearsofnewswireThus:Weneedtostoreintermediateresultsondisk.19Usethesamealgorithmfordisk?Canweusethesameindexconstructionalgorithmforlargercollections,butbyusingdiskinsteadofmemory?No:SortingT=100,000,000recordsondiskistooslow–toomanydiskseeks.Weneedanexternalsortingalgorithm.20BottleneckParseandbuildpostingsentriesonedocatatimeNowsortpostingsentriesbyterm(thenbydocwithineachterm)Doingthiswithrandomdiskseekswouldbetooslow–mustsortT=100MrecordsIfeverycomparisontook2diskseeks,andNitemscouldbesortedwithNlog2Ncomparisons,howlongwouldthistake?2112-byte(4+4+4)records(term,doc,freq).Thesearegeneratedasweparsedocs.Mustnowsort100Msuch12-byterecordsbyterm.DefineaBlock~10MsuchrecordsCaneasilyfitacoupleintomemory.Willhave10suchblockstostartwith.Basicideaofalgorithm:Accumulatepostingsforeachblock,sort,writetodisk.Thenmergetheblocksintoonelongsortedorder.BSBI:Blockedsort-basedIndexing(Sortingwithfewerdiskseeks)22BSBI:Blockedsort-basedIndexing23Remainingproblemwithsort-basedalgorithmOurassumptionwas:wecankeepthedictionaryinmemory.Weneedthedictionary(whichgrowsdynamically)inordertoimplementatermtotermIDmapping.Actually,wecouldworkwithterm,docIDpostingsinsteadoftermID,docIDpostings......butthenintermediatefilesbecomeverylarge.(Wewouldendupwithascalable,butveryslowindexconstructionmethod.)24SPIMI:

Single-passin-memoryindexingKeyidea1:Generateseparatedictionariesforeachblock–noneedtomaintainterm-termIDmappingacrossblocks.Keyidea2:Don’tsort.Accumulatepostingsinpostingslistsastheyoccur.Withthesetwoideaswecangenerateacompleteinvertedindexforeachblock.Theseseparateindexescanthenbemergedintoonebigindex.25

SPIMI-InvertMergingofblocksisanalogoustoBSBI.26DistributedindexingForweb-scaleindexing(don’ttrythisathome!):mustuseadistributedcomputingclusterIndividualmachinesarefault-proneCanunpredictablyslowdownorfailHowdoweexploitsuchapoolofmachines?27GoogledatacentersGoogledatacentersmainlycontaincommoditymachines.Datacentersaredistributedaroundtheworld.Estimate:atotalof1millionservers,3millionprocessors/cores(Gartner2007)Estimate:Googleinstalls100,000serverseachquarter.Basedonexpendituresof200–250milliondollarsperyearThiswouldbe10%ofthecomputingcapacityoftheworld!?!28GoogledatacentersIfinanon-fault-tolerantsystemwith1000nodes,eachnodehas99.9%uptime,whatistheuptimeofthesystem?Answer:37%Calculatethenumberofserversfailingperminuteforaninstallationof1millionservers.29DistributedindexingMaintainamastermachinedirectingtheindexingjob–considered“safe”.Breakupindexingintosetsof(parallel)tasks.Mastermachineassignseachtasktoanidlemachinefromapool.30ParalleltasksWewillusetwosetsofparalleltasksParsersInvertersBreaktheinputdocumentcorpusintosplitsEachsplitisasubsetofdocuments(correspondingtoblocksinBSBI/SPIMI)31ParsersMasterassignsasplittoanidleparsermachineParserreadsadocumentatatimeandemits(term,doc)pairsParserwritespairsintojpartitionsEachpartitionisforarangeofterms’firstletters(e.g.,a-f,g-p,q-z)–herej=3.Nowtocompletetheindexinversion32InvertersAninvertercollectsall(term,doc)pairs(=postings)foroneterm-partition.Sortsandwritestopostingslists33DataflowsplitsParserParserParserMastera-fg-pq-za-fg-pq-za-fg-pq-zInverterInverterInverterPostingsa-fg-pq-zassignassignMapphaseSegmentfilesReducephase34MapReduceTheindexconstructionalgorithmwejustdescribedisaninstanceofMapReduce.MapReduce(DeanandGhemawat2004)isarobustandconceptuallysimpleframeworkfordistributedcomputingwithouthavingtowritecodeforthedistributionpart.TheydescribetheGoogleindexingsystem(ca.2002)asconsistingofanumberofphases,eachimplementedinMapReduce.35MapReduceIndexconstructionwasjustonephase.Anotherphase:transformingaterm-partitionedindexintodocument-partitionedindex.Term-partitioned:onemachinehandlesasubrangeoftermsDocument-partitioned:onemachinehandlesasubrangeofdocumentsmostsearchenginesuseadocument-partitionedindex…betterloadbalancing,etc.36SchemaforindexconstructioninMapReduceSchemaofmapandreducefunctionsmap:input→list(k,v)reduce:(k,list(v))→outputInstantiationoftheschemaforindexconstructionmap:webcollection→list(termID,docID)reduce:(<termID1,list(docID)>,<termID2,list(docID)>,…)→(postingslist1,postingslist2,…)Exampleforindexconstructionmap:d2:Cdied.d1:Ccame,Cc’ed.→(<C,d2>,<died,d2>,<C,d1>,<came,d1>,<C,d1>,<c’ed,d1>reduce:(<C,(d2,d1,d1)>,<died,(d2)>,<came,(d1)>,<c’ed,(d1)>)→(<C,(d1:2,d2:1)>,<died,(d2:1)>,<came,(d1:1)>,<c’ed,(d1:1)>)37有几个问题需要解决很难找到合适的硬件设施，基于这些数据开展工作存储，运行，维护，….缺少处理这些数据的有效的软件工具分析，检索，评测，….如何维护有stateofarts算法的软件工具模块替换，功能测试，性能测试，…38智能中文搜索引擎技术研究及平台构建由一个平台,四个任务组成的.达到平台能够展示四个任务.平台是:一个开放式智能化中文搜索引擎平台任务是:构建适用于中文互联网的文本内容抽取系统及网页文本内容结构化分析基于内容的多媒体信息检索基于自然语言理解的查询分析基于用户属性挖掘的个性化检索/src/paradise/39PARADISEDesign

PlatformforApplying,ResearchingAndDevelopingIntelligentSearchEngineServersServersServersServersServersServersServersServersServersServersServersServersServersServersServersServersServersServersServersServersServersBareMetalMachinesAutomationClusterManagementToolsDatanodesTianwangjobsandevaluationjobs40PARADISE索引设计介绍41当前设计中的基本功能Usingfastersingle-passindexingHighlycompressedindexdiskdatastructuresVariouscompressalgorithm(*)Variousinvertindexfileformat(*)indexposition,freqvalueorimpactvalue(*)Indexfieldinformation,suchastitle,dateCachesupport(*)42下一步设计的功能Indexvariousdocumentformat，suchasword,pdf使用MapReduce等技术的索引多种切词的实现与处理增量索引与文档删除Termvector存储多segment的合并策略43InvertedindexDocument-sortedindexThepointersineachinvertedlistarestoredinincreasingdocumentorderUsingd-gapFrequency-sortedindexInvertedlistarestoredindecreasingtermfrequencyscoreImpact-sortedindexThepointersareorderedaccordingtotheimpactvalueImpactvalueisasmallintegerrepresentingtheoverallcontributionoftermttothescoreofdocumentd,includethefactorusedtonormalizefordocumentlength44ProcessingquerymodeDocument-at-a-timeAllinvertedlistsaresimultaneouslyaccessed|q|-wayprocessingiscarriedouttohandleaqueryqof|q|termsTerm-at-a-timeOnlyoninvertedlistisaccessedatanygiventimeAsequenceof|q|-1binaryoperationsareperformedNotclearbetterthandocument-at-a-timeprocessingScore-at-a-timeAllofthetermlistsareopenforreadingProcessedindecreasingscorecontributionorderratherthaninincreasingdocumentnumberorderDynamicquerypruning45IndexlevelsDocumentnumbersonlyOnlysupportBooleanqueriesDocumentnumbersandScoreScorecanbeimpactscoresorfrequentorbothSupportBooleanandrankedqueriesDocumentnumbers,Score,PositionsSupportBoolean,ranked,phrase(proximityqueries)46TypesofindexandsupportquerymodestypedsposOrganizationProcessingmodesupportedDY--Document-sortTermordoc–at-a-timeDSYY-Document-sortImpactorfreq-sortTermordoc–at-a-timeDSPYYYDocument-sortedTermordoc-at-a-timescore-at-a-time47InterleavingPointerinterleavingEachdocumentnumberisimmediatelyfollowedbythecorrespondingworfvalueorposvalueTerminterleavingKeepvariousrelatedpartsofeachinvertedlistincontiguousblocsNon-interleavingUsingseparateinvertedfileEachstoringaparticulartypeofinformationFordistinctdiskpointersmaintainedineachentryinthedictionary48Block-interleavedindexesEachinvertedlistisbuiltupasasequenceofoneormoregroupsWithineachgrouptherearefourormorek-blocks49Cache是一个工具包，为一些模块提供cache功能Cahce策略与存储分开有多种cahce策略 当前实现MRU策略多种存储策略基于STLmap采用模板实现，保证其通过性50DocumentThelogicalrepresentationofaDocumentforindexingandsearchingADocumentisacollectionofFieldablesAFieldableisalogicalrepresentationofauser'scontentthatneedstobeindexedorstoredFieldableshaveanumberofpropertiesthattelltheindexhowtotreatthecontent(likeindexed,tokenized,stored,etc.)51Compress工具包，提供整形数字的解压缩实现多种解压缩算法采用工厂方法模式52AnalysisAnanalyzerbuildsTokenStreams,whichanalyzetextItthusrepresentsapolicyforextractingindextermsfromtextTypicalimplementationsfirstbuildaTokenizer,whichbreaksthestreamofcharactersintorawTokensOneormoreTokenFiltersmaythenbeappliedtotheoutputoftheTokenizer53PARADISEImplementation

/src/paradise/

applicationPKUsearchpdfliteraturesearch2008Olympicssearchmodulecrawlanalysis&indexsearchutilitycompressBuffer...thirdpartycmake,boost,zlib,tidy,openssl,berkeleydbdataTianwangFormatquerylogIPLocator

tutorialCMakeandBoostreferenceBooksandpaperscourseInformationRetrievalCloudComputingDistributedSy