云计算-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构成(按docid排序一个postingslist与一个term一个posting包含一 id和一个 中出现情况相关的信息(e.g.termfrequency,positions,termproperties)同时还有对应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文档倒排索引进入reduce的键值对按照(termdocid)进入reduce的键值对按照(termdocid)Customized1带词频等属性的文档倒排算法（改进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 过多的数据而拖慢了整个程(2)当有大量的key要分配到多个partition（也就是Reducer）时，如何高效地找到每Key的分布预读一小部分数据采样对采样数据排序后均分，假设有N个reducer，则取得N-1个分割usesasortedlistofN-1sampledkeysthatdefinethekeyrangeforeachInparticular,allkeyssuchthatsample[i-1]<=key<sample[i]aresenttoreducei.guaranteesthattheoutputofreduceiarealllessthantheoutputofreduce设reduce数目为3，采到9取两个分割点60,68；划分区间为：[*,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构建单词同现矩阵-wearenotwewanttobutatwearenotweusedto同现定义wordsthatco-occurwithwwithina2-word3构建单词同现矩阵把小的键值对合并成大的键值通常一个计算问题会产生大量的键值对，为了减少键值对传输和排序的开销，一些题中的大量小的键值对可以被合并成一些大的键值对(pair