changeset 1:1ddca33b4d4e

added property_graph_traverse etc..
author Shoshi TAMAKI
date Wed, 23 Jan 2013 11:15:53 +0900
parents bf82975fa7f5
children d0addd917047
files chapter2.tex images/property_graph_traverse.graffle master_paper.aux master_paper.dvi master_paper.lof master_paper.log master_paper.lot master_paper.pdf master_paper.tex master_paper.toc
diffstat 10 files changed, 661 insertions(+), 117 deletions(-) [+]
line wrap: on
line diff
--- a/chapter2.tex	Tue Jan 22 23:28:03 2013 +0900
+++ b/chapter2.tex	Wed Jan 23 11:15:53 2013 +0900
@@ -197,9 +197,9 @@
 
 \subsubsection{Push/Pull方式}
 Push/Pull方式とは, 分散レポジトリで利用されているレポジトリの結合方法の1つである.
-分散バージョン管理システムでのレポジトリはお互いにPush/Pullを用いて自身の更新を通知・受信することができる.
+分散バージョン管理システムでのレポジトリはお互いにPush/Pullを用いて自身の更新を通知・受信することができる.\\
 Pushとは, あるレポジトリが異なるレポジトリに自分の持つ更新を通知することで, Pullは, その逆の更新を他のレポジトリより受信することである.
-また, 異なる履歴を持つレポジトリ同士がPush/Pullを行う時お互いの更新がしょうとする可能性が考えられる, これらの問題はマージを用いることで解決する.
+また, 異なる履歴を持つレポジトリ同士がPush/Pullを行う時お互いの更新がしょうとする可能性が考えられる, これらの問題はマージを用いることで解決する.\\
 これを我々が提案した方法に当てはめると以下のようになる.
 
 \begin{itemize}
@@ -219,8 +219,8 @@
  \label{fig:merge_sample_success}
 \end{figure}
 
-この状態は衝突が発生していない, なぜならPull元が編集されていないためである. 次に図\ref{fig:merge_sample_success}について考える.
-この場合, お互いの異なる履歴をもつ木構造がマージされる場合で変更が衝突している. しかし, 一方の木構造に対する変更が, もう一方の木構造の編集と衝突していない.
+この状態は衝突が発生していない, なぜならPull元が編集されていないためである. 次に図\ref{fig:merge_sample_success}について考える.\\
+この場合, お互いの異なる履歴をもつ木構造がマージされる場合で変更が衝突している. しかし, 一方の木構造に対する変更が, もう一方の木構造の編集と衝突していない.\\
 よってこの場合は自然にマージすることが可能である.
 
 \begin{figure}[!htbp]
@@ -241,13 +241,13 @@
  \label{fig:merge_sample_fail}
 \end{figure}
 
-衝突する場合は, マージ処理が必要である.マージ処理はお互いの変更点を検出し, 更新を自身の木構造に衝突を取り除いた状態で取り込むことである.
-分散レポジトリでは, お互いの更新点を検出する際に変更履歴を利用することで効率よくマージを実行することが出来ると考えられため, 我々のシステムでもマージの際に木構造に対しての更新履歴を参照できるようにする.
-マージには衝突を回避する他に, スケーラブルにするために工夫を加えることが出来る. なぜならば, 管理するコンテンツにおいて厳密なマージ処理が必要なコンテンツとそうでないコンテンツが存在するからである.
+衝突する場合は, マージ処理が必要である.マージ処理はお互いの変更点を検出し, 更新を自身の木構造に衝突を取り除いた状態で取り込むことである.\\
+分散レポジトリでは, お互いの更新点を検出する際に変更履歴を利用することで効率よくマージを実行することが出来ると考えられため, 我々のシステムでもマージの際に木構造に対しての更新履歴を参照できるようにする.\\
+マージには衝突を回避する他に, スケーラブルにするために工夫を加えることが出来る. なぜならば, 管理するコンテンツにおいて厳密なマージ処理が必要なコンテンツとそうでないコンテンツが存在するからである.\\
 そのため, 我々のシステムでは単純なマージアルゴリズムのほか, プログラマがマージアルゴリズムを記述できるようにできる仕組みを導入する. 
 
 \subsection{グラフデータベース}
-グラフデータベースとはリレーショナルデータベースと異なり, グラフ構造を保存するデータベースである. 主な実装にNeo4j,OrientDB,InfiniteGraphがあるほか, TinkerPopという様々なグラフデータベースの実装の差異を吸収するためのプロジェクトも存在する.
+グラフデータベースとはリレーショナルデータベースと異なり, グラフ構造を保存するデータベースである. 主な実装にNeo4j,OrientDB,InfiniteGraphがあるほか, TinkerPopという様々なグラフデータベースの実装の差異を吸収するためのプロジェクトも存在する.\\
 グラフデータベースはプロパティグラフと呼ばれる種類のグラフを保持することが出来る. 主にソーシャルネットワークの人物関係を表すソーシャルグラフを表現するのに利用されるほか, ページランクのアルゴリズムにも利用される.
 
 \begin{figure}[!htbp]
@@ -259,22 +259,56 @@
 \end{figure}
 
 \subsubsection{トラバース}
-グラフデータベースでのデータの検索方法はトラバースと呼ばれ, グラフ上を渡り歩く方法を示すことで目的のデータを取得する.
+グラフデータベースでのデータの検索方法はトラバースと呼ばれ, グラフ上を渡り歩く方法を示すことで目的のデータを取得する.\\
 トラバースは, 並列に効率よく行うことが可能であるためスケーラビリティに貢献できると考えられる. 以下にTinkerPopでのトラバース方法を示す.
