Mercurial > hg > Papers > 2012 > JavaKuche
view index.html @ 12:b2605d77692c draft default tip
fix
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 08 Sep 2012 08:46:15 +0900 |
| parents | 39c917cdb30d |
| children |
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>08 Sep 2012</p> </article> <article> <h3>もくじ</h3> <br/> <small> <ul> <li>ストライクウィッチーズで，GraphDB/TinkerPop入門</li> <ul> <li>GraphDBとは</li> <li>PropertyGraphについて</li> <li>TinkerPopとは</li> <li>TinkerPopを使ってストライクウィッチーズの相関図を解析</li> </ul> <li>TinkerPop による PageRank の実装</li> <ul> <li>PageRank アルゴリズム</li> <li>Page と PageRank の GraphDB による表現</li> <li>TinkerPop による PageRank の計算</li> <li>Pipes による走査</li> <li>PageRank の計算にかかる時間</li> </ul> </ul> </small> </article> <article> <h3>GraphDB とは？</h3> <p>Graph構造を保存するためのデータベース．</p> <p>Graph構造とは，たとえばこんなもの</p> <br/> <img src="./images/de2bf86e.jpeg" class="centered" height="470px"/> </article> <article> <h3>GraphDB とは？</h3> <p>このような構造をしたGraphは<span style="color: red">PropertyGraph</span>と呼ばれる．</p> <p>PropertyGraphとは，</p> <br/> <img src="./images/propertygraph_sw.png" height="470px" class="centered"/> </article> <article> <h3>PropertyGraph</h3> <p><span color="red">関係・人物・名前・特徴</span>は<span color="red">Vertex・Edge・Label・Property</span>と呼ばれる．</p> <small> <ul> <li>Edge(関係)が方向を持つ</li> <li>Vertex(人物)とEdge(関係)はLabel(名前)を持つ</li> <li><span style="color: red">VertexとEdgeはKey/Valueのマップ(Property)を持っている．</span></li> </ul> </small> <img src="./images/propertygraph_sw2.png" height="400px" class="centered"/> </article> <article> <h3>GraphDBとは？</h3> <p>GraphDBは，保存されたGraphのVertex,Edgeを渡り歩き，目的のデータを取得するようなデータベースである．</p> <p>渡り歩くことをTraverseという．</p> <br/> <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> <br/> <br/> <img height="300px" src="./images/tinkerpop_with_name.png" class="centered"/> </article> <article> <h3>Blueprints</h3> <p>Blueprintsは，PropertyGraphのJavaのinterfaceを提供する．</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>Gremlin</h3> <p>GraphをTraverseするための言語．Groovyがベースである．GraphDBに対してQueryを発行することが出来る．コンソールも利用できる．</p> <pre>gremlin> graph.v(1).out.name ==>vadas ==>lop ==>josh</pre> <p>GremlinはPipesを利用して，GraphをTraverseする．.out.nameがPipeである．．</p> <img src="./images/gremlin-logo.png"/> </article> <article> <h3>Pipes</h3> <p>PipesはGraphを処理するためのフレームワークである．Pipeという処理の単位を複数連結し，複雑なTraverseを実現する．</p> <img src="./images/pipes.png" height="150px" class="center"/> <p>graph.v(1)はGraphからIDか1のVertexを取得する，.out .name がぞれぞれPipeに値する．</p> <img src="./images/pipes-logo.png" height="200px"/> </article> <article> <h3>Pipes</h3> <p>この例題の動作は・・・</p> <br/> <br/> <img style="float: left; margin-right:10px" src="./images/pipes-mario-2.png" height="300px"/> <br/> <img src="./images/pipes-mario-4.png" height="75px"/> <pre>gremlin> g.v(1).out.name ==>vadas ==>lop ==>josh</pre> <br style="clear: both;"/> <small> <p>outはVertexから外向きのEdgeで繋がっているVertex一覧を取得する，nameはProperty名でPipeではVertexのnameを取得している．</p> </small> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <br/> <ol> <li>BlueprintsでTinkerGraphにストライクウィッチーズの相関図を入力する．</li> <li>作成したTinkerGraphを，</li> <ul> <li>Gremlinのコンソールから解析してみる．</li> <li>JavaからGremlinを使って解析してみる．</li> </ul> </ol> <br/> <p>まずは，TinkerGraphにストライクウィッチーズの相関図を入力する．</p> </article> <article> <h3>この発表のサンプルコードについて</h3> <br/> <p><span style="color:red">hg clone https://bitbucket.org/suikwasha/graphdb_javakuche</span></p> <br/> <small> <p>Mavenというプロジェクト管理ツールを利用したプロジェクトになってます．</p> </small> <pre>ビルド方法・解凍したディレクトリに移動して $ mvn compile</pre> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p>Blueprintsは，GraphDBへのインターフェイスを提供する．TinkerGraphはBlueprintsを用いて利用できる．</p> <small> <p>相関図のGraphを作るためには，<span style="color:red">Graph</span>を作成し<span style="color:red">人物（Vertex）</span>と<span style="color:red">関係（Edge）</span>，<span style="color:red">特徴（Property）</span>を作る必要がある．</p> </small> <small> <pre>// 相関図（Graph）の作成，データを保存するディレクトリを引数に取る Graph g = new TinkerGraph();</pre> <pre>// 人物（Vertex）の作成，設定したいIDを引数に取る Vertex character = g.addVertex(ID);</pre> <pre>// 関係（Edge）の作成，設定したいIDを引数に取る Edge relation = g.addEdge(ID,From,To,Label);</pre> <pre>// 特徴（Property）の作成 , Vertex・Edgeともに同様のメソッド character.setProperty(PropertyName,PropertyValue);</pre> </small> </article> <article> <h3>ストライクウィッチーズの相関図を解析するには？</h3> <p>これを入力します．</p> <img src="./images/de2bf86e.jpeg" height="550px" class="centered"/> </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.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,"仲良し新人コンビ");</pre> </small> </article> <article> <h3>CreateStrikeWitchesGraph</h3> <p>実際にコードを動作させてTinkerGraphに入力する．</p> <br/> <small> <p>mvn exec:java -Dexec.mainClass=suikwasha.javakuche.CreateStrikeWitchesGraph</p> </small> <br/> <p>プロジェクトのディレクトリにstrikwitchesが作成される．</p> </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>Gremlinのコンソールから解析してみる．</li> <li>Javaから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>% ./gremlin.sh [~/Downloads/gremlin-groovy-2.1.0/bin] \,,,/ (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>Vertexの一覧を取得してみる．</p> <pre>gremlin> g.V // GraphのVertex一覧 ==>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><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> <img src="./images/traverse_demo.png" height="250px" class="centered"/> </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> <small> <p>{it.age < 16}はクロージャである．outで出力されたキャラクターのVertexが，それぞれitに格納される．Groovyでitは暗黙に定義されるクロージャの変数であり，第一引数が自動的に割り当てられる．</p> </small> </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<Vertex,String> pipe = new GremlinPipeline<Vertex,String>(); 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(String 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(Integer 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<Vertex,Boolean>(){ public Boolean compute(Vertex _argument){ return (Integer)_argument.getProperty("age") >= 15; } }).name; for(String 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>_()はGremlinePipelineに定義されている何もしないPipe</p> <p>JavaでPipeを直接構築するより，こっちのほうが簡単である．</p> </article> <article> <h3>まとめ</h3> <p>これまでに，ストライクウィッチーズの相関図を利用してGraphDBの概要とTinkerPopの簡単な使い方を見てきた．</p> <p>この発表で大体のイメージが掴めてもらえれば幸いです．</p> <ul> <li>GraphDBは，GraphのEdgeをTraverseして，目的のデータを取得するデータベース</li> <li>GraphDBは，PropertyGraphを格納する．</p> <li>TinkerPopは，GraphDBを利用するためのツールの集合</li> </ul> <br/> <p>次に，具体的な利用例としてPageRankのGraphDBでの表現について発表する．</p> </article> <article> <h3>TinkerPopによるPageRankの実装</h3> <ul> <li>PageRankアルゴリズム</li> <li>PageとPageRankのGraphDBによる表現</li> <li>TinkerPopによるPageRankの計算</li> <li>Pipesによる走査</li> <li>PageRankの計算にかかる時間</li> </ul> </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>PageとPageRankのGraphDBによる表現</h3> <ul> <li>アンサイクロペディアの各ページをGraphDBで表す。</li> <li>1Vertexが1つのページを表す。</li> <li>各VertexはPageTitleとPageRankをPropertyとして持つ。</li> <li>リンクは "HAS_LINK" という関係で表される。</li> <li>PageRankはdoubleで初期値は 0.15 , 最大値はページ数*0.15</li> <li>アンサイクロペディアではURIはページタイトルと同じ。</li> <li>URIに対してユニークなVertexID を割り振る。</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を求める。</li> <!-- <li>PageRankはリンクを張ってくるページのPageRankが加算される。 </li> <li>この時加算されるPageRankはリンクの数で割られた値となる。</li> --> </ul> </article> <article> <h3>PageRankの取得</h3> <ul> <p class="center"> <img src="./pic/page_rank.png" style="height:40%;"> </p> <li>TinkerGraph上でPageRankの値を出すために以下の2つの値が必要</li> <ul> <li>リンク("HasLink")の関係を張ってくるVertexの取得</li> <li>リンクしてくるVertexがどれだけリンクを張っているかを取得</li> <small><p>*各ページの情報はXMLから取り出しBlueprintsを用いてTinkerGraphに書き込み済み。</p></small> </ul> </ul> </article> <article> <h3>Pipesによる走査</h3> <ul> <li>あるページへとリンクを張るページ(Vertex)の取得</li> <small><p>「id」はVertexのIDを表す。</p></small> <pre> Graph graph = ... GremlinPipeline pipe = new GremlinPipeline(); pipe.start(graph.getVertex(id)); pipe.in("HasLink"); for (Object inVerObj : pipe) { VertexinVer = (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; Vertexv = graph.getVertex(id); GremlinPipeline pipe = new GremlinPipeline(); pipe.start(graph.getVertex(id)).in("HasLink"); for (Object inVerObj : pipe) { VertexinVer = (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>計算結果</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> <li>全Vertexに対しての計算量はVertexの数に比例していることが確認できた。 </li> </ul> </article> <article> <h3>今日の勉強会で覚えておきたいこと</h3> <ul> <li>Graph の関係を表すようなデータはGraphDBで表現しやすい。</li> <li>GraphDBではVertex間を渡り歩く(Traverse)ことでデータの取得を行う。 </li> <li>GraphDBは局所性のあるデータを高速に計算することができる。</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] LawrencePage, Sergey Brin, Rajeev Motwani, Terry Winograd, 'ThePageRankCitation 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] ThePageRankAlgorithm<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 ofPageRank', 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>なぜ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> </section> </body> </html>