java - 仅报告 mapReduce 作业的映射器中的 k 个最低值

Question

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

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

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

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

感谢任何帮助

谢谢

Answer 1

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

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