GraphDB 入門
TinkerPop の使い方

Shoshi Tamaki
Nobuyasu Oshiro
08 Sep 2012

もくじ

GraphDB とは？

Graph構造を保存するためのデータベース．

Graph構造とは，たとえばこんなもの

GraphDB とは？

このような構造をしたGraphはPropertyGraphと呼ばれる．

PropertyGraphとは，

PropertyGraph

関係・人物・名前・特徴はVertex・Edge・Label・Propertyと呼ばれる．

GraphDBとは？

GraphDBは，保存されたGraphのVertex,Edgeを渡り歩き，目的のデータを取得するようなデータベースである．

渡り歩くことをTraverseという．

TinkerPop

TinkerPopはGraphDBを利用するためのツール群である．

Blueprints

Blueprintsは，PropertyGraphのJavaのinterfaceを提供する．

GraphDBの世界のJDBCの立場を目指している．

Gremlin

GraphをTraverseするための言語．Groovyがベースである．GraphDBに対してQueryを発行することが出来る．コンソールも利用できる．

gremlin> graph.v(1).out.name
==>vadas
==>lop
==>josh

GremlinはPipesを利用して，GraphをTraverseする．.out.nameがPipeである．．

Pipes

PipesはGraphを処理するためのフレームワークである．Pipeという処理の単位を複数連結し，複雑なTraverseを実現する．

graph.v(1)はGraphからIDか1のVertexを取得する，.out .name がぞれぞれPipeに値する．

Pipes

この例題の動作は・・・

gremlin> g.v(1).out.name
==>vadas
==>lop
==>josh

ストライクウィッチーズの相関図を解析するには？

1. BlueprintsでTinkerGraphにストライクウィッチーズの相関図を入力する．
2. 作成したTinkerGraphを，
• Gremlinのコンソールから解析してみる．
• JavaからGremlinを使って解析してみる．

まずは，TinkerGraphにストライクウィッチーズの相関図を入力する．

この発表のサンプルコードについて

hg clone https://bitbucket.org/suikwasha/graphdb_javakuche

ビルド方法・解凍したディレクトリに移動して
$ mvn compile

ストライクウィッチーズの相関図を解析するには？

Blueprintsは，GraphDBへのインターフェイスを提供する．TinkerGraphはBlueprintsを用いて利用できる．

// 相関図（Graph）の作成，データを保存するディレクトリを引数に取る
Graph g = new TinkerGraph();

// 人物（Vertex）の作成，設定したいIDを引数に取る
Vertex character = g.addVertex(ID);

// 関係（Edge）の作成，設定したいIDを引数に取る
Edge relation = g.addEdge(ID,From,To,Label);

// 特徴（Property）の作成 , Vertex・Edgeともに同様のメソッド
character.setProperty(PropertyName,PropertyValue);

ストライクウィッチーズの相関図を解析するには？

これを入力します．

ストライクウィッチーズの相関図を解析するには？

画像を見ながらコードに書き起こすと・・・

Graph g = new TinkerGraph("./strikewitches"); // 保存ディレクトリ
Vertex strikeWitches = g.addVertex("StrikeWitches");
Vertex yoshika = g.addVertex("yoshika");
yoshika.setProperty(propName,"宮藤芳佳");
yoshika.setProperty(propRank,"軍曹");
yoshika.setProperty(propAge,14);
yoshika.setProperty(propCV,"福圓美里");
yoshika.setProperty(propUnit,"扶桑皇国海軍遣欧艦隊");
yoshika.setProperty(propPersonality,"明るく前向きで一生懸命");
Vertex lynett = g.addVertex("lynett");
lynett.setProperty(propName,"リネット・ビショップ");
lynett.setProperty(propRank,"軍曹");
lynett.setProperty(propAge, 15);
lynett.setProperty(propCV,"名塚佳織");
lynett.setProperty(propUnit,"ブリタニア空軍");
lynett.setProperty(propPersonality,"家庭的で戦闘は苦手");
g.addEdge(null,yoshika,lynett,"仲良し新人コンビ");
g.addEdge(null,lynett,yoshika,"仲良し新人コンビ");

