メニーコアプロセッサを用いた構造的類似度に基づくグラフクラスタリングの高速化

• 高橋, 知克

• 塩川, 浩昭

• 北川, 博之

書誌事項

タイトル別名

• Efficient and Exact Parallel Structural Graph Clustering Algorithm on Intel Xeon Phi Processor

抄録

構造的類似度に基づくグラフクラスタリング手法SCANは，グラフ中からクラスタやハブ，外れ値を高精度で検出できるため幅広く利用されている．しかしながら，SCANはすべてのエッジの構造的類似度を計算するため，大規模グラフの分析には膨大な計算時間を必要とする．そこで本稿では，メニーコアプロセッサIntel Xeon Phiを用いたSCANの高速化手法SCAN-XPを提案する．提案手法は，並列グラフ処理のボトルネックを解消するとともに，アルゴリズムをIntel Xeon Phiの持つ512ビットSIMD演算に最適化する．本稿では実データを用いた評価実験を行い提案手法の有効性を示す．

The structural graph clustering method SCAN is successfully used in many applications because it can extract clusters, hubs and outliers from a graph at the same time. However, it is difficult for SCAN to compute large-scale graphs since SCAN needs to evaluate the density for all edges in graphs. To address the above problem, we present SCAN-XP that performs over Intel Xeon Phi. SCAN-XP avoids the bottlenecks that arise from parallel graph computations and it effectively exploits 512bit SIMD instructions. Our evaluations on real-world graphs demonstrate that SCAN-XP outperforms existing approaches.

収録刊行物

• 情報処理学会論文誌データベース（TOD）

  情報処理学会論文誌データベース（TOD） 10 (4), 1-5, 2017-12-13

キーワード

• [テクニカルノート] グラフクラスタリング，SIMD演算，Intel Xeon Phi

詳細情報

• CRID: 1050282812885224704
• NII論文ID: 170000149096
• NII書誌ID: AA11464847
• ISSN: 18827799
• Web Site: http://id.nii.ac.jp/1001/00184834/
• 本文言語コード: ja
• 資料種別: article
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN