并行化的集合交集算法

Question

并行化的集合交集算法

algorithmparallel-processingdistributed-computingsetset-intersection

4

我有分布在n个进程上的n组数据，表示网格的节点，并且我想知道一个高效的并行算法来查找这些集合的交集，即公共节点。只要任意两个集合共享一个节点，就定义为一个交集。

例如：

输入：

Rank 0: Set 1 - [0, 1, 2, 3, 4]

Rank 1: Set 2 - [2, 4, 5, 6]

Rank 2: Set 3 - [0, 5, 6, 7, 8]

实施并行算法 --> 结果：（找到交点后）

Rank 0: [0, 2, 4]

Rank 1: [2, 4, 5, 6]

Rank 2: [0, 5, 6]

算法需要在n个排名上完成，每个排名上设置一个集合。

- GK-F3D

我找到了一种高效地执行两个集合交集的算法，因此我考虑创建一个树形结构，每次比较两个排名，直到排名全部用完。 - GK-F3D

2个集合的交集算法如下：我们可以有两个索引，它们都从零开始。比较A和B的前两个元素。如果A [0]大于B [0]，则将B的索引增加1。如果B [0]大于A [0]，则将A的索引增加1。如果它们相等，则知道已发生交集，因此将其添加到列表中，并将A和B的索引增加1。一旦任何一个索引达到A或B的末尾，我们就找到了A和B的所有交集。这需要在排序之后实现。 - GK-F3D

2

从数学上讲，您希望每个排名的结果是该排名集合与其他每个排名集合的交集的并集。对于并行实现，考虑一个等价问题可能是值得的：删除不属于任何其他集合的每个元素。附注：这些集合总是有序的吗（如您的示例中所示）？ - Ted Hopp

是的！我认为在执行交集操作之前对其进行排序会很有帮助。通过执行排序，我可以消除一些可能没有任何共同元素的等级。你提出的等价问题也可以解决…让我再想一想！ - GK-F3D

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

你应该能够快速地使用O(N)的哈希表并行完成此操作。

对于每个集合S_i，对于每个成员m_x（所有这些都可以并行完成），将集合成员放入与集合名称相关联的哈希表中，例如。任何时候，如果从集合S_j中获取到m_x的哈希表命中，则现在您拥有相应的集合编号S_i，并且您立即知道S_i与S_j相交。您可以将m_x放入派生的交集集合中。

您需要一个并行安全的哈希表。这很容易; 在更新期间锁定桶。

[另一个答案建议对集合进行排序。对于大多数排序算法，时间复杂度为O(N ln N)，不如哈希表快]。