CreateStrikeWitchesGraph

実際にコードを動作させてTinkerGraphに入力する．

プロジェクトのディレクトリにstrikwitchesが作成される．

ストライクウィッチーズの相関図を解析するには？

Blueprintsを用いてTinkerGraphに相関図を書き込むことが出来た．

今回は，Graph探索のサンプルのため"StrikeWitches"というキャラクター全員が所属する頂点を追加してある．

1. BlueprintsでTinkerGraphにストライクウィッチーズの相関図を入力する．
2. Gremlinを使って，TinkerGraphを読み込み，
• Gremlinのコンソールから解析してみる．
• JavaからGremlinを使って解析してみる．

では，Gremlinを利用して相関図を解析してみる．

ストライクウィッチーズの相関図を解析するには？

Gremlinのセットアップ

• github tinkerpop/gremlin > Wiki のdownloadsからgremlin-groovy-2.1.0.zipを利用する．
• 解凍して展開する．
• bin/gremlin.shを実行

% ./gremlin.sh                                                                                                              [~/Downloads/gremlin-groovy-2.1.0/bin]
         \,,,/
         (o o)
-----oOOo-(_)-oOOo-----
gremlin>

こんなの表示される．

ストライクウィッチーズの相関図を解析するには？

Gremlin に相関図を食べさせて，解析開始．

gremlin> g = new TinkerGraph("path_to_graph");
==>tinkergraph[vertices:12 edges:32 directory:path_to_graph]
gremlin> 

Vertexの一覧を取得してみる．

gremlin> g.V // GraphのVertex一覧
==>v[mio]
...
==>v[minna]
==>v[lynett]
...
==>v[gertrud]
==>v[francesca]

ストライクウィッチーズの相関図を解析するには？

宮藤芳佳の年齢を取得．

gremlin> g.v("yoshika").age
==>14

宮藤芳佳を指導しているのは誰？

gremlin> g.v("yoshika").in("指導").name
==>坂本美緒

宮藤芳佳のことをきっー！なんなんですのアナタは！？と思っている人が勤務態度に不満を持っている人たち

gremlin> g.v("yoshika").in("きっー！なんなんですのアナタは！？")
      .out("勤務態度に不満").name
==>シャーロット・E・イエーガー
==>フランチェスカ・ルッキーニ

ストライクウィッチーズの相関図を解析するには？

宮藤芳佳のことをきっー！なんなんですのアナタは！？と思っている人が勤務態度に不満を持っている人たち

gremlin> g.v("yoshika").in("きっー！なんなんですのアナタは！？")
      .out("勤務態度に不満").name
==>シャーロット・E・イエーガー
==>フランチェスカ・ルッキーニ

ストライクウィッチーズの相関図を解析するには？

16歳以下のウィッチ一覧

gremlin> g.v("StrikeWitches").out.filter{it.age < 16}.name
==>宮藤芳佳
==>エイラ・イルマタル・ユーティライネン
==>サーニャ・V・リトヴャク
==>リネット・ビショップ
==>ペリーヌ・クロステルマン
==>フランチェスカ・ルッキーニ

ストライクウィッチーズの相関図を解析するには？

GremlinをJavaから使うためには，Mavenを利用するのが簡単である．

Mavenはプロジェクト管理ツールであり，他のプロジェクトのライブラリを簡単に取り込むことができる．

pom.xmlにGremlinを取り込むように記述する．

<dependency>
  <groupId>com.tinkerpop.gremlin</groupId>
  <artifactId>gremlin-java</artifactId>
  <version>2.1.0</version>
</dependency>

"Using Gremlin through Java" よりtinkerpop/gremlin wiki

ストライクウィッチーズの相関図を解析するには？

TinkerGraphで作った，相関図を読み込む

Graph g = new TinkerGraph("path_to_graph");

