algorithm - 集合交差の並列アルゴリズム

Question

メッシュのノードを表すデータの 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 セットの n ランクで実行する必要があります。

Answer 1

ハッシュテーブルを使用して、この高速なO（N）を並行して実行できるはずです。

各セットS_iについて、各メンバーm_x（すべてを並行して実行できます）について、セットメンバーをセット名に関連付けられたハッシュテーブルに配置します（例：。セットS_jからm_xのハッシュテーブルにヒットしたときはいつでも、対応するセット番号S_iがあり、S_iがS_jと交差していることがすぐにわかります。派生した交差セットにm_xを入れることができます。

並列安全なハッシュテーブルが必要です。簡単だ; 更新中にバケットをロックします。

[別の回答では、セットを並べ替えることを提案しました。ほとんどのソートアルゴリズムでは、O（N ln N）時間であり、それほど速くはありません]。