-\\
-{\bf 並列にグラフをトラバースする図}
-\\ \\
+
+\begin{lstlisting}[frame=lrbt,label=src:property_graph_traverse_tinkerpop,caption=トラバースの例,numbers=left]
+graph.v(1).out('knows').out('father);
+\end{lstlisting}
+
+\begin{figure}[!htbp]
+ \begin{center}
+  \includegraphics[width=100mm]{./images/property_graph_traverse.pdf}
+ \end{center}
+ \caption{プロパティグラフのトラバース例}
+\end{figure}
+
 我々のシステムでは, トラバースを木構造の検索方法として採用する. 
 木構造はグラフ構造の1つであるため効率よく検索を行うことができると考えられるからである.
+なぜならば, 複数の結果が得られるようなトラバース例を考える. このとき, 
 
 \subsection{ブラウザサイドの実装}
 近年のウェブブラウザはJavaScriptでかなり複雑な処理が可能になっている. その上, HTML5の制定によりウェブストレージやウェブソケットなどのIOまでサポートされるようになる.
 以下に, HTML5で実装される主なIO関連の機能を示す.
-\\
-{\bf HTML5で実装される機能一覧}
-\\ \\
+
+\begin{table}[!htbp]
+ \caption{HTML5で実装される新機能}
+ \label{tab:HTML5_functions}
+ \begin{center}
+  \begin{tabular}{|c||p{25zw}|} \hline
+   名称 & 説明 \\ \hline \hline
+   WebSocket & ウェブサーバーとウェブブラウザが相互通信するための機能. \\ \hline
+   Indexed Database API & 値とオブジェクトをローカルデータベースに保存できる.  \\ \hline
+   WebStorage & 値とオブジェクトの組みを保存できる, sessionStorageとlocalStorageの2種類が存在する. \\ \hline
+   App Cache & キャッシュマニフェストでブラウザのキャッシュを操作できるようになる. \\ \hline
+  \end{tabular}
+ \end{center}
+\end{table}
+
 通常, システムの負荷はクライアントの数に応じて増加する. 我々のシステムにおいてはクライアントはウェブブラウザに相当するため, ウェブブラウザをスケーラビリティに貢献できるようにすることでかなりの効果を期待できると考えられる.
 
 \section{全体の設計}
 提案手法を用いたシステム全体の概略図を以下に示す.
-\subsection{Push/Pullプロトコルの制定}
+
+\begin{figure}[!htbp]
+ \begin{center}
+  \includegraphics[width=150mm]{./images/basic_architecture.pdf}
+ \end{center}
+ \caption{システム全体の概要図}
+ \label{fig:basic_architecture}
+\end{figure}
+
+本システムでは, データ構造として木構造を採用する. 各サーバー・クライアントはそれぞれ木構造が保存されており, サーバーはサーバー同士で木構造のpush/pullを行い, クライアントはサーバーと木構造のpush/pullを行う.
+前述した, スケーラブルにする方法,
+
+
--- a/images/property_graph_traverse.graffle	Tue Jan 22 23:28:03 2013 +0900
+++ b/images/property_graph_traverse.graffle	Wed Jan 23 11:15:53 2013 +0900
@@ -1454,6 +1454,469 @@
 	<array>
 		<dict>
 			<key>Bounds</key>
+			<string>{{310, 107}, {64, 14}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>FitText</key>
+			<string>YES</string>
+			<key>Flow</key>
+			<string>Resize</string>
+			<key>ID</key>
+			<integer>3081</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Pad</key>
+				<integer>0</integer>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg932\cocoartf1187\cocoasubrtf340
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 .out('father')}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>Wrap</key>
+			<string>NO</string>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{190, 101}, {67, 14}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>FitText</key>
+			<string>YES</string>
+			<key>Flow</key>
+			<string>Resize</string>
+			<key>ID</key>
+			<integer>3080</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Pad</key>
+				<integer>0</integer>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg932\cocoartf1187\cocoasubrtf340
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 .out('knows')}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>Wrap</key>
+			<string>NO</string>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{138.35350036621094, 63}, {55, 14}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>FitText</key>
+			<string>YES</string>
+			<key>Flow</key>
+			<string>Resize</string>
+			<key>ID</key>
+			<integer>3079</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Pad</key>
+				<integer>0</integer>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg932\cocoartf1187\cocoasubrtf340
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 graph.v(1)}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>Wrap</key>
+			<string>NO</string>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{485.8323974609375, 63}, {35, 18}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>FitText</key>
+			<string>YES</string>
+			<key>Flow</key>
+			<string>Resize</string>
+			<key>FontInfo</key>
+			<dict>
+				<key>Font</key>
+				<string>Helvetica</string>
+				<key>Size</key>
+				<real>14</real>
+			</dict>
+			<key>ID</key>
+			<integer>3078</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Pad</key>
+				<integer>0</integer>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg932\cocoartf1187\cocoasubrtf340
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs30 \cf0 FIND}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>Wrap</key>
+			<string>NO</string>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{15, 63}, {45, 17}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>FitText</key>
+			<string>YES</string>
+			<key>Flow</key>
+			<string>Resize</string>
+			<key>FontInfo</key>
+			<dict>
+				<key>Font</key>
+				<string>Helvetica</string>
+				<key>Size</key>
+				<real>13</real>
+			</dict>
+			<key>ID</key>
+			<integer>3077</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Pad</key>
+				<integer>0</integer>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg932\cocoartf1187\cocoasubrtf340
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs28 \cf0 START}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>Wrap</key>
+			<string>NO</string>
+		</dict>
+		<dict>
+			<key>Class</key>
+			<string>LineGraphic</string>
+			<key>Head</key>
+			<dict>
+				<key>ID</key>
+				<integer>3074</integer>
+			</dict>
+			<key>ID</key>
+			<integer>3076</integer>
+			<key>Points</key>
+			<array>
+				<string>{309.16752627704227, 171.67190309501501}</string>
+				<string>{326.60390000000001, 131}</string>
+				<string>{388.88978855486329, 132.05807547667217}</string>
+			</array>
+			<key>Style</key>
+			<dict>
+				<key>stroke</key>
+				<dict>
+					<key>HeadArrow</key>
+					<string>FilledArrow</string>
+					<key>Legacy</key>
+					<true/>
+					<key>LineType</key>
+					<integer>1</integer>
+					<key>Pattern</key>
+					<integer>1</integer>
+					<key>TailArrow</key>
+					<string>0</string>
+					<key>Width</key>
+					<real>2</real>
+				</dict>
+			</dict>
+			<key>Tail</key>
+			<dict>
+				<key>ID</key>
+				<integer>3073</integer>
+			</dict>
+		</dict>
+		<dict>
+			<key>Class</key>
+			<string>LineGraphic</string>
+			<key>Head</key>
+			<dict>
+				<key>ID</key>
+				<integer>3073</integer>
+			</dict>
+			<key>ID</key>
+			<integer>3075</integer>
+			<key>Points</key>
+			<array>
+				<string>{158.85272817727991, 128.12186683981611}</string>
+				<string>{225, 126}</string>
+				<string>{253.55105273907645, 171.7778048201649}</string>
+			</array>
+			<key>Style</key>
+			<dict>
+				<key>stroke</key>
+				<dict>
+					<key>HeadArrow</key>
+					<string>FilledArrow</string>
+					<key>Legacy</key>
+					<true/>
+					<key>LineType</key>
+					<integer>1</integer>
+					<key>Pattern</key>
+					<integer>1</integer>
+					<key>TailArrow</key>
+					<string>0</string>
+					<key>Width</key>
+					<real>2</real>
+				</dict>
+			</dict>
+			<key>Tail</key>
+			<dict>
+				<key>ID</key>
+				<integer>3072</integer>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{390.38957214355469, 81.436798095703125}, {104.17674255371094, 103.06320190429688}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>3074</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Cap</key>
+					<integer>0</integer>
+					<key>Join</key>
+					<integer>0</integer>
+					<key>Pattern</key>
+					<integer>1</integer>
+					<key>Width</key>
+					<real>3</real>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Align</key>
+				<integer>0</integer>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>TextPlacement</key>
+			<integer>0</integer>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{234.39610290527344, 173.05055236816406}, {104.17674255371094, 103.06320190429688}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>3073</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Cap</key>
+					<integer>0</integer>
+					<key>Join</key>
+					<integer>0</integer>
+					<key>Pattern</key>
+					<integer>1</integer>
+					<key>Width</key>
+					<real>3</real>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Align</key>
+				<integer>0</integer>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>TextPlacement</key>
+			<integer>0</integer>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{40.999998999023433, 83.036148071289062}, {116.35350036621094, 94}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>3072</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Cap</key>
+					<integer>0</integer>
+					<key>Join</key>
+					<integer>0</integer>
+					<key>Pattern</key>
+					<integer>1</integer>
+					<key>Width</key>
+					<real>3</real>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Align</key>
+				<integer>0</integer>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>TextPlacement</key>
+			<integer>0</integer>
+		</dict>
+		<dict>
+			<key>Bounds</key>
 			<string>{{456, 237}, {53, 14}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
@@ -1859,7 +2322,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{326.55258178710938, 73}, {96, 28}}</string>
+			<string>{{346.20779418945312, 33}, {96, 42}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -1898,7 +2361,8 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
 
-\f0\fs24 \cf0 name =george\
+\f0\fs24 \cf0 ID = 4\
+name =george\
 job = programmer}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
