apache sparkのディスジョイントセット

Question

apache sparkを使用して大量のデータに対してディスジョイントセット（接続コンポーネント/ユニオン検索）を検索するアルゴリズムを見つけようとしています。 データの量に問題があります。グラフ頂点のRaw表現は、単一のマシン上のラムには適合しません。縁もラムには収まりません。

ソースデータは、hdfs： "id1 \ t id2"のグラフエッジのテキストファイルです。

idはintではなく文字列値として存在します。私が見つけた

ナイーブ解決策は以下のとおりです。

1. テイクエッジのRDD - >[id1:id2] [id3:id4] [id1:id3]
2. グループはキーでエッジ。 - >各グループに最小のIDを設定し、各レコードの[id1:[id2;id3]][id3:[id4]]
3. - >(flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
4. 逆にRDDのサイズながら、ステージ2からステージ3及び4
5. リピートからステージRDDSの3 [id2:id1] -> [id1:id2]
6. leftOuterJoinからRDDステップ3は、

を変更しないだろうが、これは、ノード間で大量のデータの転送 （シャッフリング）

もたらします

アドバイスはありますか？

Answer 1

あなたがグラフで作業している場合、私はあなたが彼らの両方が、外の連結成分のアルゴリズムを提供し、これらのライブラリのいずれか1

• GraphX
• GraphFrames

を見てみることをお勧めしますボックス。

GraphX：

val graph: Graph = ... 
val cc = graph.connectedComponents().vertices 

GraphFrames：http://spark.apache.org/：

val graph: GraphFrame = ... 
val cc = graph.connectedComponents.run() 
cc.select("id", "component").orderBy("component").show()