DEIM Forum 2019 D7-2

FPGA を用いたグラフに対する正規パス問合せアクセラレータ
三浦 賢人†

天笠 俊之††博之††北川† 筑波大学 情報学群情報科学類 〒 305–8577 茨城県つくば市天王台１丁目１−１†† 筑波大学 計算科学研究センター 〒 305–8577 茨城県つくば市天王台１丁目１−１
あらまし正規パス問合せ (RPQ) はラベル付きグラフから指定されたエッジの並びをもつパスをグラフ内から探索し，そのパスの始点・終点ノードを返す問合せである．近年のデータ分析の対象データの大規模化の傾向から，RPQの対象となるグラフも大規模化が予想されており，RPQ 処理の高速化が求められる．この問題の解決策として考えられるのが FPGA である．FPGA は任意の論理回路をプログラミングによって自由に実装できるデバイスであり，任意の処理に特化した演算パイプラインをデバイス上に構成できるため，パイプライン化が効果的な処理では CPU や

GPU に比べて高い性能を得ることが可能である．本研究では，RPQ 処理を複数のステージに分割し，それらのステージを並列に実行するための演算パイプラインを FPGA 上に実装した．また，実験として性能調査を行い，結果として小規模なデータセットで比較手法に比べ最大で約 23.6 倍の高速化，大規模なデータセットで一部の問合せにおいて約 3.14〜4.61 倍の高速化を実現した．
キーワード FPGA, 正規パス問合せ
アの並列性を利用した並列度の高い処理が可能なことである．

1 はじめにグラフ構造は身の回りの様々なデータを表すのに効果的なデータ構造である．ビッグデータ分析などの普及に伴って，現在様々な分野でグラフ構造データが用いられている．
そのようなグラフ構造データからユーザの望むデータを抽出する方法の一つとして，正規パス問合せ (RPQ) [1] が存在する.

RPQ はエッジにラベルが付与されたグラフに対して行われる
問合せであり，指定されたエッジの並びをもつパスをグラフ内から探索し，そのパスの始点・終点ノードを返す．

RPQ を適用できる事例の一つとして Meta Path [2] が挙げられる．Meta Path は複数の種類のオブジェクトから構成されるヘテロジニアスなグラフにおいて，異なるオブジェクトタイ
プの間で定義された一連の関係からなるパスである．例として対象となる処理に特化した演算パイプラインを FPGA 上に実装することで，パイプライン化が効果的な処理の場合，CPUや GPU に比べてより高い性能を得ることできる．
以上の点を踏まえ本研究では，FPGA を用いた RPQ 処理の高速化手法を提案する．最終的には，RPQ に現れる様々な正規表現に対応することが目標であるが，本研究ではまず，特殊文字等の現れない簡単な正規表現の高速化を目標とした．
本稿の構成を以下に示す．2 節で前提知識，3 節で関連研究を紹介する．4 節で提案手法について述べ，5 節で実験の結果を示す．最後に 6 節で本研究のまとめを述べる．

2 前提知識2. 1 正規パス問合せ (RPQ)

著者 (A)，論文 (P)，テーマ (T)，学会 (C) の 4 つのオブジェ

正規パス問合せ (RPQ) は，ラベル付きグラフ中の任意の２クトからなるグラフの場合，CPAPC(ある 2 つの学会に共有さノード間に指定したパスが存在するかを調べる問合せである．

れる共通の著者) といった Meta-Path を定めることができる．

処理対象となるラベル付きグラフを G = (V, E, L) とする．V

RPQ を用いることによって，グラフ内における任意の Mataはグラフ内の頂点の集合，E はグラフ内のエッジの集合，L はPath の出現箇所を得ることが可能である．

グラフ中のエッジに対する全ラベルの集合である．さらに，エッここで課題としてあげられるのは，RPQ 処理の高速化であジ集合 E からラベル集合 L に対する写像関数 ϕ : E → L を定る．近年のデータ分析での対象データの大規模化の傾向から，義する．ここで，ℓ ∈ L とすると，以下のような RPQ 評価の

RPQ の対象となるグラフも大規模化が予想されており，RPQ

セマンティクス R が定められる．

の処理の高速化が求められる．
このような処理の高速化の分野で広く用いられているのが，GPU や FPGA などのハードウェアアクセラレータである．従来の CPU のみの環境に GPU や FPGA を組み合わせたヘテロ
ジニアスな計算機を構築することで高速化を目指すといった手法である．
特に FPGA は任意の論理回路をプログラミングによって自由に実装できるデバイスであり，その性能上の特徴はハードウェ

