DEIM Forum 2016 F7-2

外部記憶アルゴリズムを用いた大規模グラフデータからのスキーマ抽出手法
関根

吉紀†

池田

光雪††

鈴木

伸崇†††

† 筑波大学 情報学群 知識情報・図書館学類 〒 305-8550 茨城県つくば市春日 1-2†† 筑波大学 大学院図書館情報メディア研究科 〒 305-8550 茨城県つくば市春日 1-2††† 筑波大学 図書館情報メディア系 〒 305-8550 茨城県つくば市春日 1-2
E-mail: †s1211512@klis.tsukuba.ac.jp, ††{lumely,nsuzuki}@slis.tsukuba.ac.jp
あらまし

本稿では，グラフデータからスキーマ抽出を行うための外部記憶アルゴリズムを提案する．ここで，外部

記憶アルゴリズムとは，主記憶上での処理が困難な大規模なデータを効率良く処理するためのアルゴリズムのことをいう．提案アルゴリズムは，増分クラスタリング法（incremental clustering method）に基づいて，各ノードが属するクラスの抽出と，それらクラス間のエッジを抽出することにより行われる．評価実験では，使用したデータは限られているものの，入力データサイズに対してほぼ線形の実行時間でスキーマ抽出が可能であり，スキーマ抽出中の主記憶使用量は入力データサイズよりも十分小さいという結果が得られた．
キーワード

グラフデータ，スキーマ，RDF

1. は じ め になすべての情報を主記憶に格納し処理していたのに対し，本研究では，グラフデータをシーケンシャルに読み込み，必要なデータを保存，管理する一般的な手段として関係データベー

データのみを主記憶上に置き逐次的にクラス抽出を行う．また，ス（RDB）がある．RDB を使用するときには，データを格納

スキーマ抽出に必要だが主記憶に乗り切らない情報は外部ファする前に必ずスキーマを設計し，そのスキーマと一致するよう

イルに書き出し，それらも同様にシーケンシャルに読み込んでにデータを格納しなければならない．スキーマはこのように分析・処理することによってスキーマ間のエッジ抽出を実現しデータの構造を規定するほか，ユーザが問合せ式を記述する際ている．外部記憶アルゴリズムは通常 C 言語のような比較的低の手助けとなる，問合せ処理系の問合せ実行効率を向上させる

水準な言語で実装されることが多いが，このようにデータを処という 2 つの重要な恩恵を与える．

理することで，Ruby のような高水準言語でも大規模データ処

一方，人間同士の関係や交通ネットワークのような，RDB

理を実現できる．評価実験では，使用したデータは限られていでは扱いにくいデータを保存，管理する手段としてグラフデー

るものの，入力データサイズに対してほぼ線形の実行時間でス

タが広く用いられている．グラフデータにおいてはスキーマをキーマ抽出が可能であり，スキーマ抽出中の主記憶使用量は入設計する必要は通常ないため，スキーマが付与されているグラ力データサイズよりも十分小さいという結果が得られた．

フデータは稀である．しかし，そのようなグラフデータにおい

グラフデータからスキーマを抽出する先行研究として，グラてもスキーマを抽出できれば先述の恩恵を受けることができる．

フ上のあるノードから同じパスで到達する 1 つ以上のノード

近年，計算機の処理能力の向上や HDD 等の外部記憶装置のを，スキーマの 1 つのノードとして写像してスキーマを求める

低価格化と大容量化によって，計算機上で処理・蓄積されるデー

もの [1]，その近似解を求めるもの [2]，各ノードについて，接タが大幅に増加している．このため，主記憶のサイズを大幅に続しているエッジラベルが類似しているノードを 1 つのクラス

超えるデータを処理することのできるアルゴリズムが必要とさにまとめるもの [3]，グラフの要約を求めるもの [4] などがある．

れている．しかし，これまで提案されてきたスキーマ抽出アル[1] は処理コストが高く，閉路を含むグラフに対応困難である．

ゴリズムは，データを主記憶に格納し処理することを前提とし[2] は [1] に比べて処理コストが低いが，閉路を含むグラフに対ているため，データが非常に大きい場合には適用困難である．

応できない場合があり，近似解しか得られない． [3] はパスの探

そこで本研究では，サイズが大きく全体を主記憶上で処理で索を行わないため， [1] や [2] に比べて効率がよく，閉路を含む

きないグラフデータに対応したスキーマ抽出手法を提案する．

グラフにも対応可能である． [4] はエッジのラベルや向きがな

スキーマ抽出は，各ノードが属するクラスの抽出と，それらクいグラフデータに対する手法である．以上のアルゴリズムはいラス間のエッジを抽出することにより行われる．具体的には，ずれも外部記憶アルゴリズムではないため，主記憶のサイズを増分クラスタリング法（incremental clustering method）を用

超えるデータは扱うことができない．グラフに関する外部記憶いた作成法である先行研究 [3] のアルゴリズムを外部記憶アルアルゴリズムとしては，グラフの強連結成分を求めるもの [5]，ゴリズムとして拡張し，さらにクラスの抽出法にも改良を加え到達可能性を判定するもの [6]，三角形分割問題を解くもの [7]る．先行研究では，グラフデータも含む，スキーマ抽出に必要がある．しかし，グラフデータからスキーマを抽出する外部記

