MapReduce 中的完整距离矩阵

Question

我对 MapReduce 比较陌生，我想到了以下问题：如何在 MapReduce 中计算完整（即非稀疏）距离矩阵？

我有一个包含 N 个实例的二维数据集，我必须评估这些点之间的所有可能距离并将它们存储在矩阵中。

到目前为止我所做的是

• 让 Map 检索其块，评估这些点之间的距离：结果矩阵将是一个 NxN 矩阵，具有一些距离和一些零。
• Reduce 将连接（求和）此类矩阵，然后填充空隙（即块内距离，仍然为零的元素）

我认为这不是很有效（尤其是从内存的角度来看）。

谁能赐教一下？

更新：我对上面的代码做了一点优化。现在

• Map 接收其块并评估这些点之间的距离，而无需预先分配 NxN 矩阵，但会预先分配 Nx3 矩阵（点 A 中的第 1 列，第 2 列是点 B，第 3 列是 dist(A,B) )
• Reducer 预分配一个完全用零填充的 NxN 矩阵。现在填充由 Map 计算的距离（块间），然后填充空隙（即块内距离，仍然为零的元素）

毫无疑问，这是一个更好的解决方案，因为 Mappers 不需要构建整个 NxN 矩阵，但我仍然认为它可以做得更好。

Answer 1

我就是这样做的：Map 任务只是评估给定实例 j 与所有其他实例之间的距离。 Reducer 将这些距离连接到一个写在磁盘上的向量中。这样的记录确实是矩阵的第j行。这适用于所有实例，然后将写入磁盘的所有记录连接在一起。