Papers/2013/shoshi-master-2013/paper: chapter2.tex comparison

comparison chapter2.tex @ 1:1ddca33b4d4e

added property_graph_traverse etc..

author	Shoshi TAMAKI
date	Wed, 23 Jan 2013 11:15:53 +0900
parents	bf82975fa7f5
children	83ddc73ce79b

comparison

equal deleted inserted replaced

-:bf82975fa7f5
+:1ddca33b4d4e
 \label{fig:distributed_and_normal_repository}
 \end{figure}
 \subsubsection{Push/Pull方式}
 Push/Pull方式とは, 分散レポジトリで利用されているレポジトリの結合方法の1つである.
-分散バージョン管理システムでのレポジトリはお互いにPush/Pullを用いて自身の更新を通知・受信することができる.
+分散バージョン管理システムでのレポジトリはお互いにPush/Pullを用いて自身の更新を通知・受信することができる.\\
 Pushとは, あるレポジトリが異なるレポジトリに自分の持つ更新を通知することで, Pullは, その逆の更新を他のレポジトリより受信することである.
-また, 異なる履歴を持つレポジトリ同士がPush/Pullを行う時お互いの更新がしょうとする可能性が考えられる, これらの問題はマージを用いることで解決する.
+また, 異なる履歴を持つレポジトリ同士がPush/Pullを行う時お互いの更新がしょうとする可能性が考えられる, これらの問題はマージを用いることで解決する.\\
 これを我々が提案した方法に当てはめると以下のようになる.
 \begin{itemize}
 \item{データの更新を受けたノードが一定時間ごとに, 他のノードに結果をPushする. 最新データは自分のみに書き込む.}
 \item{ノードは一定時間ごとに他のノードから更新をPullし, リクエストを受けたときは自信が保持するデータを利用する.}
 \end{center}
 \caption{変更が衝突しない場合}
 \label{fig:merge_sample_success}
 \end{figure}
-この状態は衝突が発生していない, なぜならPull元が編集されていないためである. 次に図\ref{fig:merge_sample_success}について考える.
+この状態は衝突が発生していない, なぜならPull元が編集されていないためである. 次に図\ref{fig:merge_sample_success}について考える.\\
-この場合, お互いの異なる履歴をもつ木構造がマージされる場合で変更が衝突している. しかし, 一方の木構造に対する変更が, もう一方の木構造の編集と衝突していない.
+この場合, お互いの異なる履歴をもつ木構造がマージされる場合で変更が衝突している. しかし, 一方の木構造に対する変更が, もう一方の木構造の編集と衝突していない.\\
 よってこの場合は自然にマージすることが可能である.
 \begin{figure}[!htbp]
 \begin{center}
 \includegraphics[width=95mm]{./images/merge_sample_success.pdf}
 \end{center}
 \caption{変更が衝突したが, 自然に解決できない場合}
 \label{fig:merge_sample_fail}
 \end{figure}
-衝突する場合は, マージ処理が必要である.マージ処理はお互いの変更点を検出し, 更新を自身の木構造に衝突を取り除いた状態で取り込むことである.
+衝突する場合は, マージ処理が必要である.マージ処理はお互いの変更点を検出し, 更新を自身の木構造に衝突を取り除いた状態で取り込むことである.\\
-分散レポジトリでは, お互いの更新点を検出する際に変更履歴を利用することで効率よくマージを実行することが出来ると考えられため, 我々のシステムでもマージの際に木構造に対しての更新履歴を参照できるようにする.
+分散レポジトリでは, お互いの更新点を検出する際に変更履歴を利用することで効率よくマージを実行することが出来ると考えられため, 我々のシステムでもマージの際に木構造に対しての更新履歴を参照できるようにする.\\
-マージには衝突を回避する他に, スケーラブルにするために工夫を加えることが出来る. なぜならば, 管理するコンテンツにおいて厳密なマージ処理が必要なコンテンツとそうでないコンテンツが存在するからである.
+マージには衝突を回避する他に, スケーラブルにするために工夫を加えることが出来る. なぜならば, 管理するコンテンツにおいて厳密なマージ処理が必要なコンテンツとそうでないコンテンツが存在するからである.\\
 そのため, 我々のシステムでは単純なマージアルゴリズムのほか, プログラマがマージアルゴリズムを記述できるようにできる仕組みを導入する.
 \subsection{グラフデータベース}
-グラフデータベースとはリレーショナルデータベースと異なり, グラフ構造を保存するデータベースである. 主な実装にNeo4j,OrientDB,InfiniteGraphがあるほか, TinkerPopという様々なグラフデータベースの実装の差異を吸収するためのプロジェクトも存在する.
+グラフデータベースとはリレーショナルデータベースと異なり, グラフ構造を保存するデータベースである. 主な実装にNeo4j,OrientDB,InfiniteGraphがあるほか, TinkerPopという様々なグラフデータベースの実装の差異を吸収するためのプロジェクトも存在する.\\
 グラフデータベースはプロパティグラフと呼ばれる種類のグラフを保持することが出来る. 主にソーシャルネットワークの人物関係を表すソーシャルグラフを表現するのに利用されるほか, ページランクのアルゴリズムにも利用される.
 \begin{figure}[!htbp]
 \begin{center}
 \includegraphics[width=100mm]{./images/property_graph.pdf}
 \caption{プロパティグラフの例}
 \label{fig:property_graph}
 \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を行う.
+前述した, スケーラブルにする方法,

Mercurial > hg > Papers > 2013 > shoshi-master-2013 > paper

comparison chapter2.tex @ 1:1ddca33b4d4e