如何用MapReduce范式找出有共同后继的网页对及对应后继页面

Map阶段处理逻辑 #

输入是形如(siteA, siteB)的元组，代表siteA存在指向siteB的链接。

• 直接以**siteB（后继页面）**作为键，**siteA（前驱页面）**作为值输出，也就是生成(siteB, siteA)这样的键值对。这一步的核心是把所有指向同一个后继的前驱页面归集到同一组中。

Reduce阶段生成网页对 #

Reduce阶段会收到同一个siteB对应的所有前驱页面列表，比如键为siteX时，对应的值列表是[site1, site2, site3, ...]。

• 对这个前驱列表进行两两组合生成无序页面对：从列表的第一个元素开始，依次和它之后的每个元素配对（比如site1和site2、site1和site3、site2和site3），避免生成重复的反向对（比如(site2,site1)和(site1,site2)视为同一对，无需重复输出）。
• 每生成一对页面，就输出格式为(siteX, siteY, siteB)的结果，其中siteX和siteY是拥有共同后继siteB的网页对。

举个实际例子：
如果输入包含(site1, siteX)、(site2, siteX)、(site3, siteX)三个元组，Map阶段会输出(siteX, site1)、(siteX, site2)、(siteX, site3)三个键值对。Reduce阶段拿到siteX对应的页面列表后，会生成三行输出：
(site1, site2, siteX)
(site1, site3, siteX)
(site2, site3, siteX)

内容的提问来源于stack exchange，提问作者bipur24