Mercurial > hg > Papers > 2012 > JavaKuche
view index.html @ 4:125ab02ad634 draft
add some pic
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 08 Sep 2012 07:56:38 +0900 |
| parents | 13b3a33da179 |
| children | 975d3790ca03 |
line wrap: on
line source
<!DOCTYPE html> <html> <head> <style type="text/css"> .center { margin-left: auto; margin-right: auto; text-align: center; } </style> <title>Presentation</title> <meta charset='utf-8'> <script src='./slides.js'></script> </head> <body style='display: none'> <section class='slides layout-regular template-default'> <article> <h1>GraphDB 入門<br>TinkerPop の使い方</h1> <p>Shoshi Tamaki<br>Nobuyasu Oshiro<br>8 Sep 2012</p> </article> <!-- <article> <h3>TinkerPop</h3> <br/> <br/> <br/> <br/> <img class="centered" height="300px" src="./images/tinkerpop_with_name.png"/> </article> --> <article> <h3>もくじ</h3> <ul> <li>ストライクウィッチーズで，GraphDB / TinkerPop 入門</li> <li>TinkerPop を利用した GraphDB 上の PageRank の計算</li> </ul> </article> <article> <h3>GraphDB とは？</h3> <p>グラフ構造を保存するためのデータベース．</p> <p>グラフ構造とは，たとえばこんなもの</p> <br/> <img src="./images/de2bf86e.jpeg" class="centered" height="470px"/> </article> <article> <h3>GraphDB とは？</h3> <p>このような構造をしたグラフは<span style="color: red">Property Graph</span>と呼ばれる．</p> <p>Property Graph はこんな特徴がある．</p> <br/> <img src="./images/propertygraph_sw.png" height="470px" class="centered"/> </article> <article> <h3>Property Graph</h3> <small> <p><span color="red">関係・人物・名前・特徴</span>は<span color="red">辺・頂点・ラベル・プロパティ</span>と呼ばれる．</p> <ul> <li>辺 ( 関係 ) が方向を持つ</li> <li>頂点 ( 人物 ) と辺 ( 関係 ) はラベル ( 名前 ) を持つ</li> <li><span style="color: red">頂点と辺は Key / Value のマップ ( 特徴 ) を持っている．</span></li> </ul> </small> <img src="./images/propertygraph_sw2.png" height="400px" class="centered"/> </article> <article> <h3>GraphDB とは？</h3> <p>複数存在する GraphDB は，主に<span color="red"> Property Graph </span>を格納する．</p> <p>GraphDB は，保存された Graph の辺を渡り歩き，目的のデータを取得するようなデータベースである．</p> <img src="./images/traverse_sw.png" class="centered"/> </article> <article> <h3>GraphDB 入門</h3> <p>ここまでに，GraphDB とそのデータ構造である，Property Graph とは何か説明してきた．</p> <p>今日は，この<span style="color: red">ストライクウィッチーズの相関図</span>を GraphDB に叩きこみ <span style="color:red">TinkerPop</span> を使って解析する．</p> <br/> <img src="./images/today-demo.png" class="centered"/> </article> <article> <h3>TinkerPop</h3> <p>TinkerPop は複数存在する GraphDB を統一した手法で利用出来るようにする，ことを目的としたプロジェクトの集合である．</p> <p>GraphDB を操作する様々なツールも開発している．</p> <br/> <br/> <img height="300px" src="./images/tinkerpop_with_name.png" class="centered"/> </article> <article> <h3>TinkerPop</h3> <p>本日は，Blueprints , Pipes , Gremlin , Rexster を利用する．</p> <p><span style="color:red">Frames</span> と <span style="color:red">Furnace</span> に関しては利用しないので触れない．</p> <br/> <br/> <img height="300px" src="./images/today-used.png" class="centered"/> </article> <article> <h3>Blueprints</h3> <p>Blueprints は，Property Graph Model のための interface , implementation , outplementations(造語？) を提供する．</p> <p>GraphDB の世界の JDBC の立場を目指している．</p><br/> <small> Blueprints を実装している GraphDB の一例 <ul> <li>Neo4j<li> <li>OrientDB</li> <li>MongoDB</li> <li>etc...</li> </ul> </small> <img src="./images/blueprints-logo.png" height="100px"/> </article> <article> <h3>Pipes</h3> <p>Pipes は，Graph を処理するためのフレームワーク．複数の処理を Pipe として定義する．その Pipe をつなげることにより，Graph を走査し目的のデータを取得する．</p> <p>Gremlin は Pipe を利用して Graph を Traverse する．</p> <small> <pre>Graph g = ... GremlinPipeline pipe = new GremlinPipeline(); pipe.start(g.getVertex(1)).out("knows").property("name"); pipe.setStarts(new SingleIterator>Vertex<(graph.getVertex(1))); for(Object name : pipe){ System.out.println((String)name); }</pre> </small> <img src="./images/pipes-logo.png" /> </article> <article> <h3>Gremlin</h3> <p>Graph を走査するための言語．GraphDB に対して Query を発行することが出来る．Shell の様なプロンプトも利用することが可能である．</p> <pre>gremlin> // lets traverse to marko's 30+ year old friends' created projects gremlin> v.out('knows').filter{it.age > 30}.out('created').name ==>ripple ==>lop</pre> <br/> <img src="./images/gremlin-logo.png"/> </article> <!-- <article> <h3>Rexster</h3> <p>Rextster は，Blueprints を対応した GraphDB に対して HTTP による API を提供するサーバーである．</p> <p>HTTP 経由でデータの取得を行うことが出来るほか．Graph の編集を付属の WebApplication で行うことが出来る</p> <small> <pre>http://localhost:8182/graphs/tinkergraph/vertices/1 { "version":"*.*", "results": { "_type":"vertex", "_id":"1", "name":"marko", "age":29 },"queryTime":0.12351 }</pre> </small> <img src="./images/rexster-logo.png"/> </article> --> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <br/> <ol> <li>Blueprints で TinkerGraph にストライクウィッチーズの相関図を入力する．</li> <li>Gremlin を使って，TinkerGraph を読み込み，</li> <ul> <li>Java から Gremlin を使って解析してみる．</li> <li>Gremlin のコンソールから解析してみる．</li> </ul> </ol> <br/> <p>まずは，TinkerGraph にストライクウィッチーズの相関図を入力する．</p> </article> <!-- <article> <h3>Rexster + TinkerGraph で GraphDB を用意する．</h3> <p>Rexster の downloads より <span style="color:red">rexster-server-2.1.0.zip</span> をダウンロードし解凍．</p> <p><a href="https://github.com/tinkerpop/rexster/downloads">https://github.com/tinkerpop/rexster/downloads</a></p> <pre>$ cd rexster-server-2.1.0/bin $ ./rexster.sh --start</pre> <p>Rexster はデフォルトで TinkerGraph が有効になるのでそのまま起動するだけで良い．</p> <p>これで，HTTP経由で TinkerGraph にアクセスできるようになり，GraphDB を用意できた．</p> </article> --> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p>Blueprints は，GraphDB へのインターフェイスを提供する．TinkerGraph は Blueprints を用いて利用できる．</p> <p>相関図の Graph を作るためには，<span style="color:red">Graph</span> を作成し<span style="color:red">人物（頂点）</span>と<span style="color:red">関係（辺）</span>，<span style="color:red">特徴</span>を作る必要がある．</p> <small> <pre>// 相関図（Graph） の作成 Graph g = new TinkerGraph();</pre> <pre>// 人物（頂点）の作成 Vertex character = g.addVertex(ID);</pre> <pre>// 関係（辺）の作成 Edge relation = g.addEdge(ID,From,To,Label);</pre> <pre>// 特徴（プロパティ）の作成 , 頂点・辺ともに同様のメソッド character.setProperty(PropertyName,PropertyValue);</pre> </small> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p>画像を見ながらコードに書き起こすと・・・</p> <small> <pre>Graph g = new TinkerGraph("./strikewitches"); // データの保存先 Vertex strikeWitches = g.addVertex("StrikeWitches"); Vertex yoshika = g.addVertex("yoshika"); yoshika.setProperty(propName,"Yoshika Miyafuji"); yoshika.setProperty(propRank,"Sergeant"); yoshika.setProperty(propAge,14); yoshika.setProperty(propCV,"Misato Fukuen"); 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,"仲良し新人コンビ");</pre> </small> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p>Blueprints を用いて TinkerGraph に相関図を書き込むことが出来た．</p> <p>今回は，Graph 探索のサンプルのため"StrikeWitches"というキャラクター全員が所属する頂点を追加してある．</p> <br/> <ol> <li>Blueprints で TinkerGraph にストライクウィッチーズの相関図を入力する．</li> <span style="color:red"> <li>Gremlin を使って，TinkerGraph を読み込み，</li> <ul> <li>Java から Gremlin を使って解析してみる．</li> <li>Gremlin のコンソールから解析してみる．</li> </ul> </span> </ol> <br/> <p>では，Gremlin を利用して相関図を解析してみる．</p> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p>Gremlin のセットアップ</p> <ul> <li>github tinkerpop / gremlin > Wiki の downloads から <span style="color:red">gremlin-groovy-2.1.0.zip</span>を利用する．</span></li> <li>解凍して展開する．</li> <li>bin/gremlin.sh を実行</li> </ul> <pre>shoshi@collett% ./gremlin.sh [~/Downloads/gremlin-groovy-2.1.0/bin] Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8 \,,,/ (o o) -----oOOo-(_)-oOOo----- gremlin></pre> <p>こんなの表示される．</p> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p>Gremlin に相関図を食べさせて，解析開始．</p> <pre>gremlin> g = new TinkerGraph("path_to_graph"); ==>tinkergraph[vertices:12 edges:32 directory:path_to_graph] gremlin> </pre> <p>頂点の一覧を取得してみる．</p> <pre>gremlin> g.V ==>v[mio] ... ==>v[minna] ==>v[lynett] ... ==>v[gertrud] ==>v[francesca]</pre> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p><span style="color:red">宮藤芳佳</span>の<span style="color:red">年齢</span>を取得．</p> <pre>gremlin> g.v("yoshika").age ==>14</pre> <p><span style="color:red">宮藤芳佳</span>を<span style="color:red">指導</span>しているのは誰？</p> <pre>gremlin> g.v("yoshika").in("指導").name ==>坂本美緒</pre> <p><small><span style="color:red">宮藤芳佳</span>のことを<span style="color:red">きっー！なんなんですのアナタは！？</span>と思っている人が<span style="color:red">勤務態度に不満</span>を持っている人たち</small></p> <pre>gremlin> g.v("yoshika").in("きっー！なんなんですのアナタは！？") .out("勤務態度に不満").name ==>シャーロット・E・イエーガー ==>フランチェスカ・ルッキーニ</pre> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p><span style="color:red">16歳以下</span>の<span style="color:red">ウィッチ一覧</span></p> <pre>gremlin> g.v("StrikeWitches").out.filter{it.age < 16}.name ==>宮藤芳佳 ==>エイラ・イルマタル・ユーティライネン ==>サーニャ・V・リトヴャク ==>リネット・ビショップ ==>ペリーヌ・クロステルマン ==>フランチェスカ・ルッキーニ</pre> <p>これを Java のプログラムからもやってみる．</p> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p>Gremlin を Java から使うためには，Maven を利用するのが簡単である．</p> <p>Maven はプロジェクト管理ツールであり，他のプロジェクトのライブラリを簡単に取り込むことができる．</p> <p>pom.xml に Gremlin を取り込むように記述する．</p> <pre><dependency> <groupId>com.tinkerpop.gremlin</groupId> <artifactId>gremlin-java</artifactId> <version>2.1.0</version> </dependency></pre> <p>"Using Gremlin through Java" より tinkerpop / gremlin wiki</p> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p>TinkerGraph で作った，相関図を読み込む</p> <pre>Graph g = new TinkerGraph("path_to_graph");</pre> <p>GremlinPipeline の作成</p> <pre>GremlinPipeline pipe = new GremlinPipeline(); pipe.start(g.getVertex("yoshika"))....</pre> <p>Gremlin は Graph に対して、ある処理をする Pipe をつなげることにより，複雑な探索を可能にする．Gremlin コンソールではあまり見えないが，Java では Pipes を利用しているのが確認できる．</p> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p><span style="color:red">宮藤芳佳</span>を<span style="color:red">指導</span>しているのは誰？</p> <pre>pipe.start(g.getVertex("yoshika")).in("指導").property("name"); for(Object name : pipe){ System.out.println("name") }</pre> <p><small><span style="color:red">宮藤芳佳</span>のことを<span style="color:red">きっー！なんなんですのアナタは！？</span>と思っている人が<span style="color:red">勤務態度に不満</span>を持っている人たちの年齢</small></p> <pre>pipe.start(g.getVertex("yoshika")).in("きっー！なんなんですのアナタは！？") .out("勤務態度に不満").property("age"); for(Object age : pipe){ System.out.println("age"); }</pre> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p><span style="color:red">15歳以上</span>の<span style="color:red">ウィッチーズの名前</span></p> <pre>pipe.start(g.getVertex("StrikeWitches")).out("member") .filter(new PipeFunction<Integer,Boolean>(){ public Boolean compute(Integer _argument){ return _argument >= 15; } }).name; for(Object name : pipe){ System.out.println(name); }</pre> <p>書き方としては，Gremlin コンソールでのほうが簡潔．</p> <pre>gremlin> g.v("StrikeWitches").out.filter{it.age > 15}.name</pre> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p>Gremlin コンソールでの書き方を Java で利用することができる．</p> <pre>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); }</pre> <p>こっちのほうが簡単である．</p> <p>このようにして，TinkerPop を使って，ストライクウィッチーズの相関図を解析してみることができた．</p> </article> <article> <h3>まとめ</h3> <ul> <li>GraphDB は，保存された Graph の辺を渡り歩き，目的のデータを取得するようなデータベースである</li> <li>TinkerPop は複数存在する GraphDB を統一した手法で利用出来るようにする，ことを目的としたプロジェクトの集合である．</li> <li>Blueprints は，Property Graph Model のための interface を提供する．</li> <li>Pipes は，Graph を処理するためのフレームワーク．複数の処理を Pipe として定義する．</li> <li>Gremlin は，Graph を走査するための言語．GraphDB に対して Query を発行することが出来る．</li> </ul> </article> <article> <h3>まとめ</h3> <p>次は，GraphDB の例題として GraphDB を利用した PageRank の計算を TinkerPop を利用して行なって見る．</p> </article> <!-- <article> <h1><font size=10em> TinkerPop による PageRank の実装 </font> </h1> <p> 琉球大学 大城信康 <br> Sep. 08, 2012 </p> </article> --> <article> <h3>Google の PageRank アルゴリズム</h3> <ul> <li>Google の Webページ検索エンジンに使われているアルゴリズム。</li> <li>あるページの『重要度』を示す値で、各ページ毎に持っている。 </li> <li>PageRank が高いほど検索結果の上位に表示される。</li> <li>『多くの良質なページからリンクされているページは、やはり良質なページである』という考えのアルゴリズム<br></li> <li>GraphDB は PageRank の計算に向いている。</li> </ul> </article> <article> <h3>なぜ PageRank なのか</h3> <ul> <li>PageRank は Page と Page のリンクの有無を利用して計算できる。</li> <li>GraphDB は Vertex と Vertex を結ぶ Edge を走査(Traverse)することで、 目的のデータを得るようなデータベースである。</li> <li>また、GraphDB は局所性のあるデータを高速に計算することができる。 </li> <li>PageRank の Page の関係は GraphDB の Vertex と Edge で表すことが出来る。 </li> <li>また、Page の数が増えても局所的な計算ができるため GraphDB は PageRank を求める DB に向いている。</li> </ul> </article> <article> <h3>Page と PageRank の GraphDB による表現</h3> <ul> <li>アンサイクロペディアの各ページを GraphDB で表す。</li> <li>1 Vertex が1つのページを表す。</li> <li>各Vertex は Page Title と PageRank を Property として持つ。</li> <li>リンクは "HAS_LINK" という関係で表される。</li> <li>PageRank は double で初期値は 0.15 , 最大値はページ数*0.15</li> <li>アンサイクロペディアでは URI はページタイトルと同じ。</li> <li>URI に対してユニークな Vertex ID を割り振る。</li> </ul> </article> <article> <h3>TinkerPop による PageRank の計算</h3> <ul> <li>○は Vertex を、→ は Edge を表す。</li> <p class="center"> <img src="./pic/graph.png" style="height:70%;"> </p> <small><p>例：アンサイクロペディア内のページ『琉球大学』のリンクの関係 </p></small> </ul> </article> <article> <h3>PageRank アルゴリズム</h3> <ul> <li>PageRank は次の計算式で求めることができる。</li> <pre> PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))</pre> <li>PR(A) は A というページの PageRank を表す。</li> <li>d は定数で 0.85</li> <li>C(T1) は T1 というページがリンクを張っている数を表す。 </li> <li>T1...Tn は A をリンクしているページなので、C(T1)...C(Tn) は 0 にならない。</li> <li>Google の PageRank はこれを改良したものである。</li> <!-- <li>PageRank はリンクを張ってくるページの PageRank が加算される。 </li> <li>この時加算される PageRank はリンクの数で割られた値となる。</li> --> </ul> </article> <article> <h3>PageRank の取得</h3> <ul> <li>TinkerPop 上で PageRank の値を出すために以下の2つの値が必要</li> <ul> <li>リンク("HasLink")の関係を張ってくる Vertex の取得</li> <li>リンクしてくる Vertex がどれだけリンクを張っているかを取得</li> <small><p>*各ページの情報は XML から取り出し Blueprints を用いて TinkerGraph に書き込み済み。</p></small> <p class="center"> <img src="./pic/page_rank.png" style="height:40%;"> </p> </ul> </ul> </article> <!-- <article> <h3>PageRank </h3> <ul> <li>TinkerPop 上での表現</li> <p class="center"> <img src="./pic/graph2.png" style="height:70%;"> </p> <small><p>PageRankは小数点第三位で四捨五入</p></small> </ul> </article> --> <!-- <article> <h3>アンサイクロペディのページを TinkerGraph で表現</h3> <ol> <li>XML のデータからページとリンクの関係を取り出す。</li> <li>Blueprints を用いて TinkerGraph にページの情報を書き込む。</li> <li></li> </ol> <ul> <li>PageRank の計算に必要な処理を Pipes を使って行う。</li> </ul> </article> --> <article> <h3>Pipes による走査</h3> <ul> <li>あるページへとリンクを張るページ(Vertex)の取得</li> <pre> Graph graph = ... GremlinPipeline pipe = new GremlinPipeline(); pipe.start(graph.getVertex(id)); pipe.in("HasLink"); for (Object inVerObj : pipe) { Vertex inVer = (Vertex)inVerObj; : } </pre> <p class="center"> <img src="./pic/inHasLink.png" style="height:30%;"> </p> </ul> </article> <article> <h3>Pipes による走査</h3> <ul> <li>あるページが張っているリンクの数の取得</li> <pre> Graph graph = ... GremlinPipeline pipe = new GremlinPipeline(); pipe.start(graph.getVertex(id)); pipe.out("HasLink"); long linkNum = pipe.count(); </ul> <p class="center"> <img src="./pic/outHasLink.png" style="height:30%;"> </p> </article> <article> <h3>TinkerPop による PageRank の計算</h3> <ul> <pre> 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); </pre> </ul> </article> <article> <h3>TinkerPop による PageRank の計算</h3> <ul> <li>アンサイクロペディア内で PageRank の高いページ</li> <li>総ページ数: 242014 ページ</li> <table> <tr> <td>ページ名</td> <td>リンク数</td> <td>PageRank</td> </tr> <tr> <td>ユーモア枯渇症</td> <td>7162</td> <td>71.120</td> <!-- <td>2.9387157726301383E-4</td> --> </tr> <tr> <td>日本</td> <td>3537</td> <td>54.584</td> <!-- <td>2.2555002445844352E-4</td> --> </tr> <tr> <td>アンサイクロペディア</td> <td>3887</td> <td>54.164</td> <!-- <td>2.2381320294806578E-4</td> --> </tr> <tr> <td>ウィキペディア </td> <td>2414</td> <td>44.617</td> </tr> <tr> <td>ニンジャスター</td> <td>177</td> <td>36.167</td> </tr> </table> </ul> </article> <article> <h3>PageRank の計算にかかる時間</h3> <ul> <li>PageRank は 10 回程の計算でほぼ収束した。</li> <table> <td> <img src="./pic/pageRank.png" style="height:70%;"> </td> <td> <img src="./pic/computePageRank.png" style="height:70%;"> </td> </table> <li>PageRank の計算は10回行うとして、ページ数に対してかかる時間を測ってみた。</li> </ul> </article> <article> <h3>PageRank の計算にかかる時間</h3> <ul> <li>各ページ数で行う10回計算をそれぞれ10回ずつタイムを測り平均をとった。</li> <table> <tr> <td>ページ数</td> <td>10回の計算にかかった時間(単位:ms)</td> </tr> <tr> <td>100</td> <td>21</td> </tr> <tr> <td>1000</td> <td>67</td> </tr> <tr> <td>10000</td> <td>976</td> </tr> <tr> <td>50000</td> <td>7140</td> </tr> <tr> <td>100000</td> <td>26150</td> </tr> <tr> <td>200000</td> <td>74130</td> </tr> <tr> <td>242014</td> <td>93512</td> </tr> </table> </ul> </article> <article> <h3>PageRank の計算にかかる時間</h3> <ul> <img src="./pic/pageRankCompare.png"> </ul> </article> <article> <h3>今日理解してほしいこと</h3> <ul> <li>今回、TinkerPop を用いてアンサイクロペディアの各ページの PageRank を求めた。</li> <li>各ページと Vertex, リンクの関係を Edge で表すことで各ページ間の関係を TinkerPop 上で表した。 </li> <li>Gremlin を用いて各 Vertex を渡り歩ことで PageRank の計算を行った。</li> </ul> </article> <article> <h3>参考文献・サイト</h3> <ul> <small><li>[1] Google の秘密 - PageRank 徹底解説<br> <a href="http://homepage2.nifty.com/baba_hajime/wais/pagerank.html">http://homepage2.nifty.com/baba_hajime/wais/pagerank.html</a></li></small> <small><li>[2] Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998,<br> <a href="http://www-db.stanford.edu/~backrub/pageranksub.ps">http://www-db.stanford.edu/~backrub/pageranksub.ps</a></li></small> <small><li>[3] The PageRank Algorithm<br> <a href="http://pr.efactory.de/e-pagerank-algorithm.shtml">http://pr.efactory.de/e-pagerank-algorithm.shtml</a></li></small> <small><li>[4] グラフデータベースを用いた PageRank 実装の試み：スケーラブルなグラフ処理系に向けて<br> <a href="http://live-e.naist.jp/sensor_overlay/5/doc/hanai.pdf">http://live-e.naist.jp/sensor_overlay/5/doc/hanai.pdf</a></li></small> <!-- <small><li>Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford Technical Report, 1999,<br> <a href="http://dbpubs.stanford.edu:8090/pub/1999-31">http://dbpubs.stanford.edu:8090/pub/1999-31</a></li> --> </small> </ul> </article> <article> <h3>RDB (SQL文)との比較</h3> <ul> <li>RDB 上で PageRank を計算するとどうなるのか。</li> <li>次のグラフを RDB で表し、 PageRank を求める SQL文を考えてみる。</li> </ul> </article> <article> <h3>RDB (SQL文)との比較</h3> <ul> <p class="center"> <img src="./pic/rdbGraph.png" style="height:70%;"> </p> <small><li>全てのエッジの関係は"HasLink"とする。</li></small> </ul> </article> <article> <h3>RDB (SQL文)との比較</h3> <ul> <li>Table は、Vertex と Edge のプロパティの情報を持つものと、 Edge が伸びている方向を表すものができる。</li> <table style="width:50%;"> <tr> <td>vid</td> <td>pageTitle</td> <td>pageRank</td> </tr> <tr> <td>1</td> <td></td> <td></td> </tr> <tr> <td>2</td> <td></td> <td></td> </tr> <tr> <td>3</td> <td></td> <td></td> </tr> <caption>vid</caption> </table> </ul> </article> <article> <h3>RDB (SQL文)との比較</h3> <ul> <table> <td> <table> <tr> <td>eid</td> <td>relationship</td> </tr> <tr> <td>1</td> <td>HasLink</td> </tr> <tr> <td>2</td> <td>HasLink</td> </tr> <tr> <td>3</td> <td>HasLink</td> </tr> <tr> <td>4</td> <td>HasLink</td> </tr> <tr> <td>5</td> <td>HasLink</td> </tr> <tr> <td>6</td> <td>HasLink</td> </tr> <tr> <td>7</td> <td>HasLink</td> </tr> <tr> <td>8</td> <td>HasLink</td> </tr> <tr> <td>9</td> <td>HasLink</td> </tr> <caption>eid</caption> </table> </td> <td> <table> <tr> <td>eid</td> <td>fromVer</td> <td>toVer</td> </tr> <tr> <td>1</td> <td>8</td> <td>5</td> </tr> <tr> <td>2</td> <td>7</td> <td>5</td> </tr> <tr> <td>3</td> <td>6</td> <td>5</td> </tr> <tr> <td>4</td> <td>1</td> <td>5</td> </tr> <tr> <td>5</td> <td>1</td> <td>4</td> </tr> <tr> <td>6</td> <td>1</td> <td>3</td> </tr> <tr> <td>7</td> <td>1</td> <td>2</td> </tr> <tr> <td>8</td> <td>2</td> <td>2</td> </tr> <tr> <td>9</td> <td>4</td> <td>3</td> </tr> <caption>graph</caption> </table> </td> </table> </ul> </article> <article> <h3>RDB (SQL文)との比較</h3> <ul> <!-- <li>SQL 文で PageRank を求める。</li> --> <li>Vertex 5 に対してリンクを張っている Vertex(SQL) </li> <pre> select vid from vid,eid,graph where eid.relationship='HasLink' and eid.eid=graph.eid and graph.fromVer=vid.vid and graph.toVer=5; </pre> </ul> </article> <article> <h3>RDB (SQL文)との比較</h3> <ul> <li>RDB(SQL文)では GraphDB の走査(Traverse) がしにくい。</li> <li></li> </ul> </article> <!-- <article> <h3>GraphDB の定義</h3> <p><span style="color:red">Property Graph</span> を実装して，その API を提供すれば GraphDB となるわけではない．</p> <p>GraphDB は</p> <br/> <p><span style="color:red">index-free adjacency</span></p> <br/> <p>でなければいけない．</p> <p>これは，GraphDB の実装において，頂点に隣接する頂点を参照する際に，再度 Graph 全体のインデックスを参照してはいけないということである．</p> <p>頂点は隣接する頂点への参照を自身で保持している．</p> </article> <article> <h3>GraphDB の定義</h3> <p>内部の実装がこんな感じだとダメ</p> <p>内部で，頂点に接続されている頂点のデータを取得する際に再度Index-Treeを参照している．</p> <br/> <img class="centered" src="./images/index-dependent-adjacency.png"/> </article> <article> <h3>GraphDB の定義</h3> <p>これはOK</p> <p>頂点が他の頂点への参照を保持する，Index-Tree を参照しない ( index-free )</p> <br/> <img class="centered" src="./images/index-free-adjacency.png"/> </article> <article> <h3>GraphDB の実装</h3> <p>GraphDB の実装にはどんなものがあるの？</p> <table> <tbody> <tr> <th>名前</th> <th>言語</th> <th>特徴</th> </tr> <tr> <td>Neo4j</td> <td>Java</td> <td>ライブラリ・ツールがたくさんある</td> </tr> <tr> <td>OrientDB</td> <td>Java</td> <td>SQL ライクな構文が使える</td> </tr> <tr> <td>sones</td> <td>C#</td> <td>Property Hyper Graph , GQL</td> </tr> <tr> <td>InfiniteGraph</td> <td>C++</td> <td>Distributed Graph Database</td> </tr> </tbody> </table> <br/> <p>沢山の GraphDB 実装がある．それぞれの GraphDB でインターフェイスが異なり，ベンダーロックインな実装になることが多いと言われている．</p> </article> <article> <h3>Frames</h3> <p>Graph をオブジェクトとして気軽に扱えるようにするためのフレームワーク，アノテーションにより，オブジェクトと Graph の関係を定義する．</p> <small> <pre>public interface Person { @Property("name") public String getName(); } public class Frames { public Frames() { FramedGraph<Neo4jGraph> graph = new FramedGraph<Neo4jGraph>(new Neo4jGraph("/tmp/neo4j")); Person person = graph.getVertex(1, Person.class); person.getName(); // equals "marko" } }</pre> </small> <img src="./images/frames-logo.png" height="100px"/> </article> <article> <h3>Furnace</h3> <p>グラフ解析のためのアルゴリズムパッケージ</p> <p>世の中には沢山のグラフ理論に基づくアルゴリズムが考案されているが，しかし多くは Property Graph のものではない，</p> <p>Furnace は Property Graph をそれらのアルゴリズムで利用できるようにする．</p> <p>まだあんまり進んでいないようで・・・</p> <br/> <br/> <img src="./images/furnace-logo.png"/> </article> <article> <h3>TinkerPop を使ってみよう</h3> <p>今日は実際に以下のプロジェクトを利用してみます．</p> <br/> <ul> <li>Blueprints</li> <li>Pipes</li> <li>Gremlin</li> <li>Rexster</li> <li>TinkerGraph</li> </ul> <br/> <p>TinkerGraph は TinkerPop に付属しているインメモリグラフデータベース</p> </article> <article> <h3>TinkerPop を使ってみよう</h3> <br/> <small> <ul> <li>TinkerGraph (In-Memory GraphDB) を Rexster で使ってみる．</li> <li>Rexster の RESTAPI を Blueprints を使ってアクセスしてみよう．</li> <li>作った Graph を Rexster の GodHouse から見てみよう．</li> <li>Gremlin で Rexster に書き込んだ Graph を Traverse してみよう．</li> </ul> <br/> </small> <img height="300px" src="./images/today-demo.png"/> </article> <article> <h3>TinkerPop を使ってみよう</h3> <small> <br/> <p>TinkerGraph (In-Memory GraphDB) を Rexster で使ってみる．</p> <br/> <Ul> <li>Rexster を tinkerpop/rexster wiki からダウンロードして展開する</li> <li>今回利用した Rexster は 2.1.0 を利用．</li> <li>bin/rexster.sh --start</li> <li>これで，localhost:8182 でサーバーが起動する．</li> <li>管理画面 : http://localhost:8182/doghouse/main/graph/tinkergraph</li> </ul> </small> </article> <article> <h3>TinkerPop を使ってみよう</h3> <small> <br/> <p>Rexster の RESTAPI を Blueprints を使ってアクセスしよう</li> <br/> <ul> <li>Blueprints を使ってグラフを書き込んでみる．</li> <li>利用した Blueprints は 2.1.0 を利用</li> <li>Eclipse + m2eclipse を使う．</li> <li>どっかにソースコードをあげます．</li> </ul> </small> </article> <article> <h3>TinkerPop を使ってみよう</h3> <small> <br/> <p>Rexster の RESTAPI を Blueprints を使ってアクセスしよう</li> <br/> <ul> </ul> </small> </article> --> </section> </body> </html>