我有n个表示网格节点的数据集（分布在n列），我想知道一个有效的并行算法来找到这些集合的交集，即公共节点。任何2组共享一个节点后立即定义交集。设置交叉点的并行算法
例如;
输入：
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]
该算法需要在正行列进行与1组上的每个秩。
你应该能够用这个快速的O（N）并行哈希表。
对于每个集合S_i，对于每个成员m_x（所有成员都可以并行完成），将集合成员置于与集合名称关联的散列表中，例如。每当你从集合S_j的m_x的哈希表中得到一个命中，你现在就有相应的集合数S_i，并且你立即知道S_i与S_j相交。你可以把m_x放在派生的交集中。
您需要一个并行安全的散列表。这很容易;更新期间锁定存储桶。
[另一个答案建议排序集。对于大多数排序算法，将会是O（N ln N）时间，而不是快速]。
我想到了这一点，但是这不是内存密集？整个域中的节点数量（所有集合中所有条目的总和）可能为100百万。如果将所有组合放在1个等级上并使用优化的串行交叉算法，然后将此信息传达给所有其他等级，会更好吗？ –
你想要快。为了获得快速，你倾向于将时间换成空间。那么，多少空间？估计，数据点可能是16个字节，集合ID可能是4个字节，哈希链接可能是8个字节，因此每个点有32个字节* 1亿 - > 3200万个字节。这是3.2 GB的RAM，在您当地的电脑经销商处售价为50美元。有什么问题？ [你是不是已经把所有这些数据点都放在内存中了？] –
....如果你不想为哈希表增加额外的内存，那么对这些集合进行排序（为空间支付时间）将是一个好的解决方案但是，1亿是22（基数2），所以期望它明显变慢。 –
我发现一个算法有效地做了2组交集，所以我正在考虑创建一个比较2个等级的树结构，直到我耗尽所有的等级。 –
2组交叉算法看起来像这样;我们可以有两个索引，都从零开始。比较A和B的两个第一个元素。如果A [0]大于B [0]，我们将B的索引增加1。如果B [0]大于A [0]，我们将A的索引增加1。如果它们相等，我们知道发生了交集，所以将其添加到列表并将A和B的索引增加1。一旦索引达到A或B的末尾，我们就找到了A和B的所有交集。这需要在排序后执行。 –
在数学上，你想要得到的每个等级的结果是该等级的集合与其他等级集合的交集**的联合。对于并行实现，考虑一个等价问题可能是值得的：删除不是任何其他集合的元素的每个元素。附：这些集合alwasys是否有序（如你的例子）？ –