一种有效的公有元素集合并的分布式算法

Question

我正在Flink上开发一个MinHash LSH的分布式实现，作为最后一步，我需要合并一些集群，这些集群被标识为它们之间相似的元素集。

因此，我有一个集的分布式集合作为输入，我需要一个算法来有效地将集合与公共元素合并。给定Flink的计算模型，该算法可能是迭代的，不一定映射约简相似。

这里有一个例子：

在{{1{1,2}},{2,{2,3}},{3,{4,5},{4{1,27}}}}中，结果应该是{1,2,3,27},{4,5}，因为集合#1、#2和#4至少有一个共同的元素。

Answer 1

这里有一个想法: Gelly是Flink的一部分，它有一个连接的组件查找器。以尽可能简单的方式为每个集合元素和边建立一个节点，例如对于{a，b，c，d，.}添加a，b，a，c，a，d，[a，.]。现在找到连接的组件。他们的节点给出了你要找的集合。

编辑如果您担心从集到图和返回的转换对性能的影响(尽管这种担心是过早的优化；您应该尝试它)，那么重新实现Gelly的令牌推送方案就足够简单了。这是怎么回事。在您的示例中已经有了标记:集合编号。让我设定我在你的例子中。例如S1 = {1,2}。设R是一个逆的multimap，它将每个集合元素带到它所属的集合集合中。例如，示例中的R2 = {1,2}。设Ti是可以通过传递的非空交“链接”从集合i到达的元素。然后计算：

T[i] = S[i] for all i // with no links at all, a set reaches its own elements
loop
  for all i, Tnew[i] = \union_{ x \in T[i] } S[R[x]]  // add new reachables
  exit if Tnew == T
  T = Tnew
end loop

完成后，映射T的不同值就是您想要的答案。迭代的最大次数应该是log =u，其中U是集合元素的宇宙。

Answer 2

只是一个主意，也许有更好的方法，但是这个怎么样：

• 在映射步骤中，为每个集合中的每个元素发出一个键值对，如：element -> other elements。
• 在减少步骤中，收集其他元素并丢弃重复的元素。
• 重复，直到数据结构停止更改。

在第一次迭代之后，您的数据如下所示：

1 -> 2, 27
2 -> 1,3
3 -> 2
4 -> 5
5 -> 4
27 -> 1

第二次会议之后：

1 -> 2, 3, 27
2 -> 1, 3, 27
3 -> 1, 2
4 -> 5
5 -> 4
27 -> 1, 2

最后，在第三个之后：

1 -> 2, 3, 27
2 -> 1, 3, 27
3 -> 1, 2, 27
4 -> 5
5 -> 4
27 -> 1, 2, 3

我目前还没有解决办法来找出什么时候改变已经停止。

若要只获得每个结果的一个副本，可以删除键大于任何其他元素的所有位置。

Answer 3

如果每个N集合都包含M元素，那么如果复制很少，那么简单的方法(将每个集合的每个元素与其他元素进行测试)都是O(N^2 * M^2)。但是，如果您实际上只有R << N*M不同的元素，那就没有那么糟糕了:一旦发现了一些东西，就可以停止测试，这在N*M比较之后就会发生，而只有R，所以您只能使用“只”O(N*N*R)。但是，如果集合实际上只存在于L组中，则不必针对其他集合测试每一组，因为一旦找到正确的组，就会停止。因此，它更像O(N*L*R) + O(N*M) (第二个术语实际上是在找到要添加的组后将元素添加到组中)。

如果您从每个元素映射到它包含的集合列表--您可以在O(N*M)时间内这样做--那么每个元素都可以遍历集合树，最多只访问一次不同的元素(即它们的R )，对于每个访问它的集合(结果是关于N*M/R的集合)，并添加其所有元素(但只有一次！)，如果您不小心添加相同的设置多次，则总体上就是O(N*M)时间。(你需要一个包装器来包装它们，这样你就可以知道你是否已经访问过它们。)所以这更快，但是如果L*R很小，你可能就不在乎了。

在Scala中，从元素到树的映射的核心看起来类似于

case class W(s: Set[Int]) { var visited: Boolean = false }
def tree(ss: Seq[Set[Int]]) = {
  var m = new collection.mutable.HashMap[Int, List[W]]
  ss.foreach{ s =>
    s.foreach{i =>
      m(i) = W(s) :: m.getOrElse(i, Nil)
    }
  }
}

遍历这些组要复杂得多，但是基本的想法是保持一张你看到的元素的地图，而不是在碰到其中一个元素时继续遍历，还可以通过在W包装器中设置标记来跟踪是否在合并元素时遍历集合。