GremlinPipeline の作成

GremlinPipeline<Vertex,String> pipe
 = new GremlinPipeline<Vertex,String>();
pipe.start(g.getVertex("yoshika"))....

GremlinはGraphに対して処理をするPipeをつなげて，複雑な探索を可能にする．Gremlin コンソールでは見えないが，JavaではPipesを利用しているのが確認できる．

ストライクウィッチーズの相関図を解析するには？

宮藤芳佳を指導しているのは誰？

pipe.start(g.getVertex("yoshika")).in("指導").property("name");
for(String name : pipe){
 System.out.println("name")
}

宮藤芳佳のことをきっー！なんなんですのアナタは！？と思っている人が勤務態度に不満を持っている人たちの年齢

pipe.start(g.getVertex("yoshika")).in("きっー！なんなんですのアナタは！？")
 .out("勤務態度に不満").property("age");
for(Integer age : pipe){
 System.out.println(age);
}

ストライクウィッチーズの相関図を解析するには？

15歳以上のウィッチーズの名前

pipe.start(g.getVertex("StrikeWitches")).out("member")
 .filter(new PipeFunction<Vertex,Boolean>(){
  public Boolean compute(Vertex _argument){
   return (Integer)_argument.getProperty("age") >= 15;
  }
 }).name;
for(String name : pipe){
 System.out.println(name);
}

書き方としては，Gremlin コンソールでのほうが簡潔．

gremlin> g.v("StrikeWitches").out.filter{it.age > 15}.name

ストライクウィッチーズの相関図を解析するには？

Gremlin コンソールでの書き方を Java で利用することができる．