作成

s0

p0

s0 作成 p0

t0

支援s1 参加 p0
s1 参加 p1

参加

s1 作成 p2
s2 参加 p2

参加

s1

p1

t1

作成

t0 支援 p0t1 作成 p1

作成

t2 支援 p2

図 2: グラフを格納するファイルの例

参加

s2

p2

t2

支援

作成

図 1: グラフの例
v̄0

憶アルゴリズムは我々の知る限り存在しない．

支援

v̄1

v̄2

参加

本稿の構成は以下の通りである．第 2 章ではグラフ関連の定作成

図 3: 抽出されたスキーマの例

義を述べる．第 3 章では提案手法について述べる．第 4 章では評価実験について述べる．第 5 章では本稿のまとめを述べる．

s0 v̄0s1 v̄02. 諸 定 義
本章では，本研究で扱うグラフとそのスキーマに関する定義について述べる．

s2 v̄0v̄0 作成 v̄1

p0 v̄1v̄0 参加 v̄1

p1 v̄1v̄2 支援 v̄1

2. 1 グ ラ フ

p2 v̄1v̄2 作成 v̄1

ラベル付き有向グラフ（以下，単にグラフ）を G = (V, E)と表す．ここで V はノードの集合，E はラベル付き有向エッ

t0 v̄2(a) クラス間のエッジを格納

t1 v̄2

するファイルの例

t2 v̄2ジの集合である．エッジは両端にノードをもち，それらを端点(b) ノードとそれが属するクと呼ぶ．ノード u ∈ V を始点とし，ノード v ∈ V を終点とす

ラスを格納するファイルの例

l

る有向エッジ e ∈ E のラベルが l であるとき，e = u → v と表す．このようにエッジ e で u, v が結ばれているとき，u, v は隣

図 4: スキーマを格納するファイルの例

接していると言い，エッジ e はノード u または v に接続していると言う．ノードに接続しているエッジのうち，そのノードをキーマ抽出ではグラフのすべてのノード（葉ノードを除く場合終点とするエッジを入力エッジ，始点とするエッジを出力エッもある）をクラスに写像するため，クラスは元のグラフの 1 つ

ジと呼ぶ．

以上のノードと対応している．クラス間のエッジには，対応し

例 と し て ，図 1 に 学 生 や 先 生 と 活 動 プ ラ ン の 関 係を表すグラフ G=(V, E) を 示 す．こ こ で ，V{s0 , s1 , s2 , t0 , t1 , t2 , p0 , p1 , p2 }，E
参加

作成

参加

=
支援

{s0

作成

→

p0 , s 1

作成

=
参加

→

支援

p0 , s1 → p1 , s1 → p2 , s2 → p2 , t0 → p0 , t1 → p1 , t2 → p2 }ている元のグラフのノード間のエッジが張られる．図 1 のグラフから抽出したスキーマの例を図 3 に示す．s0 , s1 , s2 は v̄0 に，

p0 , p1 , p2 は v̄1 に，t0 , t1 , t2 は v̄2 に対応している．このとき，
s0 , s1 , s2 はクラス v̄0 に属すると言う．

である．学生の集合を {s0 , s1 , s2 }，先生の集合を {t0 , t1 , t2 }，本研究では，スキーマは 2 つのファイルで構成される．1 つ活動プランの集合を {p0 , p1 , p2 } とする．このグラフにおいて，目はクラス間のエッジを格納するファイルである．Notation3

ノードは個々の人間や活動プラン，有向エッジはそれらの関係のように，各行に「始点」「端点を結ぶエッジのラベル」「終点」

を表し，エッジにつけられたラベルは始点を主語，終点を目的を記述する．2 つ目は，元のグラフデータのノードとその属す語とする動詞である．

るクラスを格納するファイルである．各行に「グラフのノード」

本研究では，グラフを格納するファイルとして，Resource De-

scription Framework（RDF）の記法の一つである Notation3のように，各行に 1 つのエッジの情報が書かれているものを考える．具体的には，各行が「始点」「端点を結ぶエッジのラベル」「終点」の 3 つで構成されているファイルである．図 1 のグラフデータをこの記法で表現した例を図 2 に示す．

と「それが属するクラス」を記述する．図 3 のスキーマをこれ
らの記法で表現した例を図 4 に示す．

3. 提 案 手 法スキーマ抽出は各ノードが属するクラスを決定すること（クラス抽出）と，それらクラス間にエッジを張ること（エッジ抽

2. 2 グラフにおけるスキーマ

出）の二段階からなる．我々は増分クラスタリング法を用いたスキーマは元のグラフを要約した概形であり，スキーマ自体

スキーマ抽出アルゴリズム [3] におけるクラス抽出手法を拡張

もグラフである．以下，スキーマのノードをクラスと呼ぶ．ス

し，さらに全体を外部記憶アルゴリズムとした．本章ではまず，

クラス抽出時に用いる効用値の定義を行い，次に提案する外部記憶アルゴリズムについて述べる．

3. 1 準入出力エッジに対する効用値 U を，入力エッジに対する効用値と出力エッジに対する効用値の線形和と定義する．

備

U = αUin + βUout ,本手法はラベル付き有向グラフを入力とし，各ノードに接続

