AcGMコードを用いたスーパーグラフ検索の並列化
著者 今井 舜
URL http://hdl.handle.net/10236/00028894
2019 年度 修士論文要旨
AcGM コードを用いたスーパーグラフ検索の並列化
関西学院大学大学院理工学研究科 情報科学専攻 猪口研究室 今井 舜
近年，情報通信技術の進展により，膨大な量のデータを蓄積することが可能になった．
そのような大量のデータから有益な情報を抽出する方法の一つに情報検索があり，より大 規模なデータを現実的な時間で処理できるよう，情報検索手法の高速化が望まれている．
情報検索のなかでも，グラフを対象とするものをグラフ検索と呼ぶ．グラフ検索とは，グ ラフの集合からなるデータベースに対してクエリとなるグラフを与えたとき，条件を満た すグラフをデータベースから探し出して出力する技術である．グラフ検索がよく取り扱わ れる分野として，生命情報科学，化学情報学，ソーシャルネットワーク，パターン認識な どが挙げられる．
本研究はグラフ検索の一種であるスーパーグラフ検索を対象とする．スーパーグラフ検 索とは，与えられたクエリグラフに含まれるグラフをデータベースの中から探し出して出 力する処理であり，今までに様々な手法が研究されてきている．しかし，未だかつて並列 処理を導入したスーパーグラフ検索について言及した手法は私の知る限りでは存在せず，
スーパーグラフ検索の並列化が検討されていないのが現状である．そこで本研究では，既 存のスーパーグラフ検索手法に並列処理を導入する手法を提案する．
これまでの実験結果により，現状において最も高速に動作すると期待されるスーパー グラフ手法はCodeTreeかDGTreeのどちらかであると判明している．本研究では，こ
のうち CodeTreeをベースとして並列処理を取り入れたスーパーグラフ検索手法である
ParallelCodeTreeを実現する．ParallelCodeTreeでは，並列化におけるスーパーグラフ検 索の計算速度向上を最大化するため，複数のスレッドでタスクを分担したときのそれぞれ のタスクの独立性を考慮したプログラムの改良や，Java 7から導入された並列処理のAPI
であるFork/Joinフレームワークを用いた並列処理の実装などを行っている．また，評価
実験においては，CodeTreeの処理速度とParallelCodeTreeの処理速度の比較だけでなく，
DGTreeの処理速度とも比較を行うことにより，現状で最も高速に動作するスーパーグラ
フ検索の手法が何であるかを明らかにする．
2
