[6D]グラフ分析

17:15 〜 17:40

[6D-04] 大規模グラフデータにおけるGPUを用いた全点対最短経路アルゴリズム

*二上 海斗¹、常 穹¹、宮崎 純¹ (1. 東京科学大学　宮崎研究室)

発表者区分：学生
論文種別：ロングペーパー
インタラクティブ発表：あり

キーワード：

グラフデータ処理、GPU

近年、GPUは大規模な並列処理が可能であるという特性からデータ処理の高速化に活用されている。しかし、GPUにはメモリに制限があるという特性もあり大規模なグラフデータへの処理に対して相性が悪い。そこで、本研究では分割したグラフデータを効率的に処理して統合する分割統治戦略にGPU上でグラフデータの処理に特化した並列幅優先探索の手法を組み込み、大規模なグラフデータを更に効率的に処理する全点対最短経路探索アルゴリズムを提案する。提案手法ではこの2つの手法を組み合わせることで、現実にあるTwitterやYoutubeといった大規模なスパースグラフを対象に高速化を図る。評価実験では使用する２つの既存手法を比較手法として提案手法の性能を評価する。