α+β =1するエッジのラベルが類似しているノードを同じクラスにまと効用値は，接続するエッジのラベルが類似したノードが同じクめる手法である．なお，軽微な修正でラベル付き無向グラフにラスにまとまっているほど大きい値となる．この値が高いほども適用可能である．

スキーマの質が高いとみなし，クラス抽出の際に用いる．

クラス抽出を行う際，文献 [3] では入力エッジと出力エッジを

3. 2 提 案 手 法

区別せずに効用値（utility value）を計算するため，分けられ[3] のアルゴリズムは，ノードの属するクラスの情報などのるべきノードが同じクラスになるという問題があった．そこでスキーマ抽出に必要となるすべての情報を主記憶上に格納し，提案手法では効用値の定義を拡張し，入力エッジと出力エッジ

データの任意の場所にアクセスして処理することを前提としてそれぞれの効用値を計算し，その線形和をクラス抽出に用いる．

いる．しかし，データサイズが非常に大きい場合，必要となる

ノード vi の入力エッジの集合を R(vi )，出力エッジの集合

すべての情報は主記憶に格納できないため，このアルゴリズム

を A(vi ) と表す．クラス v̄i の入力エッジの集合を R(v̄i ) =∪vi ∈v̄i R(vi ) とし，同様にクラス v̄i の出力エッジの集合を∪A(v̄i ) = vi ∈v̄i A(vi ) とする．

をそのまま用いて処理することは困難である．
そこで提案手法では，グラフデータをシーケンシャルに読み込み，必要最低限のデータのみを主記憶上に格納し逐次的にククラス v̄i に属するノードのうち，入力エッジにラベル l をもラス抽出を行う．また，クラス間のエッジ抽出に必要だが（サつノードの割合を Pin (l|v̄i ) と表す．これが高いほど，クラス

イズの都合上）主記憶に格納することが困難な情報は外部ファv̄i に属しているノードは入力エッジにラベル l をもつことにな

イルに書き出す．それらをシーケンシャルに読み込んで分析・る．これに対して，すでにクラスに属するノードの中で，入力処理することによってクラス間のエッジ抽出を実現する．

エッジにラベル l をもつノードのうち，クラス v̄i に属するノー

本手法は（1）前処理，（2）クラス抽出，（3）エッジ抽出の 3

ドの割合を Pin (v̄i |l) と表す．これが高いほど，入力エッジにラ段階からなり，図 2 のようなグラフデータを与えると，そのス

ベル l をもつノードがクラス v̄i に属していることになる．入力

キーマを抽出する． 3. 1 節で述べた通り，入出力エッジを区別

エッジのラベル l とクラス v̄i の関係性の高さ Tin (l, v̄i ) と，ク

する効用値を用いてクラス抽出を行う．なお， [3] では指定しラス v̄i におけるその平均 Ein (v̄i ) を次のように定義する．

たルートノードから深さ優先順にクラスを抽出するが，本研究Tin (l, v̄i ) = Pin (l|v̄i ) · Pin (v̄i |l)Ein (v̄i ) =∑1|R(v̄i )|Tin (l, v̄i )l∈R(v̄i )でのクラス抽出はノード名のアルファベット順である．
処理手順の概要を以下に示す．
入力: グラフ（各行が「始点」「端点を結ぶエッジのラベル」「終点」で構成されるファイル．以下，ファイル 1）

入力エッジに対する効用値 Uin は各クラスにおける Ein (v̄i ) の

出力: 入力グラフから抽出したスキーマ

平均値である．K をクラスの総数（スキーマのノード数）とし処理内容:

たとき，次のように定義する．

（ 1 ） 前処理

1 ∑
Ein (v̄i )
K i=1
K

Uin =

出力エッジに対しても同様に，クラス v̄i に属するノードの（ a ） ファイル 1 を 1 行ずつ読み込み，始点と終点を入れ換
え，「終点」「端点を結ぶエッジのラベル」「始点」の順にしてファイル 2 に書き出す．この操作をファイル 1 の最終行まで行う（ b ） ファイル 1 とファイル 2 を外部ソートする．その結果

うち，出力エッジにラベル l をもつノードの割合を Pout (l|v̄i )をそれぞれファイル 3，ファイル 4 とすると表し，すでにクラスに属するノードの中で，出力エッジにラ（ 2 ） クラス抽出

ベル l をもつノードのうち，クラス v̄i に属するノードの割合（ a ） ファイル 3 とファイル 4 を並行してシーケンシャルにを Pout (v̄i |l) と表す．出力エッジのラベル l とクラス v̄i の関係

読み込む性の高さ Tout (l, v̄i ) と，クラス v̄i におけるその平均 Eout (v̄i )，（ b ） 効用値を計算し，1 ノードずつクラスを抽出する

出力エッジに対する効用値 Uout を入力エッジと同様に次のよ（ c ） クラス抽出を終えるたびに，ノードとクラスの対応関うに定義する．

係をファイル 5 に書き出し，そのノードの出力エッジの情報をTout (l, v̄i ) = Pout (l|v̄i ) · Pout (v̄i |l)Eout (v̄i ) =Uout =∑

1|A(v̄i )|
K
1 ∑

K i=1