@@ -1908,7 +2372,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{296, 319.41024780273438}, {96, 28}}</string>
+			<string>{{294, 305.41024780273438}, {96, 42}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -1947,7 +2411,8 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
 
-\f0\fs24 \cf0 name = gina\
+\f0\fs24 \cf0 ID = 5\
+name = gina\
 job = programmer}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
@@ -1957,7 +2422,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{164.3961009979248, 203.5821533203125}, {70, 42}}</string>
+			<string>{{154.99999809265137, 198}, {70, 56}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -1996,7 +2461,8 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
 
-\f0\fs24 \cf0 name = gina\
+\f0\fs24 \cf0 ID = 3\
+name = gina\
 age = 23\
 job = student}</string>
 				<key>VerticalPad</key>
@@ -2007,7 +2473,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{15.458099365234375, 298}, {74, 28}}</string>
+			<string>{{15.458099365234375, 298}, {74, 42}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -2046,7 +2512,8 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
 
-\f0\fs24 \cf0 name = sarah\
+\f0\fs24 \cf0 ID = 2\
+name = sarah\
 age = 40}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
@@ -2346,7 +2813,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{9.91619873046875, 66.0677490234375}, {67, 28}}</string>
+			<string>{{65.676750183105469, 29}, {67, 42}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -2385,7 +2852,8 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
 
-\f0\fs24 \cf0 name = john\
+\f0\fs24 \cf0 ID = 1\
+name = john\
 age = 29}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
@@ -2513,7 +2981,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2013-01-22 14:13:38 +0000</string>
+	<string>2013-01-22 14:54:17 +0000</string>
 	<key>Modifier</key>
 	<string>shoshi</string>
 	<key>NotesVisible</key>
@@ -2589,7 +3057,7 @@
 		<key>ExpandedCanvases</key>
 		<array/>
 		<key>Frame</key>
-		<string>{{-1307, 228}, {937, 1019}}</string>
+		<string>{{-1772, 209}, {937, 1019}}</string>
 		<key>ListView</key>
 		<true/>
 		<key>OutlineWidth</key>
--- a/master_paper.aux	Tue Jan 22 23:28:03 2013 +0900
+++ b/master_paper.aux	Wed Jan 23 11:15:53 2013 +0900
@@ -85,34 +85,40 @@
 \@writefile{lof}{\contentsline {figure}{\numberline {3.16}{\ignorespaces プロパティグラフの例}}{16}}
 \newlabel{fig:property_graph}{{3.16}{16}}
 \@writefile{toc}{\contentsline {subsubsection}{トラバース}{16}}
+\newlabel{src:property_graph_traverse_tinkerpop}{{3.1}{16}}
+\@writefile{lol}{\contentsline {lstlisting}{\numberline {3.1}トラバースの例}{16}}
+\@writefile{lof}{\contentsline {figure}{\numberline {3.17}{\ignorespaces プロパティグラフのトラバース例}}{17}}
 \@writefile{toc}{\contentsline {subsection}{\numberline {3.3.4}ブラウザサイドの実装}{17}}
