在多个关键点上映射reduce

Question

问题

我们有记录，比如r_i，其中i=0，。。。，n.n可以很大(以数百亿为单位(。

每个记录都有多个密钥，k_ij，其中j=0，。。。，m是小的(比如说20(

我们说，r_p=r_q，如果k_p0=k_q0、k₁=k_q1…、或、k_pm=7_qm

也就是说，记录是相等的，如果至少有一个键是相等的。我们需要找到这样的记录集，并为这些记录集生成唯一的id。

方法

运行m map reduce jobs，其中每个作业在一个键上减少。

因此，对于作业i，映射器发出(r_p，k_i(，减少器得到({r₁、…、r_p}、k_i

在所有m个作业结束时，我们将有一组具有相同密钥的记录。

S_k={r_l}

我们预计k小于n，但仍可能是数亿，l是一个小数字(比如2到5000之间(

为了获得最终结果，我们需要合并以上至少有一个共同成员的集合。

我有以下问题：

1. 如何有效地合并这些集合
2. 或者，还有其他方法可以解决这个问题吗

Answer 1

我意识到这是一个ConnectedComponent问题，并且有众所周知的解决方案。