Tout (l, v̄i )l∈A(v̄i )ファイル 6 に書き出す（ 3 ） エッジ抽出（ a ） ファイル 6 を外部ソートする．その結果をファイル 7とする（ b ） ファイル 5 と，ファイル 7 を並行してシーケンシャル

Eout (v̄i )に読み込む（ c ） クラス未特定のノードのクラスをファイル 5 から特定

Algorithm 1 クラス抽出する

1: ファイル 3 から 1 行読み込む．
「始点」を v とする（ d ） クラス間のエッジを張る

2: ファイル 4 から 1 行読み込む．
「終点」を u とする

以下，上記処理手順の詳細を述べる．

3: while ファイル 3 とファイル 4 の少なくとも一方が EOF でないdo

3. 2. 1 前 処 理

4:スキーマ抽出の対象となるグラフデータは，「始点」「端点を5:結ぶエッジラベル」「終点」の順で 1 行が構成されているファ

6:

end while

イルである（ファイル 1）．ノードに接続するすべての出力エッ

7:current = min{u, v}

ジをシーケンシャルな読み込みで特定するために，ファイル 1

8:

行目からシーケンシャルに読み込むことで出力エッジは特定でイル 1 の始点と終点を入れ換え「終点」「端点を結ぶエッジのラベル」「始点」の順で各行が構成されるファイル（ファイルファイル 3 とファイル 4 をシーケンシャルに読み，current の9:

効用値を計算し，current のクラス c を抽出

10:

current とそれが属するクラスの対応をファイル 5 に出力
current の各出力エッジに対して，「始点」を c に置き換えたも

11:

きる．しかし，ノードの入力エッジを特定するためにはファイル 3 全体を参照する必要が生じる．これを回避するため，ファファイル 4 を 1 行読み込む．
「終点」を u とする

入力エッジと出力エッジを集めるをアルファベット順に外部ソートする（ファイル 3）．ファイル

3 は同じ始点をもつエッジが連続して出現するので，これを 1

while u が葉ノードの場合 doのをファイル 6 に出力
ファイル 3 の現在行の「始点」を v ，ファイル 4 の現在行の12:「終点」を u とする
13: end while2）を作成し，外部ソートする（ファイル 4）．ファイル 4 は同
じ終点をもつエッジが連続して出現するので，各ノードの入力が構成されるようにする．これは，次のエッジ抽出において終エッジをシーケンシャルな読み込みで特定できる．

点でソートを行うからである．

3. 2. 2 クラス抽出

3. 2. 3 エッジ抽出

効用値の計算に必要で，主記憶に格納し続けるデータは，「各

エッジ抽出の流れを Algorithm 2 に示す．まずファイル 6 をクラスに属するノードの数」，「各クラス v̄ と v̄ の各ラベル l に

外部ソートする（ファイル 7，1 行目）．ファイル 7 は同じ終対して，v̄ において l をもつノードの数」の 2 つである．後者

点をもつエッジが連続して出現するので，そのノードのクラス

は，入力エッジと出力エッジを分けて保存する．なお，主記憶をファイル 5 からシーケンシャルな読み込みで特定できる．具にはノードに接続するエッジのラベルや出力先の隣接ノードも体的には，ファイル 7 を 1 行読み，あるクラスを始点とし，ク格納するが，そのノードのクラス抽出が終わった時点で破棄さラス未特定のノードを終点とするラベル付きエッジを得る．それる．

の終点ノードの属するクラスをファイル 5 から特定することにクラス抽出の流れを Algorithm 1 に示す．前処理でソート済

よってエッジ抽出を行う（5〜17 行目）．なお，クラスから葉みの 2 つのファイル（ファイル 3，4）はアルファベット順に並ノードに向かうエッジの出力先のクラスは NIL とする (5〜6 行

んでいるため，両ファイルの先頭を確認，比較して小さい方の目)．また，同一のエッジがすでに存在した場合は張らないこと

ノードからクラス抽出を行う（7〜9 行目）．ただし，葉ノードとする．

のクラスは NIL とし，クラス抽出は行わない（4〜6 行目）．そ3. 3 I/O コストのノードに接続するエッジがすべて得られたら，そのノードの

上記アルゴリズムの I/O コストを考える．G(V, E) のノークラスを抽出する．

ド数を |V |，エッジ数を |E|，B を主記憶と外部記憶との間でクラス抽出は元のアルゴリズム [3] の通り，既存のクラスが行われるブロック転送のサイズとする．また，O(sort(|E|)) はない場合は新規クラスを作成し割り当て，既存のクラスがある

マージソートのオーダーを表している．例えば，2-way マージ

場合は既存の各クラスに割り当てたときの効用値と，新しいクの場合

大きいクラスにそのノードを割り当てる（9 行目）．
ノードのクラス抽出を終えるたびに，次のエッジ抽出で必要な情報を書き出す．クラス間にエッジを張るためには，「クラスを始点とし，（クラス未特定の）ノードを終点とするエッジ」と，（クラス未特定の）ノードのクラスを特定するための「ノードとそれが属するクラスの対応」の 2 つが必要である．そこで，「ノードとそれが属するクラスの対応」をファイル 5 に書き出し，さらに，「クラスを始点とし，（クラス未特定の）ノードを終点とするエッジ」をファイル 6 に書き出す（10，11 行目）．なお，ファイル 6 は「終点（クラス未特定のノード）」「クラスから終点に向かうエッジのラベル」「始点（クラス）」の順で各行(O(sort(|E|)) = O

ラスを作成し割り当てたときの効用値を計算し，効用値が最も

|E|
|E|
log2
B
B

)