-\@writefile{toc}{\contentsline {section}{\numberline {3.4}全体の設計}{17}}
-\@writefile{toc}{\contentsline {subsection}{\numberline {3.4.1}Push/Pullプロトコルの制定}{17}}
-\@writefile{toc}{\contentsline {chapter}{\numberline {第4章}分散コンテンツマネージメントシステムの実装}{18}}
+\@writefile{lot}{\contentsline {table}{\numberline {3.1}{\ignorespaces HTML5で実装される新機能}}{17}}
+\newlabel{tab:HTML5_functions}{{3.1}{17}}
+\@writefile{toc}{\contentsline {section}{\numberline {3.4}全体の設計}{18}}
+\@writefile{lof}{\contentsline {figure}{\numberline {3.18}{\ignorespaces システム全体の概要図}}{18}}
+\newlabel{fig:basic_architecture}{{3.18}{18}}
+\@writefile{toc}{\contentsline {chapter}{\numberline {第4章}分散コンテンツマネージメントシステムの実装}{19}}
 \@writefile{lof}{\addvspace {10\p@ }}
 \@writefile{lot}{\addvspace {10\p@ }}
-\@writefile{toc}{\contentsline {section}{\numberline {4.1}はじめに}{18}}
-\@writefile{toc}{\contentsline {section}{\numberline {4.2}開発環境}{18}}
-\@writefile{toc}{\contentsline {subsection}{\numberline {4.2.1}言語}{18}}
-\@writefile{toc}{\contentsline {section}{\numberline {4.3}全体の構造}{18}}
-\@writefile{toc}{\contentsline {section}{\numberline {4.4}木構造の検索}{18}}
-\@writefile{toc}{\contentsline {subsection}{\numberline {4.4.1}Traverser}{18}}
-\@writefile{toc}{\contentsline {section}{\numberline {4.5}木構造読み込み}{18}}
-\@writefile{toc}{\contentsline {subsection}{\numberline {4.5.1}Journal}{18}}
-\@writefile{toc}{\contentsline {section}{\numberline {4.6}木構造への書き込み}{18}}
-\@writefile{toc}{\contentsline {subsection}{\numberline {4.6.1}TreeEditor}{18}}
-\@writefile{toc}{\contentsline {section}{\numberline {4.7}木構造のマージ}{18}}
-\@writefile{toc}{\contentsline {subsection}{\numberline {4.7.1}Merger}{18}}
-\@writefile{toc}{\contentsline {chapter}{\numberline {第5章}結論}{19}}
+\@writefile{toc}{\contentsline {section}{\numberline {4.1}はじめに}{19}}
+\@writefile{toc}{\contentsline {section}{\numberline {4.2}開発環境}{19}}
+\@writefile{toc}{\contentsline {subsection}{\numberline {4.2.1}言語}{19}}
+\@writefile{toc}{\contentsline {section}{\numberline {4.3}全体の構造}{19}}
+\@writefile{toc}{\contentsline {section}{\numberline {4.4}木構造の検索}{19}}
+\@writefile{toc}{\contentsline {subsection}{\numberline {4.4.1}Traverser}{19}}
+\@writefile{toc}{\contentsline {section}{\numberline {4.5}木構造読み込み}{19}}
+\@writefile{toc}{\contentsline {subsection}{\numberline {4.5.1}Journal}{19}}
+\@writefile{toc}{\contentsline {section}{\numberline {4.6}木構造への書き込み}{19}}
+\@writefile{toc}{\contentsline {subsection}{\numberline {4.6.1}TreeEditor}{19}}
+\@writefile{toc}{\contentsline {section}{\numberline {4.7}木構造のマージ}{19}}
+\@writefile{toc}{\contentsline {subsection}{\numberline {4.7.1}Merger}{19}}
+\@writefile{toc}{\contentsline {chapter}{\numberline {第5章}結論}{20}}
 \@writefile{lof}{\addvspace {10\p@ }}
 \@writefile{lot}{\addvspace {10\p@ }}
-\newlabel{chapter:conclusion}{{5}{19}}
-\@writefile{toc}{\contentsline {section}{\numberline {5.1}まとめ}{19}}
-\@writefile{toc}{\contentsline {section}{\numberline {5.2}今後の課題}{19}}
+\newlabel{chapter:conclusion}{{5}{20}}
+\@writefile{toc}{\contentsline {section}{\numberline {5.1}まとめ}{20}}
+\@writefile{toc}{\contentsline {section}{\numberline {5.2}今後の課題}{20}}
 \citation{*}
 \bibstyle{junsrt}
 \bibdata{master_paper}
