Description

  给定一行一行关系数据,找出所有的二度关系。

A B
A C
A D
B E
B C
C D
C F

Solution

  这里要分两个串行的 MR 才能解决,第一个 MapReduce 的 Map 阶段可以将所有的逆关系加进去,比如遇到 <A, B> 把 <B, A> 加进去,这样所有的关系都是成对出现了,然后把所有关系对的第一列作为 Key,第二列作为 Value 保存成结果输出给 Reduce。

  然后在 Reduce 阶段得到输入数据为 <A, {B,C,D}> 的形式,那么我们先构建一度关系,将 Key 跟 Value 中的每一个值进行关联成 <{A, B}, 1> 格式。因为 Value 中的都是可能二度关系,所以我们可以取两两关系,组合成 <{B, C},2> 格式。

  接着第二个 MapReduce 程序的 Map 阶段读入 <{B, C},2> 格式的数据,得到结果 <{B, C},{1,2}>。对于 Value 中包含 1 的即表示含有一度关系,我们就不存储,所以在 Reduce 阶段只要过滤掉含有 1 的关系对,只保留只有 2 的关系对,并将其做成 <Key,Value>的形式输出即可。

References

  1. 利用 MapReduce 思想求解二度人脉