である [8]．
（ 1 ） 前処理

2 つ の エッジ の ファイ ル を 外 部 ソ ー ト す る I/O コ ス ト:O(sort(|E|))（ 2 ） クラス抽出（ a ） 2 つのエッジのファイルの読み込み: O(|E|/B)（ b ） ノ ー ド と ク ラ ス の 対 応 を ファイ ル に 書 き 出 し:O(|V |/B)（ c ） クラス未特定のエッジの書き出し: O(|E|/B)（ d ） 書き出したエッジファイルのソート: O(sort(|E|))（ 3 ） エッジ抽出

Algorithm 2 エッジ抽出v2

p

1: ファイル 6 を外部ソートする．得られたファイルをファイル 7 と

v8
b

する
2: tmp ← NIL

v1

4:

ファイル 7 を 1 行読み込む．その行を v, l, v̄i とする

5:

if v が葉ノード then

7:
8:
9:
10:

v4

b

3: while ファイル 7 が EOF でない do

6:

c

m

v5
a

q
c

else if v = tmp then

a

v3

l

エッジ v̄i → NIL を張る

d

v9

d

l

エッジ v̄i → v̄j を張る

else

v6

v7

while ファイル 5 が EOF でない do

11:

ファイル 5 を 1 行読み込む．その行を tmp, v̄j とする

12:

if v = tmp then

図 5: 入力グラフの例
v1 p v2

v2 p v 1

v2 b v3

v3 b v 2

v3 q v1

v1 q v3

v3 a v4v 4 a v3

v3 c ”v6 ””v6 ” c v3v3 d ”v7 ””v7 ” d v3v4 m v2

v2 m v 4

v4 b v5

v5 b v 4（ a ） 2 つのエッジのファイルの読み込み: O(|E|/B)

v5 a v4v 4 a v5

（ b ） 1 で書き出した，クラス未特定のエッジファイルの読

v5 c ”v8 ””v8 ” c v5

み込み: O(|E|/B)

v5 d ”v9 ””v9 ” d v5

（ c ） ノードとクラスの対応ファイルの読み込み: O(|V |/B)(a) 入力グラフデータ（ファイ(b) 第 1 列と第 3 列を入れ換え（2）と（3）を合わせて，本処理での I/O コストは次のよう

ル 1）たもの（ファイル 2）

break

13:
14:

end if15:

end while

16:
17:

l

エッジ v̄i → v̄j を張る

end if

18: end while

になる．
(
)
(
)
|E|
|V |
|V |
O
+
+ sort(|E|) = O+ sort(|E|)
B
B
B

3. 4 アルゴリズムの動作例

図 6: ファイル 1 とファイル 2

的にファイル 5，6（図 8a，8b）を得る．
最後に，Algorithm 2 を用いてエッジ抽出を行う．まず，ファ

本節では，図 5 のグラフを用いてアルゴリズムの動作例を示

イル 6 を外部ソートし，ファイル 7（図 8c）を得る．ファイ

す．このグラフに対応するファイルをファイル 1 とし，図 6a にル 7 を 1 行読み込み，v = ”v6 ”, l = c, v̄i = v̄3 を得る．この示す．以下，葉ノードは ” で囲み表記する．

エッジはクラスから葉ノードへ向かうエッジであるため，空のまず，ファイル 1 を入力として前処理を行う．前処理では，クラス（NIL）へ向かうエッジとしてエッジを張る．エッジ情

第 1 列と第 3 列を入れ換え，ファイル 2（図 6b）を作成する．

報は v̄3 c NIL と書き出す．続いてファイル 7 を 1 行読み込み，次に，ファイル 1 とファイル 2 をそれぞれ外部ソートし，ファv = ”v6 ” を得る．再び葉ノードなので，先ほどと同様に処理を

イル 3，4（図 7）を得る．

行う．ファイル 7 を読み進めていくと，v = v1 , l = q, v̄i = v̄3

続いて，Algorithm 1 を用いてクラス抽出を行う．ファイルを得る．葉ノード以外のノードなので，そのノードのクラスを

3，4 を 1 行読み込み，v = v1 ，u = ”v6 ” を得る．しかし，”v6 ”

ファイル 5 を読み込んで特定する．ファイル 5 の 1 行目を読みは葉ノードで，クラス抽出対象外であるため，クラス抽出対象

込むことで，v1 は v̄1 に属すると特定できたので，クラス間にノードが現れるまでファイル 4 を読み込み，v1 を u とする．こエッジ v̄3 → v̄1 を張る．これをファイル 7 の終端まで繰り返

こで，v と u を比較すると，v = u = v1 なので，この v1 に接し，エッジ抽出を終了する．抽出されたスキーマを図 9 に，ス

続する出力エッジのラベル p をまずファイル 3 から読み込み，

キーマのエッジを図 10 に示す．

次に入力エッジのラベル q をファイル 4 から読み込む．接続するエッジのラベルがすべて得られたので，クラス抽出を行う．