-\@writefile{toc}{\contentsline {chapter}{謝辞}{20}}
+\@writefile{toc}{\contentsline {chapter}{謝辞}{21}}
 \bibcite{dynamo}{1}
 \bibcite{bigtable}{2}
 \bibcite{seda:1}{3}
@@ -120,5 +126,5 @@
 \bibcite{shoshi:2010a}{5}
 \bibcite{shoshi:2011a}{6}
 \bibcite{shoshi:2011b}{7}
-\@writefile{toc}{\contentsline {chapter}{参考文献}{21}}
-\@writefile{toc}{\contentsline {chapter}{発表文献}{22}}
+\@writefile{toc}{\contentsline {chapter}{参考文献}{22}}
+\@writefile{toc}{\contentsline {chapter}{発表文献}{23}}
Binary file master_paper.dvi has changed
--- a/master_paper.lof	Tue Jan 22 23:28:03 2013 +0900
+++ b/master_paper.lof	Wed Jan 23 11:15:53 2013 +0900
@@ -23,5 +23,7 @@
 \contentsline {figure}{\numberline {3.14}{\ignorespaces 変更が衝突したが, 自然に解決できる場合}}{15}
 \contentsline {figure}{\numberline {3.15}{\ignorespaces 変更が衝突したが, 自然に解決できない場合}}{15}
 \contentsline {figure}{\numberline {3.16}{\ignorespaces プロパティグラフの例}}{16}
+\contentsline {figure}{\numberline {3.17}{\ignorespaces プロパティグラフのトラバース例}}{17}
+\contentsline {figure}{\numberline {3.18}{\ignorespaces システム全体の概要図}}{18}
 \addvspace {10\p@ }
 \addvspace {10\p@ }
--- a/master_paper.log	Tue Jan 22 23:28:03 2013 +0900
+++ b/master_paper.log	Wed Jan 23 11:15:53 2013 +0900
@@ -1,4 +1,4 @@
-This is e-pTeX, Version 3.1415926-p3.3-110825-2.4 (utf8.euc) (TeX Live 2012) (format=platex 2013.1.15)  22 JAN 2013 23:14
+This is e-pTeX, Version 3.1415926-p3.3-110825-2.4 (utf8.euc) (TeX Live 2012) (format=platex 2013.1.15)  23 JAN 2013 01:20
 entering extended mode
  \write18 enabled.
  %&-line parsing enabled.
@@ -98,6 +98,31 @@
 \Gin@req@height=\dimen127
 \Gin@req@width=\dimen128
 )
