将收集与阈值过滤分组

Question

我正在尝试提出一种算法来减少地图中的以下内容。我收到一堆对象和所有者的用户ID。换句话说，我会收到一对：

(object, uid)

我想最终获得对(object,count)的列表，其中count是指对象出现在列表中的次数。注意的是，我们需要按照以下方式过滤所有内容：

1. 我们应该仅包括对象对，以使对象至少对n不同的UID重复。

2. 我们应该只包含对象，以使其重复的总数至少为m。

对象和用户都表示为整数。问题在于，将每个(object,uid)对转换为(object, 1)，然后通过将第二个整数求和在一起，这是微不足道的。然后，我可以过滤所有未达到（2）阈值的所有内容。但是，在这一点上，我将失去通过（1）过滤所需的信息，这是我不知道如何将其纳入其中的内容。有人有任何建议吗？

Answer 1

最简单，最自然的方法是按顺序运行两个MR Jobs。第一个工作的目标是计算每个uid拥有的每个object的次数。结果是三重态（object，uid，count）。uid字段此处仅用于调试目的 - 在第二个作业中不需要。object的第二个工作组三重态。在每个redain（）呼叫的末尾，您知道：

1. 对象的不同uid s的数量（接收的三胞胎数）
2. 拥有多少时间object的总数（count字段的总和）

所以，现在您可以使用两个过滤器。

---

单job设置也是可能的，但是它需要使用SetSortComparatorClass（），setGroupingComparatorClass（）和setPartitionerclass（）在较低级别上操纵工作。想法是Map（）应该发出包含object和uid字段的复合键，完全不使用值（无效）：

1. 仅通过使用键的object字段才能分区分区键。这确保所有具有相同object的记录都将完成相同的减少任务。
2. sortcomparator类的实现方式首先比较 object字段，如果它们相同，则uid字段。
3. GroupingComparatorClass仅使用object字段进行比较。

在结果中，单个减少任务的输入看起来如下：

object1 uid1
object1 uid2
object1 uid2
object1 uid2
object1 uid5
object1 uid6
object1 uid6
------------  <- boundary of call to reduce
object7 uid1
object7 uid1
object7 uid5
------------- <-- boundary of call to reduce()
object9 uid3

如您所见，UID被严格在每个呼叫内部订购以降低（），这使您可以同时计数不同的和不固定的UID的数量。