q

4. 評 価 実 験

既存のクラスはないため，新規クラス v̄1 を作り，v1 を v̄1 に割

本章では（1）入出力エッジの区別の有無から抽出されるス

り当てる．ここで，ファイル 5 にノードとそれが属するクラス

キーマを比較，（2）データサイズを変化させたときのアルゴリの対応 v1 v̄1 を書き出し，ファイル 6 にこのクラス v̄1 から出ズムの処理時間，（3）アルゴリズムの主記憶使用量の 3 点から力するエッジの情報 v2 p v̄1 を書き出す．次のノード以降も同提案アルゴリズムを評価する．

様に，クラス抽出と情報の書き出しを続ける．これを両ファイ

4. 1 評価用データ

ルの終端に達するまで繰り返し，クラス抽出を終了する．最終

評価実験で用いるグラフデータの作成には SP2 Bench [9] をv1 p v2

”v6 ” c v3v̄3 c NILv2 b v3”v7 ” d v3v̄3 d NILv3 a v4”v8 ” c v5v̄3 q v̄1

v3 c ”v6 ””v9 ” d v5v̄3 a v̄2

v3 d ”v7 ”

v1 q v3v̄2 m v̄2

v3 q v1

v2 m v 4v̄2 b v̄3

v4 b v5

v2 p v 1v̄1 p v̄2

v4 m v2

v3 b v 2

図 10: スキーマのエッジファイル

v5 a v4v 4 a v3

v5 c ”v8 ”

v 4 a v5

v5 d ”v9 ”

v5 b v 4(a) ファイル 1 をソートした結(b) ファイル 2 をソートした結果得られたファイル（ファイル

果得られたファイル（ファイル3）4）

図 7: ファイル 3 とファイル 4

表 1: SP2 Bench で作成されたグラフデータ
サイズ（MB）

ノード数

1

10.5

61,107

エッジ数

100,0732

108.6

593,379

1,000,009

3

1,105.2

5,582,764

10,000,457

4

5,511.5 27,452,918

50,000,869

5

10,946.1 55,182,878 100,000,380

v2 p v̄1

v1 v̄1v2 v̄2v3 v̄3v4 v̄2v5 v̄3v3 b v̄2”v6 ” c v̄3v4 a v̄3”v7 ” d v̄3”v6 ” c v̄3”v8 ” c v̄3”v7 ” d v̄3”v9 ” d v̄3v1 q v̄3

v1 q v̄3

v5 b v̄2

v2 m v̄2

ノードである．提案アルゴリズムでは，文字列リテラルノード

v2 m v̄2

v2 p v̄1

を葉ノードとみなし，クラス抽出の対象となるのは一般のノーつけて表される．例えば，人物クラスは foaf:が先頭に付加され，foaf:Person と表される．文字列リテラルノードは ” で囲み表される．
クラス抽出の対象となるノードは，葉ノードを除くすべての

v4 a v̄3

v3 b v̄2

ド，匿名ノード，RDF クラスを表すノードとする．また，各(a) ノードとそれが”v8 ” c v̄3v4 a v̄3

ノードが判別できるように，意味のある文字列のアルファベッ

属するクラスの対応”v9 ” d v̄3v4 a v̄3

トに付随する<，>，_:，foaf:などもノード名の一部とする．

v5 b v̄2

すなわち，<nodename>，_:personname，foaf:Person などをし，クラス未特定の(c) ファイル 6 をソー

ノード名とする．このため，ソートした際には一般のノード，

ノードを終点とする

トした結果得られた匿名ノード，RDF クラスを表すノードの順に並ぶ．

エッジのリスト（ファファイル（ファイル 7）のリスト（ファイル(b) クラスを始点と

5）

イル 6）

実験で使用するグラフデータは，約 10MB から約 10GB ま
での 5 つのサイズのグラフデータである（表 1）．ノード数は

図 8: ファイル 5，ファイル 6，ファイル 7

葉ノードを含むすべてのノード数である．

4. 2 評価実験の詳細
mc

OS: Linux CentOS 7（64bit）

b
v̄1

p

v̄2
q

a

評価実験を行った環境は以下の通りである．

CPU: Intel Xeon E5-2623 v3 3.0GHz

v̄3

主記憶:
d

使用言語:

16GB
Ruby 2.3.0

以下，得られた結果について述べる．
図 9: 図 5 から抽出したスキーマ

4. 2. 1 評価実験 1: 抽出されたスキーマの比較[3] の効用値の定義をそのまま用いた場合，入出力エッジを用いる．これは，DBLP のデータ構造に沿ったスキーマに基づ

区別せずにクラス抽出を行う．これに対して本研究での効用

いて，任意のサイズのラベル付き有向グラフ（Notation3 形式）

値の定義を用いる場合は，入力エッジと出力エッジを区別してを作成するベンチマークソフトである．作成されるファイルのクラス抽出を行う．出力エッジがノードの特徴を決める傾向が各行は「始点」「端点を結ぶエッジのラベル」「終点」で構成さあるため，効用値計算においては，出力に重きを置くようにれる．始点および終点に当たるノードは，一般のノード，匿名

α = 0.2，β = 0.8 とした．

ノード，RDF クラス，文字列リテラルである．一般のノード

