云計算-cloud如選擇投影求交集、并集連接成組聚合

副研究員博士 4如：選擇，投影，求交集、并集，連接，成組，聚合5討 one:doc1doc3fish:one:doc1doc3fish:doc1,doc2two:doc1red:doc2,doc3blue:doc2bird:doc3onefishtwooneonered bluefish→doc1,doc2red→doc2,doc3redfish→doc2importimportimportimportpublicclassInvertedIndexMapperextendsMapper<Text,Text,Text, //defaultRecordReader:LineRecordReader;key:lineoffset;value:line FileSplitfileSplit=(FileSplit)context.getInputSplit();StringfileName=fileSplit.getPath().getName();Textword=newText();TextfileName_lineOffset=newfor(;itr.hasMoreTokens();) }}}importjava.io.IOException;importjava.util.Collections;importjava.util.Iterator;importimport throwsIOException, Iterator<Text>it=values.iterator();StringBuilderall=newStringBuilder();for(;it.hasNext();) }}publicclass{publicstaticvoidmain(String[]{tryConfigurationconf=newjob=newJob(conf,"invertFileInputFormat.addInputPath(job,newFileOutputFormat.setOutputPath(job,new pletion(true)?0:}catch(Exceptione) }}11一個倒排索引由大量的postingslist一個postingslist由多個posting構(gòu)成(按docid排序一個postingslist與一個term一個posting包含一 id和一個 中出現(xiàn)情況相關(guān)的信息(e.g.termfrequency,positions,termproperties)同時還有對應(yīng)Web文檔到其URL的映射111:class procedureMap(docidn,docd) H←newAssociativeArray foralltermt∈docddo H{t}←H{t}+ foralltermt∈H Emit(termt,posting<n,H{t}>)1:classReducer procedureReduce(termt,postings[<n1,f1>,<n2, P←new forallposting<a,f>∈postings[<n1,f1>,<n2,f2>…] Append(P,<a,f>) Emit(termt;postings11文檔倒排索引1文檔倒排索引進(jìn)入reduce的鍵值對按照(termdocid)進(jìn)入reduce的鍵值對按照(termdocid)Customized1帶詞頻等屬性的文檔倒排算法（改進(jìn)Class rtitionerextends// //overridethegetPartition(Kkey,Vvalue,int term=key.toString().split(“,”)[0];//<term,super.getPartition(term,value,}}SetthecustomizedpartitionerinjobJob. 2DistributedData10MB?10GB?2SortAlgorithminmap(k1,*)->(k1, //Identity(1)total-order(2)localreduce(k1,*)->(k1, //IdentityAcustomizedtotal-orderrecallthatshufflephaseneedsaPartitionertopartitionthekeythatdependsonyourdata22(1)如何避免在某些Reducer 過多的數(shù)據(jù)而拖慢了整個程(2)當(dāng)有大量的key要分配到多個partition（也就是Reducer）時，如何高效地找到每Key的分布預(yù)讀一小部分?jǐn)?shù)據(jù)采樣對采樣數(shù)據(jù)排序后均分，假設(shè)有N個reducer，則取得N-1個分割usesasortedlistofN-1sampledkeysthatdefinethekeyrangeforeachInparticular,allkeyssuchthatsample[i-1]<=key<sample[i]aresenttoreducei.guaranteesthattheoutputofreduceiarealllessthantheoutputofreduce設(shè)reduce數(shù)目為3，采到9取兩個分割點60,68；劃分區(qū)間為：[*,60),[60,68),3M.R.Algorithm(“pairs”approach)pseudo-1:class2:methodMap(docida,doc foralltermw∈docd foralltermu∈Neighbors(w) //Emitcountforeachco-occurrenceEmit(pair(w,u),count1)1:class2:methodReduce(pairp;counts[c1, s← forallcountc2counts[c1,c2,…] s←s+ //Sumco-occurrence Emit(pairp,count3構(gòu)建單詞同現(xiàn)矩陣-wearenotwewanttobutatwearenotweusedto同現(xiàn)定義wordsthatco-occurwithwwithina2-word3構(gòu)建單詞同現(xiàn)矩陣把小的鍵值對合并成大的鍵值通常一個計算問題會產(chǎn)生大量的鍵值對，為了減少鍵值對傳輸和排序的開銷，一些題中的大量小的鍵值對可以被合并成一些大的鍵值對(pair