- 1、本文档共44页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
在Pregel计算模型中,图中的每个顶点会对应一个计算单元,每个计算单元包含三个成员变量: 顶点值(Vertex value):顶点对应的PR值 出射边(Out edge):只需要表示一条边,可以不取值 消息(Message):传递的消息,因为需要将本顶点对其它顶点的PR贡献值,传递给目标顶点 每个计算单元包含一个成员函数Compute(),该函数定义了顶点上的运算,包括该顶点的PR值计算,以及从该顶点发送消息到其链出顶点 9.7.2 PageRank算法在Pregel中的实现 9.7.2 PageRank算法在Pregel中的实现 class PageRankVertex: public Vertexdouble, void, double { public: virtual void Compute(MessageIterator* msgs) { if (superstep() = 1) { double sum = 0; for (;!msgs-Done(); msgs-Next()) sum += msgs-Value(); *MutableValue() = 0.15 / NumVertices() + 0.85 * sum; } if (superstep() 30) { const int64 n = GetOutEdgeIterator().size(); SendMessageToAllNeighbors(GetValue()/ n); } else { VoteToHalt(); } } }; 9.7.2 PageRank算法在Pregel中的实现 PageRankVertex继承自Vertex类,顶点值类型是double,用来保存PageRank中间值,消息类型也是double,用来传输PageRank值,边的value类型是void,因为不需要存储任何信息 这里假设在第0个超步时,图中各顶点值被初始化为1/NumVertices(),其中,NumVertices()表示顶点数目 在前30个超步中,每个顶点都会沿着它的出射边,发送它的PageRank值除以出射边数目以后的结果值。从第1个超步开始,每个顶点会将到达的消息中的值加到sum值中,同时将它的PageRank值设为0.15/NumVertices()+0.85*sum 到了第30个超步后,就没有需要发送的消息了,同时所有的顶点停止计算,得到最终结果 MapReduce也是谷歌公司提出的一种计算模型,它是为全量计算而设计 采用MapReduce实现PageRank的计算过程包括三个阶段: 第一阶段:解析网页 第二阶段:PageRank分配 第三阶段:收敛阶段 9.7.3 PageRank算法在MapReduce中的实现 9.7.3 PageRank算法在MapReduce中的实现 该阶段的任务就是分析一个页面的链接数并赋初值。 一个网页可以表示为由网址和内容构成的键值对 URL,page content,作为Map任务的输入。阶段1的Map任务把URL,page content映射为URL,PRinit,url_list后进行输出,其中,PRinit是该URL页面对应的PageRank初始值,url_list包含了该URL页面中的外链所指向的所有URL。Reduce任务只是恒等函数,输入和输出相同。 对右图,每个网页的初始PageRank值为1/4。它在该阶段中: Map任务的输入为: AURL,Acontent BURL,Bcontent CURL,Ccontent DURL,Dcontent Map任务的输出为: AURL,1/4,BURL,CURL,DURL BURL,1/4,AURL,CURL CURL,1/4,DURL DURL,1/4,AURL,BURL 1. 阶段1:解析网页 9.7.3 PageRank算法在MapReduce中的实现 该阶段的任务就是多次迭代计算页面的PageRank值。 在该阶段中,Map任务的输入是URL,cur_rank,url_list,其中,cur_rank是该URL页面对应的PageRank当前值,url_list包含了该URL页面中的外链所指向的所有URL。 对于url_list中的每个元素u,Map任务输出u,URL, cur_rank/|url_list|(其中,|url_list|表示外链的个数),并输出链接关系URL,url_list。 每个页面的PageRank当前值被平均分配给了它们的每个外链。Map任务的输出会作为下面Reduce任务的输入。对下图第一次迭代Map
您可能关注的文档
- ao理论与方法的新进展——骨折的生物学固定.ppt
- APDL实例MPC184定义万向联轴器滑动副转动副.doc
- API 16C产品设计要求规范.doc
- API函数在VB中的应用.doc
- API油管和套管螺纹加工与检验探讨.docx
- app用户注册协议模板.doc
- ArcGIS102 学习课程——4专题图制作和地图打印.ppt
- arcgis云平台软件---单一来源采购参数.doc
- arlonsecure1500fg导热粘接绝缘膜应用介绍.ppt
- arvc单形性室速:导管消融还是icd.ppt
- 10《那一年,面包飘香》教案.docx
- 13 花钟 教学设计-2023-2024学年三年级下册语文统编版.docx
- 2024-2025学年中职学校心理健康教育与霸凌预防的设计.docx
- 2024-2025学年中职生反思与行动的反霸凌教学设计.docx
- 2023-2024学年人教版小学数学一年级上册5.docx
- 4.1.1 线段、射线、直线 教学设计 2024-2025学年北师大版七年级数学上册.docx
- 川教版(2024)三年级上册 2.2在线导航选路线 教案.docx
- Unit 8 Dolls (教学设计)-2024-2025学年译林版(三起)英语四年级上册.docx
- 高一上学期体育与健康人教版 “贪吃蛇”耐久跑 教案.docx
- 第1课时 亿以内数的认识(教学设计)-2024-2025学年四年级上册数学人教版.docx
文档评论(0)