5 つのグラフデータ（表 1）に対して前述の 2 通りのスキーは <>で囲まれており，匿名ノードは _:が先頭に付加される．

マ抽出を行った結果を表 2 に示す．まず，スキーマのサイズに

そして，RDF クラス（これは，スキーマのクラスとは別物でついては，どちらの手法もクラス数とクラス間のエッジ数は元ある）に当たるノードは，その種類に応じて名前空間接頭辞をのグラフデータと比べて大幅に減少した． [3] の効用値の定義

表 2: 抽出されたスキーマ(a) 入出力エッジを区別しない

typereferences
1(b) 入出力エッジを区別する

references
2

rdf:_1

クラス数 エッジ数

1

4

142

1

9

181

2

4

188

2

8

197

3

4

220

3

8

205

4

4

244

4

9

243

5

4

Unknown
Document

クラス数 エッジ数

254

5

8

type

rdf:_1
type

Proceeding1
partOfissued#tle

editortype

Inproceeding1

#tle

pages

Book1

224

Smith

Ar#cle2creatortype

name
Unknown
Document

rdf:_1

references

Jones

name

partOfissuedcreator

Smith

type

Incollec#onreferences
2
rdf:_1

Procee
ding1

#tle

name

Jones

type

rdf:_2

editorcreatorreferences
1

Persontype
creator#tle

Proceed
ings

Bag

type

Inproceeding1

#tle

pages

Journal1

journal #tle
Ar#cle1

Book1

issued #tle

Inproceedingsisbn

type

Journal

type

#tle

journal Journal1#tle
issuedProceedings
Inproceedings

WWW

sc

sc sc
sc

DocumentBook

sc

Ar#clesc
Journal

sc

sc

PhD
ThesisMasters
Thesis

Person

type

sc

type

図 12: 入出力エッジを区別した場合

WWW

sc
sc
sc

表 3: 処理時間の内訳
sc

sc
sc
sc

Book

前処理（s） クラス抽出（s）

Document

Ar#cletype

Ar#cle
1

type

name
sc

sc

type

Incollec#on

Bag

references

PhD
ThesisMasters
Thesis

エッジ抽出（s）

合計（s）

1

1.53

7.16

0.86

9.55

2

6.99

63.80

3.86

74.65

3

62.64

644.42

32.82

739.884

386.523535.44170.814092.775

787.667339.29315.608442.55

図 11: 入出力エッジを区別しない場合

10,0009,000をそのまま用いた場合，抽出されたスキーマのクラス数は 4 で8,000あり，データサイズを変えてもクラス数に変化はなかった．本7,000

研究での効用値を用いた場合は，クラス数が 8 のものと 9 のものが抽出された．
どのようにクラス抽出されたかについて詳しく見る
た め に ，図 11， 12 に 元 の デ ー タ [9] の 一 部 と 抽 出 さ れた ス キ ー マ の 比 較 を 示 し た ． [3] の 効 用 値 の 定 義 を そ の
ま ま 用 い た 場 合 ，_:references の ご く 一 部 と ，ノ ー ド

時
間
︵
s
︶

6,000
5,000
4,000
3,000
2,000
1,000
0

<http://localhost/misc/UnknownDocument>が同じクラスと

0

50,000,000
100,000,000
グラフのサイズ（エッジ数）

なり，_:Aaarti_Arvelo といった人名を表すノードは 1 つの図 13: 処理時間の合計

クラスになった．Article，Inproceeding，Journal が同じクラスに属しており，bench，foaf，rdf という接頭辞の付く，

RDF クラスを表すノードは同じクラスにまとまった．しかし，処理時間の内訳については表 3 に示し，処理時間の合計のグラ

Article や_:references が同じクラスとなってしまっている．

フを図 13 に示す．この結果から，処理時間はほぼ線形である

本研究での効用値を用いた場合は入出力エッジを区別したことにより，より細かくクラスが抽出された．具体的には，RDF

ことがわかる．

4. 2. 3 評価実験 3: アルゴリズムの主記憶使用量

クラスを表すノードがまとまり，さらに foaf:Document のみ

主記憶サイズを超えるデータで処理できるかを確認するたで 1 クラスとなった．Article のみのクラスや，Proceeding

め，実行中の主記憶使用量を計測した．5 つのファイルのうちと Book がまとまったクラスができた．9 クラスに分かれたもので最大のもの（約 10GB）に対して前処理，クラス抽出，エッは，Journal のみが 1 つのクラスとなったり，_:references

ジ抽出を実行中における主記憶使用量を計測した．sort コマン

がさらに分かれたりするなど，サイズによって細かい部分に多ドを実行する際「-S」オプションをつけ，sort の主記憶使用量

少の違いが見られた．

を 1GB に制限した．

4. 2. 2 評価実験 2: アルゴリズムの処理時間

まず，前処理においては外部ソートの間，オプションで主記用意した 5 つのグラフデータ（表 1）を対象に前処理，クラス

憶使用量を 1GB に制限しているため，使用量が最大 1.1GB ま抽出，エッジ抽出にかかる処理時間を計測した．前処理とエッで上昇した．この値が前処理中の最大の使用量であった．次に，

ジ抽出での外部ソートには，UNIX の sort コマンドを用いた．

