Mercurial > hg > Papers > 2012 > JavaKuche

changeset 9:dffb9ea9d1a9 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 08 Sep 2012 08:36:17 +0900
parents 2d7dc1332fff
children a7ae614deffc
files index.html
diffstat 1 files changed, 64 insertions(+), 56 deletions(-) [+]
line wrap: on
line diff
--- a/index.html	Sat Sep 08 08:20:17 2012 +0900
+++ b/index.html	Sat Sep 08 08:36:17 2012 +0900
@@ -412,37 +412,46 @@
   	  	<p>次に，具体的な利用例としてPageRankのGraphDBでの表現について発表する．</p>
   	  </article> 
 
-
+      <article>
+	<li>TinkerPopによるPageRankの実装</li>
+	<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>
+	<h3>GoogleのPageRankアルゴリズム</h3>
 	<ul>
-	  <li>Google の Webページ検索エンジンに使われているアルゴリズム。</li>
+	  <li>GoogleのWebページ検索エンジンに使われているアルゴリズム。</li>
 	  <li>あるページの『重要度』を示す値で、各ページ毎に持っている。 </li>
-	  <li>PageRank が高いほど検索結果の上位に表示される。</li>
+	  <li>PageRankが高いほど検索結果の上位に表示される。</li>
 	  <li>『多くの良質なページからリンクされているページは、やはり良質なページである』という考えのアルゴリズム<br></li>
-	  <li>GraphDB は PageRank の計算に向いている。</li>
+	  <li>GraphDBはPageRankの計算に向いている。</li>
 	</ul>
       </article>
 
 
       <article>
-	<h3>Page と PageRank の GraphDB による表現</h3>
+	<h3>PageとPageRankのGraphDBによる表現</h3>
 	<ul>
-	  <li>アンサイクロペディアの各ページを GraphDB で表す。</li>
-	  <li>1 Vertex が1つのページを表す。</li>
-	  <li>各Vertex は Page Title と PageRank を Property として持つ。</li>
+	  <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 に対してユニークな Vertex ID を割り振る。</li>
+	  <li>PageRankはdoubleで初期値は 0.15 , 最大値はページ数*0.15</li>
+	  <li>アンサイクロペディアではURIはページタイトルと同じ。</li>
+	  <li>URIに対してユニークなVertexID を割り振る。</li>
 	</ul>	  
       </article>      
 
       <article>
-	<h3>TinkerPop による PageRank の計算</h3>	
+	<h3>TinkerPopによるPageRankの計算</h3>	
 	<ul>
-	  <li>○は Vertex を、→ は Edge を表す。</li>
+	  <li>○はVertexを、→ はEdgeを表す。</li>
 	  <p class="center">
 	  <img src="./pic/graph.png" style="height:70%;">
 	  </p>
@@ -451,31 +460,31 @@
       </article>      
 
       <article>
-	<h3>PageRank アルゴリズム</h3>
+	<h3>PageRankアルゴリズム</h3>
 	<ul>
-	  <li>PageRank は次の計算式で求めることができる。</li>
+	  <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>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>GoogleのPageRankはこれを改良したものである。</li>
 <!--
-	  <li>PageRank はリンクを張ってくるページの PageRank が加算される。 </li>
-	  <li>この時加算される PageRank はリンクの数で割られた値となる。</li>
+	  <li>PageRankはリンクを張ってくるページのPageRankが加算される。 </li>
+	  <li>この時加算されるPageRankはリンクの数で割られた値となる。</li>
 -->
 	</ul>
       </article>
 
       <article>
-	<h3>PageRank の取得</h3>
+	<h3>PageRankの取得</h3>
 	<ul>
-	  <li>TinkerPop 上で PageRank の値を出すために以下の2つの値が必要</li>
+	  <li>TinkerPop上でPageRankの値を出すために以下の2つの値が必要</li>
 	  <ul>
-	    <li>リンク("HasLink")の関係を張ってくる Vertex の取得</li>
-	    <li>リンクしてくる Vertex がどれだけリンクを張っているかを取得</li>
-	  <small><p>*各ページの情報は XML から取り出し Blueprints を用いて TinkerGraph に書き込み済み。</p></small>
+	    <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>
@@ -485,7 +494,7 @@
       </article>
 
       <article>
-	<h3>Pipes による走査</h3>
+	<h3>Pipesによる走査</h3>
 	<ul>
 	  <li>あるページへとリンクを張るページ(Vertex)の取得</li>
 	  <pre>
@@ -494,7 +503,7 @@
 pipe.start(graph.getVertex(id));
 pipe.in("HasLink");
 for (Object inVerObj : pipe) {
-  Vertex inVer = (Vertex)inVerObj;
+ VertexinVer = (Vertex)inVerObj;
   :
 }	  </pre>
 	  <p class="center">
@@ -502,10 +511,9 @@
 	  </p>
 	</ul>
       </article>