+(/usr/local/texlive/2012/texmf-dist/tex/latex/listings/listings.sty
+\lst@mode=\count95
+\lst@gtempboxa=\box50
+\lst@token=\toks19
+\lst@length=\count96
+\lst@currlwidth=\dimen129
+\lst@column=\count97
+\lst@pos=\count98
+\lst@lostspace=\dimen130
+\lst@width=\dimen131
+\lst@newlines=\count99
+\lst@lineno=\count100
+\lst@maxwidth=\dimen132
+
+(/usr/local/texlive/2012/texmf-dist/tex/latex/listings/lstmisc.sty
+File: lstmisc.sty 2007/02/22 1.4 (Carsten Heinz)
+\c@lstnumber=\count101
+\lst@skipnumbers=\count102
+\lst@framebox=\box51
+)
+(/usr/local/texlive/2012/texmf-dist/tex/latex/listings/listings.cfg
+File: listings.cfg 2007/02/22 1.4 listings configuration
+))
+Package: listings 2007/02/22 1.4 (Carsten Heinz)
+
 (/usr/local/texlive/2012/texmf-dist/tex/latex/comment/comment.sty
 \CommentStream=\write3
 
@@ -107,28 +132,26 @@
 )
 (/usr/local/texlive/2012/texmf-dist/tex/latex/tools/multicol.sty
 Package: multicol 2011/06/27 v1.7a multicolumn formatting (FMi)
-\c@tracingmulticols=\count95
-\mult@box=\box50
-\multicol@leftmargin=\dimen129
-\c@unbalance=\count96
-\c@collectmore=\count97
-\doublecol@number=\count98
-\multicoltolerance=\count99
-\multicolpretolerance=\count100
-\full@width=\dimen130
-\page@free=\dimen131
-\premulticols=\dimen132
-\postmulticols=\dimen133
+\c@tracingmulticols=\count103
+\mult@box=\box52
+\multicol@leftmargin=\dimen133
+\c@unbalance=\count104
+\c@collectmore=\count105
+\doublecol@number=\count106
+\multicoltolerance=\count107
+\multicolpretolerance=\count108
+\full@width=\dimen134
+\page@free=\dimen135
+\premulticols=\dimen136
+\postmulticols=\dimen137
 \multicolsep=\skip43
 \multicolbaselineskip=\skip44
-\partial@page=\box51
-\last@line=\box52
-\mult@rightbox=\box53
-\mult@grightbox=\box54
-\mult@gfirstbox=\box55
-\mult@firstbox=\box56
-\@tempa=\box57
-\@tempa=\box58
+\partial@page=\box53
+\last@line=\box54
+\mult@rightbox=\box55
+\mult@grightbox=\box56
+\mult@gfirstbox=\box57
+\mult@firstbox=\box58
 \@tempa=\box59
 \@tempa=\box60
 \@tempa=\box61
@@ -144,14 +167,16 @@
 \@tempa=\box71
 \@tempa=\box72
 \@tempa=\box73
-\c@columnbadness=\count101
-\c@finalcolumnbadness=\count102
-\last@try=\dimen134
-\multicolovershoot=\dimen135
-\multicolundershoot=\dimen136
-\mult@nat@firstbox=\box74
-\colbreak@box=\box75
-\multicol@sort@counter=\count103
+\@tempa=\box74
+\@tempa=\box75
+\c@columnbadness=\count109
+\c@finalcolumnbadness=\count110
+\last@try=\dimen138
+\multicolovershoot=\dimen139
+\multicolundershoot=\dimen140
+\mult@nat@firstbox=\box76
+\colbreak@box=\box77
+\multicol@sort@counter=\count111
 )
 \@indexfile=\write4
 \openout4 = `master_paper.idx'.
@@ -187,6 +212,7 @@
 LaTeX Font Info:    ... okay on input line 39.
 LaTeX Font Info:    Checking defaults for JT1/mc/m/n on input line 39.
 LaTeX Font Info:    ... okay on input line 39.
+\c@lstlisting=\count112
 LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <24.88> not available
 (Font)              Font shape `JT1/gt/m/n' tried instead on input line 41.
 LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <24.88> not available
@@ -373,24 +399,32 @@
 
 <./images/property_graph.pdf>
 File: images/emblem-bitmap.eps Graphic file (type eps)