Pipe pipe = Gremlin.compile("_().out.filter{it.age > 15}.name");
pipe.setStarts(
 new SingleIterator<Vertex>(g.getVertex("StrikeWitches"));
for(Object name : pipe){
 System.out.println(name);
}

_()はGremlinePipelineに定義されている何もしないPipe

JavaでPipeを直接構築するより，こっちのほうが簡単である．

まとめ

これまでに，ストライクウィッチーズの相関図を利用してGraphDBの概要とTinkerPopの簡単な使い方を見てきた．

この発表で大体のイメージが掴めてもらえれば幸いです．

• GraphDBは，GraphのEdgeをTraverseして，目的のデータを取得するデータベース
• GraphDBは，PropertyGraphを格納する．

• TinkerPopは，GraphDBを利用するためのツールの集合

次に，具体的な利用例としてPageRankのGraphDBでの表現について発表する．

Google の PageRank アルゴリズム

• Google の Webページ検索エンジンに使われているアルゴリズム。
• あるページの『重要度』を示す値で、各ページ毎に持っている。
• PageRank が高いほど検索結果の上位に表示される。
• 『多くの良質なページからリンクされているページは、やはり良質なページである』という考えのアルゴリズム
  
• GraphDB は PageRank の計算に向いている。

Page と PageRank の GraphDB による表現

• アンサイクロペディアの各ページを GraphDB で表す。
• 1 Vertex が1つのページを表す。
• 各Vertex は Page Title と PageRank を Property として持つ。
• リンクは "HAS_LINK" という関係で表される。
• PageRank は double で初期値は 0.15 , 最大値はページ数*0.15
• アンサイクロペディアでは URI はページタイトルと同じ。
• URI に対してユニークな Vertex ID を割り振る。

TinkerPop による PageRank の計算

• ○は Vertex を、→ は Edge を表す。



例：アンサイクロペディア内のページ『琉球大学』のリンクの関係

PageRank アルゴリズム

• PageRank は次の計算式で求めることができる。

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

• PR(A) は A というページの PageRank を表す。
• d は定数で 0.85
• C(T1) は T1 というページがリンクを張っている数を表す。
• T1...Tn は A をリンクしているページなので、C(T1)...C(Tn) は 0 にならない。
• Google の PageRank はこれを改良したものである。

PageRank の取得

• TinkerPop 上で PageRank の値を出すために以下の2つの値が必要
• リンク("HasLink")の関係を張ってくる Vertex の取得
• リンクしてくる Vertex がどれだけリンクを張っているかを取得

*各ページの情報は XML から取り出し Blueprints を用いて TinkerGraph に書き込み済み。

Pipes による走査

• あるページへとリンクを張るページ(Vertex)の取得

Graph graph = ...
GremlinPipeline pipe = new GremlinPipeline();
pipe.start(graph.getVertex(id));
pipe.in("HasLink");
for (Object inVerObj : pipe) {
  Vertex inVer = (Vertex)inVerObj;
  :
}	  

Pipes による走査

• あるページが張っているリンクの数の取得

Graph graph = ...
GremlinPipeline pipe = new GremlinPipeline();
pipe.start(graph.getVertex(id));
pipe.out("HasLink");
long linkNum = pipe.count();
	

TinkerPop による PageRank の計算

final double weight = 0.85;
double sum = 0.0;
double pageRank = 0.0;
Vertex v = graph.getVertex(id);
GremlinPipeline pipe = new GremlinPipeline();
pipe.start(graph.getVertex(id)).in("HasLink");
for (Object inVerObj : pipe) {
  Vertex inVer = (Vertex) inVerObj;
  Object inVerId = inVer.getId();
  GremlinPipeline inPipe = new GremlinPipeline();
  inPipe.start(graph.getVertex(inVerId)).out("HasLink");
  long linkNum = inPipe.count();
  double pr = (Double) inVer.getProperty(PAGE_RANK);
  sum += (double) pr / linkNum;
}
pageRank = (double) 1 - weight + (double) sum * weight;
v.setProperty(PAGE_RANK, pageRank);

TinkerPop による PageRank の計算

• アンサイクロペディア内で PageRank の高いページ
• 総ページ数: 242014 ページ

ページ名	リンク数	PageRank
ユーモア枯渇症	7162	71.120
日本	3537	54.584
アンサイクロペディア	3887	54.164
ウィキペディア	2414	44.617
ニンジャスター	177	36.167

PageRank の計算にかかる時間

• PageRank は 10 回程の計算でほぼ収束した。
• PageRank の計算は10回行うとして、ページ数に対してかかる時間を測ってみた。

PageRank の計算にかかる時間

• 各ページ数で行う10回計算をそれぞれ10回ずつタイムを測り平均をとった。

ページ数	10回の計算にかかった時間(単位:ms)
100	21
1000	67
10000	976
50000	7140
100000	26150
200000	74130
242014	93512

PageRank の計算にかかる時間

今日理解してほしいこと

• 今回、TinkerPop を用いてアンサイクロペディアの各ページの PageRank を求めた。
• 各ページと Vertex, リンクの関係を Edge で表すことで各ページ間の関係を TinkerPop 上で表した。
• Gremlin を用いて各 Vertex を渡り歩ことで PageRank の計算を行った。

参考文献・サイト

• [1] Google の秘密 - PageRank 徹底解説
  http://homepage2.nifty.com/baba_hajime/wais/pagerank.html
• [2] Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998,
  http://www-db.stanford.edu/~backrub/pageranksub.ps
• [3] The PageRank Algorithm
  http://pr.efactory.de/e-pagerank-algorithm.shtml
• [4] グラフデータベースを用いた PageRank 実装の試み：スケーラブルなグラフ処理系に向けて
  http://live-e.naist.jp/sensor_overlay/5/doc/hanai.pdf

なぜ PageRank なのか

• PageRank は Page と Page のリンクの有無を利用して計算できる。
• GraphDB は Vertex と Vertex を結ぶ Edge を走査(Traverse)することで、 目的のデータを得るようなデータベースである。
• また、GraphDB は局所性のあるデータを高速に計算することができる。
• PageRank の Page の関係は GraphDB の Vertex と Edge で表すことが出来る。
• また、Page の数が増えても局所的な計算ができるため GraphDB は PageRank を求める DB に向いている。