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

Question

问题是:假设我们有一组Sets : Set(1,2,3) Set(1,2,3,4) Set(4,5,6) Set(1,2,3,4,6),我们需要删除所有子集,最后得到Result : Set(4,5,6) Set(1,2,3,4,6). (由于两个Set(1,2,3)和Set(1,2,3,4)是的子集Set(1,2,3,4,6),这两种都被删除.)

并且假设集合的元素有order,可以是Int,Char等.

是否有可能以map-reduce方式进行？

以map-reduce方式执行此操作的原因是,有时Group的组具有非常大的大小,这使得无法在单个机器的内存中执行此操作.所以我们希望以map-reduce方式实现它,它可能效率不高,但只是工作.

我的问题是:

1. 我不知道如何在map-reduce进程中为键值对定义一个键,以便正确地对Set进行分组.

2. 我不知道何时应该完成该过程,所有子集都已被删除.

EDIT:

1. 未来数据的规模将继续扩大.

2. 输入可以是一组或多行,每行包含一组集.目前val data = RDD[Set],我首先做的是输入data.collect(),这导致整组的集合.但我可以将输入的生成修改为a RDD[Array[Set]],这将为我提供多行,每行包含一组集合.

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

Answer 1

我怀疑这可以通过传统的映射归约技术来完成，该技术本质上是一种分而治之的方法。这是因为：

• 在这个问题中，每个集合本质上必须与所有较大基数的集合进行比较，这些较大基数的最小和最大元素位于较小集合的最小和最大元素周围。
• 与排序和其他适合映射归约的问题不同，我们没有传递性关系，即，如果A is not-a-subset-of B和B is-not-subset-of C，我们无法对Awrt做出任何陈述C。

根据上述观察，这个问题似乎与重复检测类似，并且有关于重复检测的研究，例如这里。类似的技术对于当前的问题也很有效。