R ::= ϵ | ℓ | ℓ− | R ◦ R | R ∪ R | Ri,j(1)

ここで，ϵ は空列，ℓ はラベルを順方向に，ℓ− は逆方向にたどる表現であり，◦ は結合，∪ は和， Ri,j は R の k 回 (i <= j)=k<の繰り返し R· · ◦ R} を表す．例として，図 1 のグラフを Gex| ◦ ·{zk timesとし，RPQ : a ◦ b ◦ b を適用すると

a ◦ b ◦ b (Gex ) = {(2, 5)}(2)となる．この RPQ 処理では図中の赤色でハイライトされた

3. 3 RPQ 処理の高速化に関する研究

パスが検出され，最終的にその始点・終点ノードの集合であRPQ の評価手法として，オートマトンを用いた手法 [15]，る {(2, 5)} が得られる．本研究では簡単のため結合 (◦) のみの

Path Index を用いた手法 [16] などが挙げられる．オートマト

RPQ 処理の高速化を考える．結合以外の RPQ 処理への対応

ンを用いた手法では与えられた RPQ のクエリからオートマト

は今後の課題である．

ンを作成し，グラフに対して適応する．例として図 1 のグラフを対象に，R = a ◦ b ◦ b が与えられた場合，図 2 のようなオー
トマトンが作成され，図 1 内の全ノードを開始ノードとしてこのオートマトンが適応される．[15] ではグラフ内での出現頻度が低いラベルによってグラフを分割し，探索スペースを削減することでより効率的なオートマトンによる探索を実現している．
本手法は出現頻度の低いラベルの存在を必要としており，また，
そのラベルを適切に選択できるかどうかに性能が依存している．

図 1 RPQ の例 (R = a ◦ b ◦ b を適応)

2. 2 FPGA

図 2 クエリから作成されるオートマトン

FPGA(Field Programmable Gate Array) は様々な回路をプ
ログラムによって実装可能なハードウェアチップであり，一度実装された回路は application-specific integrated circuit(ASIC)のように動作させることが可能である．
従来，FPGA は Verilog や VHDL のようなハードウェア記

Path Index を用いた手法ではグラフ中のパスの登場を指定した長さ k まで, 事前にインデクシングしておく. 図 1 を例として，k=2 までのパスを全てインデクシングすると表 1 のようになる

述言語によってプログラムされることが一般的であり，大規模
表 1 Path Index

な回路を作成する場合の開発コストの高さが問題視されていた．しかし，近年では C/C++や OpenCL 等のより高レベルな言語によって FPGA 上の回路をプログラムできる高位合成(a) k = 1(b) k = 2

Path 始点・終点ノード

Path 始点・終点ノード

a

(1,5)

a◦b

(2,3)

(HLS) といった技術が確立されてきている [3] [4]．本研究では

a

(2,4)

a◦c

(1,4)

HLS を用いて FPGA 上への回路の実装を行なった．

b

(3,5)

b◦b

(4,5)

b

(4,3)

b◦c

(3,4)

c

(1,3)

c◦a

(2,5)

c

(2,1)

c◦b

(1,5)

c

(5,4)

c◦b

(5,3)

c◦c

(2,3)

3 関連研究3. 1 FPGA を用いた高速化の事例
FPGA を用いた処理の高速化の研究は広く行われており，
データベースに対する正規表現を含んだ問合せを FPGA を用
いて高速化する Sidler ら [5] の研究，PageRank [6] や協調フィ
ルタリング [7] などのグラフ分析処理を高速化する為の FPGA
アクセラレータ Graphicionado [8] などが挙げられる. また，商用システムの例では IBM 社の Netezza(現 PureData System

for Analytics [9]) が FPGA を用いて大幅なスループットの向上を達成している.

このように事前にインデクシングを行うことで，与えられた

RPQ のクエリの長さ |R| が |R| <= k だった場合は Path Index
内を検索するだけで結果を取得でき，|R| > k だった場合もPath Index を利用することで結果を得るために必要な結合処理の回数を少なくすることができる．例として RPQ : a ◦ b ◦ bが与えられた場合，Path Index を利用しない場合は a,b,b の

3. 2 RDF データやグラフ指向データベースに対する RPQ

エッジをその始点・終点ノードで結合するので 2 度の結合処理

RDF データやグラフ指向データベースにおける問合せ言語が必要だが，Path Index を用いる場合，a,b ◦ b または a ◦ b,bの分野でも RPQ は重要視されており，Oracle 社の開発したPGQL [10] が RPQ に対応している他，openCypher プロジェ
クト [11] や World Wide Web Consortium (W3C) [12] もそれぞれの開発した Neo4j cypher [13] や SPARQL 1.1 [14] に対して，RPQ への対応を進めている．

を結合すれば良いので，結合処理は 1 度で済む．また，この手法では Path Index 内のパスが何度グラフ中に出現するかを表すヒストグラムを事前に作成し，結合処理の中間結果が最小になるようにクエリプランを指定することで処理の高速化を図っている．

Path Index は RPQ 処理の高速化の面では効果的だが，パスの長さ k が増えるに連れてインデクシングされるパスの数が増加し，ストレージサイズを圧迫してしまうといった問題点も存在する．

4 提案手法
本研究では，FPGA 上で RPQ を並列に処理するための手法を提案する．RPQ 処理を複数のステージに分割し，FPGA 上
でパイプライン処理を行う．

4. 1 提案手法の処理の概要
図 3 に提案手法の処理の概要を示す．図の例はユーザから

RPQ : a ◦ b ◦ b を与えられた場合を表している，全体の処理は

図 4 グラフデータの保存形式

Host 側 (FPGA と通信を行う PC) で行われる処理と FPGA 側で行われる処理に分割される．まず，Host ではユーザから与えジ結合を行う．図 5(a) の例では，図 4 で示したラベル a のエッ

られた RPQ に出現するラベルを持つエッジのデータ (a ◦ b ◦ b

ジ群とラベル b のエッジ群の結合を行なっている．この場合の場合，ラベル a を持つエッジ群とラベル b を持つエッジ群)

Join モジュールはラベル a のエッジ群を終点ノード番号でソーを FPGA に転送する．FPGA は受け取ったエッジを RPQ のトしたエッジデータとラベル b のエッジ群を始点ノード番号

順番の通りに結合する．最終的に得られた結果は FPGA からでソートしたエッジデータを受け取って結合する．結果としてHost を通ってユーザへ送信される．

エッジ (2,4) と (4,3) が結合され (2,3) が Join モジュールから出力される．

Sort モジュールでは，入力されたエッジデータをバッファに保管し，バッファが満杯になるとバッファ内のエッジ群を終点
ノード番号でソートし，ソート後のデータを出力する．

図 3 提案手法の概要 (a ◦ b ◦ b を適応)

4. 2 Host 側 : グラフデータの保持
Host 側は処理対象のグラフ内の全てのエッジをラベル毎に分け，始点・終点ノード番号でそれぞれ昇順にソートして事前にストレージ領域に保管しておく．図 4 は図 1 のグラフを保管(a) Join モジュール(b) Sort モジュール

図 5 FPGA 上に実装するモジュールする場合の例である．
図 1 のグラフには 3 種類のエッジラベル a,b,c が存在する．
よって，ストレージにはラベル a を振られたエッジ群を始点
ノード番号でソートした a src，終点ノード番号でソートした

a dst, 同様にラベル b,c を始点・終点ノード番号でソートした
b src, b dst, c src, c dst が保存される．

4. 3. 2 エッジの結合処理
次に先ほどの 2 種類のモジュールを用いて FPGA 上で実際にどのように RPQ 処理を行うのかを示す．例として RPQ :a ◦ b ◦ b ◦ c が与えられた場合, 2 種類のモジュールを FPGA 上
で図 6 のような木構造に連結する．
図中の a dst, b src, c src は図 4 に示した Host 側のストレー

4. 3 FPGA 側の処理ジ領域から読みだしたエッジデータを表す．つまり，一番下の4. 3. 1 Sort・Join モジュールの実装

Join モジュールではラベル a のエッジデータとラベル b のエッ

概要で述べた通り，FPGA は Host から RPQ に登場するラジデータの結合を行い，結合結果はストリームデータとして 2ベルを持つエッジ群を受け取り，RPQ の順番通りに Join を段目の Sort モジュールに入力される．2 段目の Sort モジュー行う．この処理を効率的に行うために FPGA 上に図 5 に示す

ルではバッファサイズ分のデータを保存し，そのソートを行

Sort・Join モジュールを実装した．

う．ソート済みのデータは 1 段目の Join モジュールと同様にJoin モジュールでは，終点ノード番号でソートされたエッジ

ストリームデータとして出力され，3 段目の Join モジュール

群と始点ノード番号でソートされたエッジ群を受け取り，マーに入力される．3 段目の Join モジュールでは 2 段目の Sort モ

えた場合の例である．
この構成では RPQ で指定されたパスを二分割し (RPQ :図 8 2 つの演算パイプラインを用いる方法
図 6 FPGA 上の演算パイプライン

ジュールから受け取ったバッファサイズ分のエッジデータとラベル b のエッジデータを結合する．バッファサイズ分のデータを結合し終えると，2 段目の Sort モジュールから新たなエッジデータを受け取り，再度ラベル b のエッジデータの先頭から結合を行う．3 段目の Join モジュールはこの処理を 2 段目のSort モジュールからデータが入力される限り繰り返す．4 段目の Sort モジュールは 2 段目と同様の処理を行い，5 段目の Join
モジュールも 3 段目と同様に 4 段目の Sort モジュールから受け取ったエッジデータとラベル c のエッジデータの結合処理を
データが入力される限り繰り返す．最終的に 5 段目の Join モ
ジュールから出力される結果が RPQ : a ◦ b ◦ b ◦ c の結果となる．
以上の点を踏まえ，全体の処理の流れを示すと図 7 のようになる．Host 側は FPGA 上の演算パイプラインに RPQ 処理に必要なエッジデータを与え，FPGA 側は与えられたエッジデー
タを用いて演算を行い，結果を Host 側に返す．

図7

a ◦ b ◦ b ◦ c ◦ b ◦ a の場合は a ◦ b ◦ b と c ◦ b ◦ a に分割) 二つの演算パイプラインで並列に結合処理を行う．パスを二分割したことによってパイプライン一つあたりの長さが短くなったた
め，全てのモジュールにデータが行き渡りやすくなり，より並列度の高い処理が可能となる．また，最終的な RPQ の結果を導出するためには演算パイプライン 1 と演算パイプライン 2 の結果を結合する必要があるが，この結合を FPGA 上で行う場
合，演算パイプライン 1 と演算パイプライン 2 の結果を FPGA
外のオフチップメモリに一旦保存し，2 つのパイプラインの実行が終了した後に結合処理を行う必要がある．一般にオフチッ
プメモリへのアクセスは低速であるためこれは好ましくない．
よって，最終的な結合は対象となる演算パイプライン 1 と 2 のデータを Host 側に送信した後，Host 側でハッシュ結合を行うこととした．前述の構成と区別するため，1 つの演算パイプラ
インを用いる構成をシリアルな構成，2 つの演算パイプラインを用いる構成をパラレルな構成と呼ぶ．本構成の最終的な流れを図 9 に示す．

全体の処理の流れ

図 9 パラレルな構成での処理の流れ

4. 3. 3 処理の並列度を高めるための構成
図 6 に示した演算パイプラインにおいて，最も処理の並列度が高くなるのは全てのモジュールが稼働している場合である．

5 実

験

しかし，各 Sort モジュールでデータのバッファリングが行われ提案手法の性能を評価するため，以下に示す 2 つのデータ

るため，パイプライン長が長くなるほど，上段付近のモジューセットを用いて評価実験を行なった．データセットの規模がルにデータが行き渡るまでに時間がかかるといった問題点が考小さく 3. 3 節で示した Path Index を適応できる場合は Path

えられる．この問題点を緩和するため，図 8 に示す演算パイプ

Index を，規模が大きく適応できない場合は PostgreSQL によ

ラインの構成を考案した．図は RPQ : a ◦ b ◦ b ◦ c ◦ b ◦ a を与る結合処理を用いて本手法と比較した．Path Index には Index

の使用方法やクエリプランの決定方法が数種類存在するが，多くの場合で最も良い結果を示した MinJoin 方式との比較を行

5. 3 小規模グラフに対する性能
本実験では advogato を用いて，RPQ のパスの長さ |R| を変なった．

化させた際の，提案手法と比較手法の性能の比較を行なった．

5. 1 実 行 環 境

比較手法は Path Index の長さを,1 <=k<= 3 として性能を測定した．実験の結果は正規表現の長さ毎に，無作為に選択した 10

本実験の実行環境を表 2 に示す．

個のクエリを実行しその実行時間の平均をとったものである．
また，パラレルな構成ではパスを二分割するため，|R| >=4の

表2 実行環境

CPU

インテル Core i7-7700K 3.60 GHz × 8

場合にしか適応できない．よって，その場合のみで結果を測定

OSLinux version 3.10.0

した．なお，演算パイプラインのバッファサイズには 8192 エッ

メモリ

31.1GiB

コンパイラ

gcc-4.8.5

FPGA

Xilinx Kintex UltraScale FPGA KCU1500

RDBMS

PostgreSQL 9.2.24

ジを指定した．結果を表 5 に示す．
結果としてシリアルな構成の場合，|R| = 2 の場合には提案
手法は比較手法よりも速度が遅かったが，|R| >= 3 の場合では，各パス長で比較手法の最も高速であった物と比べ，約 1.72〜

2.31 倍の高速化が得られた．また，パラレルな構成では更なる高速化がみられ，|R| = 4, 5 の場合で比較手法に比べ約 15.3〜

5. 2 データセット
本 実 験 で は デ ー タ セット と し て advogato [17] と DBLP-

Citation-network V10 [18] を用いた．詳細を以下に示す．
5. 2. 1 advogato
advogato は、フリーソフトウェアの開発者向けのオンライ
ンコミュニティプラットフォームから作成された有向グラフで，プラットフォームを利用するユーザ同士の信頼関係をラベル付
きエッジで表したものである．advogato の情報を表 3 に示す．

23.6 倍高速だった．
5. 4 大規模グラフに対する性能
本実験では DBLP-Citation-network V10 から作成したグラ
フデータを用いて実験を行なった．本グラフデータではパスの並びに制限があるため (例. writing ◦ publishing を満たすパス
はグラフ中に存在しない)，クエリを無作為に選択するのではなく以下に示す q1 ∼ q5 までの 5 種類のクエリを用いて実験を行なった．

表 3 advogato
ノード数

エッジ数

ラベルの種類

6,541

51,1273

q1 :R = writing ◦ written byq2 :R = writing ◦ citing ◦ written by(ノードタイプ APA の並び)
(ノードタイプ APPA の並び)

5. 2. 2 DBLP-Citation-network V10
DBLP-Citation-network は，コンピュータサイエンスに関

q3 :の論文データを集めたデータセットであり，各論文データに

q4 :引用論文 id，学会のデータを抽出し，論文 (P)，著者 (A)，学会 (C) をノードとしたヘテロジニアスなグラフデータを作成した．エッジは P 同士や P とその他の種類のノードとの関係
writing

written by

publishing

を表し，A −−−−−→ P ，P −−−−−−−→ A， C −−−−−−−→ P ，published incitingcited by

R = publishing ◦ written by ◦ writing ◦ published in(ノードタイプ CPAPC の並び)

は論文 id，タイトル, 著者，引用論文 id， 学会 などの情報が含まれている．本実験ではこの論文データから論文 id，著者，

R = writing ◦ published in ◦ publishing ◦ wiritten by(ノードタイプ APCPA の並び)する書誌学ウェブサイトである DBLP から収集した約 300 万

q5 :R = writing ◦ citing ◦ published in ◦publishing ◦ citing ◦ written by(ノードタイプ APPCPPA の並び)

なお，クエリで指定されたパスを満たすすべての始点・終点ノードペアを列挙すると結果数が膨大になってしまうため，始点

P −−−−−−−−→ C ，P −−−−→ P P −−−−−→ P の 6 種類のラベノードのみ特定ノードへの指定を行なった (著者ノード (A) かルを付与した．作成したグラフデータの情報を表 4 に示す．

ら始まるクエリの始点ノードには”北川博之”教授を，学会ノー

表 4 DBLP-Citation-network V10 から作成したグラフデータ
ノード数 (P:A:V)

エッジ数

4,850,632(3,079,007:1,766,547:5,078) 38,973,022

ド (C) から始まるクエリの始点ノードには”very large databases”を指定した)．

ラベルの種類

本実験では大規模なデータセットを用いたため，ストレージ

6

サイズの問題から Path Index を作成することが出来なかった(k ＝ 2 の Path Index で数十 GB 以上)．よって PostgreSQL
を用いて表 5. 4 に示すスキーマ構造のテーブルを作成し，以下の例のようなクエリを与えて比較手法として用いた．
クエリの例 (q1 と同義) :SELECT e1.src, e2.dst FROM edges AS e1, edges AS e2
WHERE e1.src = 260069 e1.label id = 0 AND e2.label id =1 AND e1.dst = e2.src;

表 5 小規模グラフに対する性能 (advogato)

Length of R Proposed method
serial (ms)

Proposed method
parallel (ms)Path Index
k = 1 (ms)Path Index
k = 2 (ms)Path Index
k = 3 (ms)

2

133

N/A

47

39

44

3

324

N/A

624

589

556

4

2275

340

6217

5203

5523

5

39238

3848

11046010300790622

特性に大きな変化がみて取れた．小規模なデータセットの場

表 6 テーブルのスキーマ構造(a) edges(b) labels

合では，比較手法に比べて高速に処理を行うことが可能だが，

src

dst

label idlabel idlabel

163954

1766548

0

0

writing

1766548..
.

163954
..
.

1
..
.

1

written by2

publishing加が挙げられる．1 段目以外の Join ステージでは下の Sort ス

3published in

テージからバッファサイズ分のデータを受け取り，結合候補の

4

citingエッジ群の先頭から末尾に向けて比較・結合処理を行い，バッ

5cited by

ファサイズ分のデータを結合し終えると，新たなデータを Sort

データセットが大規模になると本手法の実行速度に大幅な低下がみられた．この要因として，Join ステージでの結合候補の増ステージから受け取りまた結合候補のエッジ群の先頭から比較・(ノード番号 260069 は”北川博之”教授を表す著者ノードを指す)
なお，本実験では演算パイプラインのバッファサイズとして32768 エッジを指定した．本実験の結果を表 7 に示す.

結合処理を行う．つまり，結合候補のエッジ数が多くなるに連れて比較しなければならないデータが増え結合処理のコストが増加する．大規模なデータセットにおいてバッファサイズが性能に与える影響が顕著である点もこの Join ステージでの処理に起因すると考えられる．バッファサイズが大きいほど一度の

表 7 大規模グラフに対する性能 (DBLP-Citation-network V10

結合処理で処理できるデータ数が増え，結合候補のエッジ群を

Proposed method
parallel (ms)PostgreSQL(ms)

先頭から読み直す回数が減るためである．逆にバッファサイズ
いので大幅に性能が低下する．つまり現在の演算パイプライン

Querys Proposed method
serial (ms)
q1

434

N/A

17

q2

884

N/A

40

q3

8820

1540

4836

q4

10551

1659

7644

q5

183084

93913

46719

本実験の結果として，シリアルな構成の場合，すべてのクエが小さいと何度も結合候補を先頭から読み直さなければならなの構成で，大規模なデータセットを処理する上でのボトルネッ
クとなっているのは，1 段目以外の Join ステージでの結合候補の読み直しのコストであると考えられる．

6 ま と めリにおいて PostgreSQL での実行速度よりも低速であった．パ

本研究では FPGA を用いた RPQ 処理の高速手法を提案しラレルな構成の場合，q3 , q4 の場合は PostgreSQL に比べて約た．FPGA 上に Join と Sort の二種類のモジュールを実装し，3.14〜4.61 倍高速だったが，q5 の場合では PostgreSQL の実行

それらを連結させ RPQ 処理を並列に実行するための演算パイ

速度よりも低速で，約 2 倍の実行時間がかかった．

プラインを構成した．結果としてデータセットが小規模な場合

5. 5 バッファサイズによる性能の変化
本実験ではシリアルな構成において上記の 2 つの実験で，Sort モジュールのバッファサイズを変化させた場合に性能にどのような影響が出るのかを調査した．また，|R| = 2 の場合はSort モジュールを使用しないため，|R| >= 3 の場合で調査を行なった．バッファサイズは 2048,4096,8192,16384,32768 の 5 種類を選択した．結果を表 8，9 に示す．
結果から，小規模なデータセット (advogato) の場合ではバッ
ファサイズの影響は微々たるものだが，大規模なデータセット(DBLP-Citation-network V10) の場合ではバッファサイズが性能に大きな影響を与えていることがみて取れる．

5. 6 考察

本手法では用いるデータセットの規模によってその性能上のでは最大で約 23.6 倍の高速化が得られた．現時点の課題として，データセットが大規模になるに連れて性能が低下すること
や，バッファサイズの値によって実行速度に影響が出やすくなるなどの性能上での課題や本手法で対象としなかった，和演算や繰り返し処理などを含む RPQ に対応するなどの課題が挙げられる．よって，今後はそれらの課題を解決するための手法を模索していく予定であり，また，3. 2 節で示したような RDF
データやグラフ指向データベースに対する RPQ 処理と本手法との比較を行うことを考えている．

表 8 バッファサイズによる性能の変化 (advogato)

Buﬀer size = 2048
Length of R
(ms)

Buﬀer size = 4096
(ms)

Buﬀer size = 8196
(ms)

Buﬀer size = 16384(ms)

Buﬀer size = 32768
(ms)

3

350

340

324

338

351

4

2428

2379

2275

2365

2952

5

43580

41623

39238

38870

40963

表 9 バッファサイズによる性能の変化 (DBLP-Citation-network V10)

Buﬀer size = 2048
(ms)

Buﬀer size = 4096
(ms)

Buﬀer size = 8196
(ms)

Buﬀer size = 16384(ms)

Buﬀer size = 32768
(ms)

q1

413

415

414

399

434

q2

2678

825

870

867

884

q3

102392

59624

29753

14254

8820

Querys

q4

93619

54979

26173

12454

10551

q5

23931101204940645820343709183084文献agement of Data, SIGMOD ’18, pp. 1433–1445, New York,NY, USA, 2018. ACM.
SPARQL 1.1 Query Language. https://www.w3.org/TR/
sparql11-query/.
André Koschmieder and Ulf Leser. Regular path queries onlarge graphs. In Anastasia Ailamaki and Shawn Bowers, editors, Scientific and Statistical Database Management, pp.
177–194, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
George H. L. Fletcher, Jeroen Peters, and Alexandra Poulovassilis. Eﬃcient regular path query evaluation using pathindexes. In Proceedings of the 19th International Conference on Extending Database Technology, EDBT 2016, Bordeaux, France, March 15-16, 2016, Bordeaux, France, pp.
636–639, March 2016.
Paolo Massa, Martino Salvetti, and Danilo Tomasoni. Bowling alone and trust decline in social network sites. In In
Proc. Int. Conf. Dependable, Autonomic and Secure Computing, pp. 658–663, 2009.
[18] Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang,
and Zhong Su. Arnetminer: Extraction and mining of academic social networks. In Proceedings of the 14th ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08, pp. 990–998, New York,NY, USA, 2008. ACM.

[1] Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood.
[14]
A Graphical Query Language Supporting Recursion. SIGMOD Rec., Vol. 16, No. 3, pp. 323–330, December 1987.
[15][2] Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S. Yu, andTianyi Wu. Pathsim: Meta path-based top-k similarity
search in heterogeneous information networks. In VLDB
11, 2011.
[3] Intel. Intel FPGA SDK for OpenCL Pro Edition Program[16]ming Guide. https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/opencl-sdk/aocl_
programming_guide.pdf.
[4] Xilinx. Vivado Design Suite User Guide High-Level Synthesis. https://www.xilinx.com/support/documentation/sw_
manuals/xilinx2017_4/ug902-vivado-high-level-synthesis.
[17]
pdf.
[5] David Sidler, Zsolt István, Muhsen Owaida, and Gustavo
Alonso. Accelerating pattern matching queries in hybrid
cpu-fpga architectures. In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD’17, pp. 403–415, New York, NY, USA, 2017. ACM.
[6] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry
Winograd. The pagerank citation ranking: Bringing orderto the web, 1999.
[7] D. Agarwal and B.-C. Chen. Machine learning for large
scale recommender systems, 2011.
[8] T. J. Ham, L. Wu, N. Sundaram, N. Satish, and
M. Martonosi. Graphicionado: A high-performance andenergy-eﬃcient accelerator for graph analytics. In 2016 49th
Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pp. 1–13, Oct 2016.
[9] Introducing the next step in Netezza s evolution: IBM Integrated Analytics System. https://www.ibm.com/us-en/
marketplace/puredata-system-for-analytics.
[10] Oskar van Rest, Sungpack Hong, Jinha Kim, Xuming Meng,and Hassan Chafi. Pgql: A property graph query language. In Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems, GRADES ’16, pp. 7:1–7:6, New York, NY, USA, 2016.
ACM.
[11] openCypher. http://www.opencypher.org/.
[12] World wide web consortium. https://www.w3.org/.
[13] Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid
Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor.
Cypher: An evolving query language for property graphs. In
Proceedings of the 2018 International Conference on Man-