GPUを用いたグラフ型データベースの高速化及び拡張性の改善

森島 信  松谷 宏紀  

誌名
電子情報通信学会論文誌 D   Vol.J98-D   No.12   pp.1436-1450
発行日: 2015/12/01
早期公開日: 2015/09/01
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2015JDP7006
論文種別: 論文
専門分野: 計算機システム
キーワード: 
グラフ型データベース,  GPU,  グラフ探索,  

本文: PDF(1.4MB)>>
論文を購入




あらまし: 
グラフ型データベースは,データをグラフ形式で蓄積し処理するデータベースである.グラフ型データベースはノード間の関係性を表現するのに向いているため,SNS (Social Networking Service)やソーシャルグラフを基にしたリコメンデーションエンジンへの応用が期待されている.ソーシャルグラフのような大規模データが一台の計算機に収まらない場合は,複数台の計算機にグラフ型データベースを分割する手法が提案されているが,グラフの探索をする際,複数の計算機に跨って探索を行う必要があり,計算時間が長くなる.本論文では,複数台のグラフ型データベースサーバに跨るグラフを直接探索するのではなく,これらのグラフ型データベースからグラフ探索に必要最低限の情報のみを集め,一台の計算機上でGDBキャッシュとして併合し,これを探索に使用する.辺を跨ぐ横断処理をこのGDBキャッシュに対して行うことで,グラフ型データベースの枠組みを維持しつつ拡張性を改善できる.更に,GPUを用いてこのGDBキャッシュを探索することでグラフ型データベースのグラフ探索クエリを高速化する.GDBキャッシュは元のデータ構造に対して0.71%から0.77%のデータサイズとなった.その結果,64GBのメモリを有する計算機において,オリジナルのグラフ型データベースの139台分の大きさのグラフを保存できることを示した.GDBキャッシュに対するDijkstra法において,GPUによる実装はCPUに対して最大2.5倍,CPUとGPUの混成実行では最大4.8倍の高速化を実現した.