- <images/emblem-bitmap.eps> [16]) (./chapter3.tex
-File: images/emblem-bitmap.eps Graphic file (type eps)
+ <images/emblem-bitmap.eps> [16]
+File: ./images/property_graph_traverse.pdf Graphic file (type pdf)
 
-<images/emblem-bitmap.eps> [17]
-第 4 章(18ページ)
-) (./conclusion.tex [18
+<./images/property_graph_traverse.pdf>
+File: images/emblem-bitmap.eps Graphic file (type eps)
+ <images/emblem-bitmap.eps> [17]
+File: ./images/basic_architecture.pdf Graphic file (type pdf)
+
+<./images/basic_architecture.pdf>) (./chapter3.tex
+File: images/emblem-bitmap.eps Graphic file (type eps)
+ <images/emblem-bitmap.eps>
+[18]
+第 4 章(19ページ)
+) (./conclusion.tex [19
 
 ]
-第 5 章(19ページ)
-) (./thanx.tex [19
+第 5 章(20ページ)
+) (./thanx.tex [20
 
-]) (./master_paper.bbl [20
+]) (./master_paper.bbl [21
 
-]) (./appendix.tex [21
+]) (./appendix.tex [22
 
 ])
 No file master_paper.ind.
-[22
+[23
 
 ] (./master_paper.aux)
 
@@ -398,12 +432,12 @@
 
  ) 
 Here is how much of TeX's memory you used:
- 1130 strings out of 494059
- 15721 string characters out of 3156205
- 74132 words of memory out of 3000000
- 4512 multiletter control sequences out of 15000+200000
+ 2318 strings out of 494059
+ 33372 string characters out of 3156205
+ 94226 words of memory out of 3000000
+ 5686 multiletter control sequences out of 15000+200000
  19379 words of font info for 75 fonts, out of 3000000 for 9000
  745 hyphenation exceptions out of 8191
- 33i,11n,24p,357b,428s stack positions out of 5000i,500n,10000p,200000b,50000s
+ 33i,11n,32p,357b,905s stack positions out of 5000i,500n,10000p,200000b,50000s
 
-Output written on master_paper.dvi (28 pages, 69408 bytes).
+Output written on master_paper.dvi (29 pages, 72776 bytes).
--- a/master_paper.lot	Tue Jan 22 23:28:03 2013 +0900
+++ b/master_paper.lot	Wed Jan 23 11:15:53 2013 +0900
@@ -2,5 +2,6 @@
 \addvspace {10\p@ }
 \contentsline {table}{\numberline {2.1}{\ignorespaces スケーラビリティ検証環境のマシン性能一覧}}{4}
 \addvspace {10\p@ }
+\contentsline {table}{\numberline {3.1}{\ignorespaces HTML5で実装される新機能}}{17}
 \addvspace {10\p@ }
 \addvspace {10\p@ }
Binary file master_paper.pdf has changed
--- a/master_paper.tex	Tue Jan 22 23:28:03 2013 +0900
+++ b/master_paper.tex	Wed Jan 23 11:15:53 2013 +0900
@@ -3,7 +3,7 @@
 \usepackage{here}
 \usepackage{ascmac}
 \usepackage[dvipdfmx]{graphicx}
-%\usepackage{mediabb}
+\usepackage{listings}
 \usepackage{comment}
 
 \input{dummy.tex} %% font
--- a/master_paper.toc	Tue Jan 22 23:28:03 2013 +0900
+++ b/master_paper.toc	Wed Jan 23 11:15:53 2013 +0900
@@ -30,24 +30,23 @@
 \contentsline {subsection}{\numberline {3.3.3}グラフデータベース}{16}
 \contentsline {subsubsection}{トラバース}{16}
 \contentsline {subsection}{\numberline {3.3.4}ブラウザサイドの実装}{17}
-\contentsline {section}{\numberline {3.4}全体の設計}{17}
-\contentsline {subsection}{\numberline {3.4.1}Push/Pullプロトコルの制定}{17}
-\contentsline {chapter}{\numberline {第4章}分散コンテンツマネージメントシステムの実装}{18}
-\contentsline {section}{\numberline {4.1}はじめに}{18}
-\contentsline {section}{\numberline {4.2}開発環境}{18}
-\contentsline {subsection}{\numberline {4.2.1}言語}{18}
-\contentsline {section}{\numberline {4.3}全体の構造}{18}
-\contentsline {section}{\numberline {4.4}木構造の検索}{18}
-\contentsline {subsection}{\numberline {4.4.1}Traverser}{18}
-\contentsline {section}{\numberline {4.5}木構造読み込み}{18}
-\contentsline {subsection}{\numberline {4.5.1}Journal}{18}
-\contentsline {section}{\numberline {4.6}木構造への書き込み}{18}
-\contentsline {subsection}{\numberline {4.6.1}TreeEditor}{18}
-\contentsline {section}{\numberline {4.7}木構造のマージ}{18}
-\contentsline {subsection}{\numberline {4.7.1}Merger}{18}
-\contentsline {chapter}{\numberline {第5章}結論}{19}
-\contentsline {section}{\numberline {5.1}まとめ}{19}
-\contentsline {section}{\numberline {5.2}今後の課題}{19}
-\contentsline {chapter}{謝辞}{20}
-\contentsline {chapter}{参考文献}{21}
-\contentsline {chapter}{発表文献}{22}
+\contentsline {section}{\numberline {3.4}全体の設計}{18}
+\contentsline {chapter}{\numberline {第4章}分散コンテンツマネージメントシステムの実装}{19}
+\contentsline {section}{\numberline {4.1}はじめに}{19}
+\contentsline {section}{\numberline {4.2}開発環境}{19}
+\contentsline {subsection}{\numberline {4.2.1}言語}{19}
+\contentsline {section}{\numberline {4.3}全体の構造}{19}
+\contentsline {section}{\numberline {4.4}木構造の検索}{19}
+\contentsline {subsection}{\numberline {4.4.1}Traverser}{19}
+\contentsline {section}{\numberline {4.5}木構造読み込み}{19}
+\contentsline {subsection}{\numberline {4.5.1}Journal}{19}
+\contentsline {section}{\numberline {4.6}木構造への書き込み}{19}
+\contentsline {subsection}{\numberline {4.6.1}TreeEditor}{19}
+\contentsline {section}{\numberline {4.7}木構造のマージ}{19}
+\contentsline {subsection}{\numberline {4.7.1}Merger}{19}
+\contentsline {chapter}{\numberline {第5章}結論}{20}
+\contentsline {section}{\numberline {5.1}まとめ}{20}
+\contentsline {section}{\numberline {5.2}今後の課題}{20}
+\contentsline {chapter}{謝辞}{21}
+\contentsline {chapter}{参考文献}{22}
+\contentsline {chapter}{発表文献}{23}