0

我正在编写一个 mapReduce 作业，该作业从一个巨大的数据集中找到与一个点的距离最短的 k 个对象。

在我的映射器中，我只想报告该数据块距离最短的 k 个对象。这样，对于每个数据块，我都有 k 个中间值（键，值），其中键是距离，值是 object_id。所以在我的 reducer() 中，我可以轻松地处理和总结 k 个最小值。

我想不出一种方法来仅报告与我的映射器类中的一个数据块的点距离最短的 k 对象的中间键值对？

我知道我可以为该数据块中的所有输入数据返回 (distance,obj_id) 作为中间键值对，然后在我的减速器类中减少它并获得相同的结果。但是 k <<（每个数据块中的数据数量）并且通过只报告 k 个中间键值而不是全部，我可以显着减少数据传输/改组的数量。

任何帮助表示赞赏

谢谢

4

1 回答 1

2

假设 k 很小（你可以在内存中容纳这个数量的对象），那么这应该很容易：

  • 创建一个包含两个实例变量的包装器/容器对象 - 计算距离（浮点数/双精度？）和 object_id（文本？）
  • 有许多可能的方法来维护一组固定的值，但是对于这个例子，让我们使用 TreeSet（你的包装器对象类型）
  • 要么确保你的包装对象实现了 Comparable 接口，要么创建一个可以被 TreeSet 用来确定顺序的 Comparator 实现——实现应该首先比较距离实例变量，如果它们相同，然后比较对象 ID（这个引出了一个有趣的问题——如果你想保留最小的 10 个值，但有 20 个值都具有最小的距离——你想保留哪 10 个？）
  • 当您在映射器中处理值时，计算距离值，如果树集大小小于 K，或者距离小于集合的尾值距离，则添加此距离/obj_id 对（或者创建一个新实例如果集合大小小于 k，则删除包装器，或者驱逐尾部值并重新使用它来托管新的距离/obj id（确保将其从集合中删除，修改值，然后重新添加）
  • 在映射器的清理方法中，一次输出一个值的树集。
于 2012-07-24T01:25:43.320 回答