算法:是否有 map-reduce 方法通过删除所有子集来合并一组集合

Question

问题是:假设我们有一组集合:Set(1,2,3) Set(1,2,3,4) Set(4,5,6) Set(1,2,3,4,6)，我们需要删除所有的子集，最后得到Result: Set( 4,5,6) 集合(1,2,3,4,6)。 (因为 Set(1,2,3) 和 Set(1,2,3,4) 都是 Set(1,2,3 ,4,6)，两者都被删除了。)

并且假设集合的元素有顺序，可以是Int、Char等。

是否可以用 map-reduce 的方式来做？

之所以用map-reduce的方式来做，是因为有时候Set的group的size非常大，单机内存做不到。所以我们希望用map-reduce的方式来做，效率可能不是很高，但是可以。

我的问题是:

1. 我不知道如何在 map-reduce 过程中为键值对定义键以正确分组 Sets。

2. 我不知道这个过程什么时候应该结束，因为所有的子集都已经被删除了。

编辑:

1. future 数据量会越来越大。

2. 输入可以是一组集合，也可以是多行，每行包含一组集合。当前输入是 val data = RDD[Set]，我首先执行 data.collect()，这会产生一组整体集合。但我可以将输入的生成修改为 RDD[Array[Set]]，这将给我多行，每行包含一组集合。

3. 可以通过修改程序的其他部分来对每个集合中的元素进行排序。

Answer 1

我怀疑这可以通过传统的 map-reduce 技术来完成，它本质上是一种分而治之的方法。这是因为:

• 在这个问题中，每个集合都必须与所有基数较大的集合进行比较，这些集合的最小和最大元素位于较小集合的最小和最大值附近。
• 与排序和其他适用于 map-reduce 的问题不同，我们没有传递关系，即，如果 A 不是 B 的子集 并且 B 是-不是 C 的子集，我们不能对 A w.r.t 做任何声明。 C。

根据以上观察，这个问题似乎与重复检测类似，并且有关于重复检测的研究，例如here .类似的技术将适用于当前的问题。