マルチコアおよびGPUを用いたグラフ型データベースの性能評価

摘要

グラフ型データベースは、データをグラフ形式で蓄積し処理するデータベースである。グラフ型データベースはノード間の関係性を表現するのに向いているため、SNS（Social Networking Service）やソーシャルグラフを基にしたリコメンデーションエンジンへの応用が期待されている。グラフ型データベースで最も計算量が多い処理は、グラフの探索である。本論文では、グラフ探索処理の並列化とGPUによる高速化を実現し、その性能を評価する。ここではグラフ型データベースNeo4jを対象に、Dijkstra法やA~*法を高速化する。評価では、Facebookの次数分布を基にした100，000ノードのグラフに対して探索を行ったときの計算時間を測定した。データ構造を変える際のオーバーヘッドを含めない場合は、オリジナルのNeo4jと比べて、8ノードで並列化すると、Dijkstra法において16.2倍、A~*法において13.8倍高速化できた。一方、GPUでは、Dijkstra法において26.2倍、A~*法において32.8倍高速化できた。オーバーヘッドを考慮しても、この性能向上は有意である。