-      
 
       <article>
-	<h3>Pipes による走査</h3>
+	<h3>Pipesによる走査</h3>
 	<ul>
 	<li>あるページが張っているリンクの数の取得</li>
 	  <pre>
@@ -522,17 +530,17 @@
       </article>
 
       <article>
-	<h3>TinkerPop による PageRank の計算</h3>
+	<h3>TinkerPopによるPageRankの計算</h3>
 	<ul>
 <pre>
 final double weight = 0.85;
 double sum = 0.0;
 double pageRank = 0.0;
-Vertex v = graph.getVertex(id);
+Vertexv = graph.getVertex(id);
 GremlinPipeline pipe = new GremlinPipeline();
 pipe.start(graph.getVertex(id)).in("HasLink");
 for (Object inVerObj : pipe) {
-  Vertex inVer = (Vertex) inVerObj;
+ VertexinVer = (Vertex) inVerObj;
   Object inVerId = inVer.getId();
   GremlinPipeline inPipe = new GremlinPipeline();
   inPipe.start(graph.getVertex(inVerId)).out("HasLink");
@@ -549,7 +557,7 @@
       <article>
 	<h3>計算結果</h3>
 	<ul>
-	  <li>アンサイクロペディア内で PageRank の高いページ</li>
+	  <li>アンサイクロペディア内でPageRankの高いページ</li>
 	  <li>総ページ数: 242014 ページ</li>
 	  <table>
 	    <tr>
@@ -591,9 +599,9 @@
       </article>
 
       <article>
-	<h3>PageRank の計算にかかる時間</h3>
+	<h3>PageRankの計算にかかる時間</h3>
 	<ul>
-	  <li>PageRank は 10 回程の計算でほぼ収束した。</li>
+	  <li>PageRankは 10 回程の計算でほぼ収束した。</li>
 	  <table>
 	    <td>
 	      <img src="./pic/pageRank.png" style="height:70%;">
@@ -602,12 +610,12 @@
 	      <img src="./pic/computePageRank.png" style="height:70%;">
 	    </td>
 	  </table>
-	  <li>PageRank の計算は10回行うとして、ページ数に対してかかる時間を測ってみた。</li>
+	  <li>PageRankの計算は10回行うとして、ページ数に対してかかる時間を測ってみた。</li>
 	</ul>
       </article>
 
       <article>
-	<h3>PageRank の計算にかかる時間</h3>
+	<h3>PageRankの計算にかかる時間</h3>
 	<ul>
 	  <li>各ページ数で行う10回計算をそれぞれ10回ずつタイムを測り平均をとった。</li>
 	  <table>
@@ -649,7 +657,7 @@
 
 
       <article>
-	<h3>PageRank の計算にかかる時間</h3>
+	<h3>PageRankの計算にかかる時間</h3>
 	<ul>
 	  <img src="./pic/pageRankCompare.png">
 	</ul>
@@ -658,36 +666,36 @@
       <article>
 	<h3>まとめ</h3>
 	<ul>
-	  <li>今回、TinkerPop を用いてアンサイクロペディアの各ページの PageRank を求めた。</li>
-	  <li>各ページと Vertex, リンクの関係を Edge で表すことで各ページ間の関係を TinkerPop 上で表した。 </li>
-	  <li>Gremlin を用いて各 Vertex を渡り歩ことで PageRank の計算を行った。</li>
-	  <li>全 Vertex に対しての計算量は Vertex の数に比例していることが確認できた。 </li>
+	  <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>
+	  <li>Graph の関係を表すようなデータはGraphDBで表現しやすい。</li>
+	  <li>GraphDBではVertex間を渡り歩く(Traverse)ことでデータの取得を行う。 </li>
+	  <li>GraphDBは局所性のあるデータを高速に計算することができる。</li>
 	</ul>
       </article>
 
       <article>
 	<h3>参考文献・サイト</h3>
 	<ul>
-	  <small><li>[1] Google の秘密 - PageRank 徹底解説<br>
+	  <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>
+	  <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] The PageRank Algorithm<br>
+	  <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>
+	  <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>
+	  <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>
@@ -697,14 +705,14 @@
 
 
       <article>
-	<h3>なぜ PageRank なのか</h3>
+	<h3>なぜPageRankなのか</h3>
 	<ul>
-	  <li>PageRank は Page と Page のリンクの有無を利用して計算できる。</li>
-	  <li>GraphDB は Vertex と Vertex を結ぶ Edge を走査(Traverse)することで、
+	  <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 
+	  <li>また、GraphDBは局所性のあるデータを高速に計算することができる。 </li>
+	  <li>PageRankのPageの関係はGraphDBのVertexとEdgeで表すことができる<li>
+	  <li>また、Pageの数が増えても局所的な計算ができるためGraphDBはPageRank
 	  を求める DB に向いている。</li>
 	</ul>
       </article>