研究は実際のビッグデータではなく合成データセットのホーニングアルゴリズムを対象としているため、「開発」はここで重要な言葉です。
「グラフは、ソーシャルネットワーク、ビジネスインテリジェンス、生物学、神経科学など、多くのドメインで実世界のオブジェクトを表現および分析するために広く使用されています」とKaist氏は述べています。 「大規模なグラフのアルゴリズムを開発およびテストする場合、通常、実際のグラフの代わりに合成グラフが使用されます。 これは、大規模な実際のグラフの共有と利用が、独占的であるか、収集することが事実上不可能であるために非常に制限されているためです。」
従来、Kaistによれば、グラフアルゴリズムの開発とテストは、次のXNUMX段階のアプローチで行われます。
ステップXNUMXは、合成グラフを生成し、それをディスクに保存します。 グラフは通常、パラメーターベースの生成またはグラフのアップスケーリングのいずれかによって生成されます。前者は、特定の実際のグラフのいくつかのプロパティをキャプチャできる少数のパラメーターを抽出し、パラメーターを使用して合成グラフを生成します。後者は、元の実グラフのプロパティを可能な限り保持するために、実グラフをより大きなグラフに指定します。
ステップXNUMXは、保存されたグラフをApache GraphXなどのグラフ処理エンジンのメインメモリにロードし、エンジンで特定のグラフアルゴリズムを実行します。 「グラフが大きすぎてXNUMX台のコンピューターのメインメモリに収まらないため、グラフエンジンは通常、数十台または数百台のコンピューターのクラスターで実行されます」とKaist氏は述べています。「したがって、従来のXNUMX段階アプローチのコストは高くなります。 。」
韓国チームは、大規模な合成グラフを生成して保存していません。
代わりに、最初の小さな実グラフをメインメモリにロードします。 次に、T-GPS（兆スケールのグラフ処理シミュレーション）と呼ばれる手法を使用して、グラフアルゴリズムは、実グラフから生成されるはずの大規模な合成グラフがメインメモリに存在するかのように、小さな実グラフに直面しました。 、アルゴリズムが実行された後、T-GPSは従来のXNUMXステップアプローチと同じ結果を返すことを追加します。
「T-GPSの重要なアイデアは、アルゴリズムがオンザフライでアクセスする必要のある合成グラフの部分のみを生成し、グラフ処理エンジンを変更して、オンザフライで生成された部分を実際に生成された合成グラフの一部として認識することです。 」とカイストは言った。
T-GPSは43台のコンピューターでXNUMX兆個のエッジのグラフを処理しましたが、従来のXNUMX段階のアプローチでは、XNUMX億個のエッジのグラフを処理するために、同じ仕様のXNUMX台のコンピューターのクラスターが必要でした。 ネットワークアクセスを必要としないT-GPSは、通信のオーバーヘッドが大きい従来のアプローチよりも最大XNUMX倍高速でした。
この作業は、IEEE ICDE 2021会議で、「トップダウングラフアップスケーリングに基づく兆スケールのグラフ処理シミュレーション」として発表されました。