クラス抽出中の主記憶使用量を計測した．得られた結果を図 14

ラス間にエッジを張るエッジ抽出の 3 段階からなる．

2,000
1,800

評価実験を行い，（1）入出力エッジの区別の有無から抽出さ1,600

れるスキーマを比較，（2）データサイズを変化させたときのア

主記 1,400
憶 1,200
使
用 1,000
量
︵ 800
M
B 600
︶
400

ルゴリズムの処理時間，（3）アルゴリズムの主記憶使用量の 3点から提案アルゴリズムを評価した．その結果，先行研究 [3] では分けられなかったノードをクラス分けすることができ，抽出に要する時間はほぼ線形であった．そして，主記憶使用量は最大で入力データサイズの約 16%であるという結果が得られた．

200
0

0

1,000

2,000

3,000 4,000 5,000
経過時間（s）

6,000

7,000

8,000

今後の課題として，より主記憶使用量を抑える手法を考案することが挙げられる．なお，RDF のクラスを表すノードのよ
うに，多くのノードから参照されるノードのみクラス抽出の計

図 14: クラス抽出中の主記憶使用量の推移

算を行わずに別個のクラスとしてまとめることで，主記憶使用量の増大を抑えることができると考えられる．また，提案手法

1,200

ではグラフデータに変更があった場合，スキーマを作り直さな

主 1,000
記
憶 800
使
用 600
量
︵
M 400
B
︶ 200
0

ければならないため，スキーマを更新する手法を開発することも今後の課題となる．

文

0

50

100

150
200
250
経過時間（s）

300

350

図 15: エッジ抽出中の主記憶使用量の推移に示す．実行開始から 7225 秒まで主記憶使用量は約 150MBで推移し，そこから最大 1,722MB まで上昇した．つまり，入力データサイズ（10,946.1MB）に対して，約 16%の主記憶使用量でクラス抽出が完了している．最後に，エッジ抽出中の結果のグラフを図 15 に示す．前処理と同様に，外部ソートの間はオプションで主記憶使用量を 1GB に制限しているため，最大約 1.1GB まで上昇し，その後のエッジを張る処理の間は約9MB で推移した．
クラス抽出の終盤で主記憶使用量が増えた理由は，入力エッジを非常に多くもつ「RDF クラス」を表すノードが最後に処理され，このとき多くの情報が主記憶に格納されたためである．クラス抽出はアルファベット順に行われるため，最初に一般ノード，次に匿名ノード，最後に「RDF クラス」を表すノードが処理される．この結果から，莫大な数のエッジをもつノードが主記憶使用量の増加につながることがわかった．この問題への対処は今後の課題である．

5. む す び
本研究では，大規模グラフデータに対応したスキーマ抽出手法を提案した．具体的には，増分クラスタリング法を用いた作成法である先行研究 [3] の効用値の定義を拡張し，アルゴリズ
ム全体を外部記憶アルゴリズムとした．提案するスキーマ抽出
手法は，（1）ノードに接続するエッジをシーケンシャルに得るために必要なファイルを作成する前処理，（2）ノードが属するクラスを逐次的に効用値を計算して求めるクラス抽出，（3）ク

献[1] R. Goldman and J. Widom, “Dataguides: Enabling
query formulation and optimization in semistructured
databases,” Technical Report 1997-50, Stanford InfoLab,
1997. http://ilpubs.stanford.edu:8090/264/[2] R. Goldman and J. Widom, “Approximate Dataguides,”Proceedings of the Workshop on Query Processing for
Semistructured Data and Non-Standard Data Formats,vol.97, pp.436–445, 1999.
[3] Q.Y. Wang，J.X. Yu, and K.-F. Wong, “Approximate graphschema extraction for semi-structured data,” Advances in
Database Technology―EDBT 2000, pp.302–316, Springer,
2000.
[4] S. Navlakha, R. Rastogi, and N. Shrivastava, “Graph summarization with bounded error,” Proceedings of the 2008
ACM SIGMOD international conference on Management of
dataACM, pp.419–432 2008.
[5] Z. Zhang，J.X. Yu，L. Qin，L. Chang, and X. Lin, “I/O eﬃcient: Computing sccs in massive graphs,” The VLDB Journal―The International Journal on Very Large Data Bases,
vol.24, no.2, pp.245–270, 2015.
[6] Z. Zhang, J.X. Yu, L. Qin, Q. Zhu, and X. Zhou, “I/O cost
minimization: reachability queries processing over massivegraphs,” Proceedings of the 15th International Conference
on Extending Database TechnologyACM, pp.468–479 2012.
[7] X. Hu, Y. Tao, and C.-W. Chung, “Massive graph triangulation,” Proceedings of the 2013 ACM SIGMOD international
conference on Management of dataACM, pp.325–336 2013.
[8] N. Sitchinava, “Memory hierarchies,” http://algo2.iti.
kit.edu/download/mem_hierarchy_01_unedited.pdf. Accessed: 2015-12-14.
[9] M. Schmidt, T. Hornung, G. Lausen, and C. Pinkel,“SP2 Bench: a SPARQL Performance Benchmark,” Data
Engineering, 2009. ICDE’09. IEEE 25th International Conference onIEEE, pp.222–233 2009.