Binary file paper/sigos.dvi has changed

--- a/paper/sigos.log	Fri Apr 21 17:56:00 2017 +0900
+++ b/paper/sigos.log	Fri Apr 21 19:02:00 2017 +0900
@@ -1,4 +1,4 @@
-This is e-pTeX, Version 3.14159265-p3.7-160201-2.6 (utf8.euc) (TeX Live 2016) (preloaded format=platex 2017.4.10)  21 APR 2017 17:55
+This is e-pTeX, Version 3.14159265-p3.7-160201-2.6 (utf8.euc) (TeX Live 2016) (preloaded format=platex 2017.4.10)  21 APR 2017 19:00
 entering extended mode
  restricted \write18 enabled.
  %&-line parsing enabled.
@@ -215,17 +215,17 @@
 
 ]
 LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <9> not available
-(Font)              Font shape `JT1/gt/m/n' tried instead on input line 100.
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 101.
 LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <9> not available
-(Font)              Font shape `JY1/gt/m/n' tried instead on input line 100.
-LaTeX Font Info:    Try loading font information for OML+cmr on input line 103.
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 101.
+LaTeX Font Info:    Try loading font information for OML+cmr on input line 102.
 
 
 (/usr/local/texlive/2016/texmf-dist/tex/latex/base/omlcmr.fd
 File: omlcmr.fd 2014/09/29 v2.5h Standard LaTeX font definitions
 )
 LaTeX Font Info:    Font shape `OML/cmr/m/n' in size <9> not available
-(Font)              Font shape `OML/cmm/m/it' tried instead on input line 103.
+(Font)              Font shape `OML/cmm/m/it' tried instead on input line 102.
 File: ./pic/nodepath.pdf Graphic file (type pdf)
 
 <./pic/nodepath.pdf> [2]
@@ -233,27 +233,27 @@
  <./pic/PushPopDemerit.pdf>
 
 LaTeX Warning: Reference `table:Differential API' on page 3 undefined on input 
-line 168.
+line 169.
 
 
-Overfull \hbox (0.80186pt too wide) in paragraph at lines 174--174
+Overfull \hbox (0.80186pt too wide) in paragraph at lines 175--175
 [][]| 
  []
 
 
-Overfull \hbox (18.31381pt too wide) in paragraph at lines 173--178
+Overfull \hbox (18.31381pt too wide) in paragraph at lines 174--179
  [][][] 
  []
 
 [3]
 File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf)
  <./pic/EditDifferencialTree.pdf>
-Overfull \hbox (22.76657pt too wide) in paragraph at lines 188--189
+Overfull \hbox (22.76657pt too wide) in paragraph at lines 189--190
  [] 
  []
 
 
-Overfull \hbox (14.58702pt too wide) in paragraph at lines 196--197
+Overfull \hbox (14.58702pt too wide) in paragraph at lines 197--198
 []\OT1/cmr/m/n/9 Editor \JY1/mc/m/n/9 が保持している木構造に対して \OT1/cmr/m/n
 /9 addNewChild(
  []
@@ -262,7 +262,7 @@
 <./pic/Differential_Interface_Traverser.pdf> [4]
 File: ./pic/Tree_ver2.pdf Graphic file (type pdf)
  <./pic/Tree_ver2.pdf>
-Overfull \hbox (18.31381pt too wide) in paragraph at lines 234--239
+Overfull \hbox (18.31381pt too wide) in paragraph at lines 235--240
  [][][] 
  []
 
@@ -288,6 +288,6 @@
  6635 multiletter control sequences out of 15000+600000
  17185 words of font info for 66 fonts, out of 8000000 for 9000
  929 hyphenation exceptions out of 8191
- 30i,13n,49p,1602b,329s stack positions out of 5000i,500n,10000p,200000b,80000s
+ 30i,13n,49p,1614b,329s stack positions out of 5000i,500n,10000p,200000b,80000s
 
-Output written on sigos.dvi (6 pages, 40696 bytes).
+Output written on sigos.dvi (6 pages, 42080 bytes).

Binary file paper/sigos.pdf has changed

--- a/paper/sigos.tex	Fri Apr 21 17:56:00 2017 +0900
+++ b/paper/sigos.tex	Fri Apr 21 19:02:00 2017 +0900
@@ -72,7 +72,7 @@
 % 和文概要
 \begin{abstract}
 コンピュータの性能が向上するにつれ、ソフトウェアやアプリケーションを高速に動作させる需要が求められてきた。しかし、RDB
-では、同時書き込みの際に起こる競合を防ぐため、編集中にロックがかけられ、編集に時間がかかってしまう。また、不定形のデータ構造と表構造がミスマッチを起こしてしまう、インピーダンスミスマッチという問題がある。そこで当研究では、非破壊的木構造データベースJungleを開発している。非破壊的木構造により、読み込みと書き込みを同時に実行することができる。また、データベースの再設計を行わずに不定形のデータ構造を扱うことが可能である。本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるjungleの書き出し速度の測定方法の提案をする。
+では、同時書き込みの際に起こる競合を防ぐため、編集中にロックがかけられ、編集に時間がかかってしまう。また、不定形のデータ構造と表構造がミスマッチを起こしてしまう、インピーダンスミスマッチという問題がある。そこで当研究では、非破壊的木構造データベースJungleを開発している。非破壊的木構造により、読み込みと書き込みを同時に実行することができる。また、データベースの再設計を行わずに不定形のデータ構造を扱うことが可能である。本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるJungleの書き出し速度の測定方法の提案をする。
 \end{abstract}
 
 % 表題などの出力
@@ -83,7 +83,7 @@
 % Introduce
 \section{サービス利用に適したデータベース}
 CPUのマルチコア化により、コンピュータのCPU性能が格段に上がった。マルチコアCPUの普及により、一般的なコンピュータの性
-能も向上してきた。コンピュータの性能が向上するにつれ、ソフトウェアやアプリケーションを高速に動作させる需要が求められてきた。しかし、RDBでは、１一人のユーザーがデータを書き込んでいるとき、他のユーザーが書き込みをしてくることで起こるデータの競合を防ぐために、書き込みが終わるまでロックをかける必要がある。これにより、データの編集に時間がかかってしまうという問題がある。また、データのネスト構造を許さない第一正規系を要求するRDBの表構造は、Jsonなどの不定形のデータ構造とミスマッチを起こしてしまうという問題がある。この問題はデータベースのインピーダンスミスマッチと呼ばれている。不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理する方法が考えられるが、並列処理が中心となってきている今のアプリケーションには向いているとは言えない。これらの問題を解決するため、当研究室では、分散処理環境で動くことができるデータベースを目指して非破壊的木構造データベースJungleを開発している。木構造を扱えることによって、従来のRDBとは異なり、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、その木をそのままデータベースとして使用することも可能である。非破壊的木構造とは、データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。 これにより、データの書き込み中であっても、元のデータは変更されない為、読み込みも同時に行うことができる。Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。また、Index の構築も大幅なネックとなっていた。そこで、本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるjungleの書き出し速度の測定方法の提案をする。
+能も向上してきた。コンピュータの性能が向上するにつれ、分散に適したデータベースや分散データベースの速度を向上させる需要が求められてきた。しかし、RDBでは、１一人のユーザーがデータを書き込んでいるとき、他のユーザーが書き込みをしてくることで起こるデータの競合を防ぐために、書き込みが終わるまでロックをかける必要がある。これにより、データの編集に時間がかかってしまうという問題がある。また、データのネスト構造を許さない第一正規系を要求するRDBの表構造は、Jsonなどの不定形のデータ構造とミスマッチを起こしてしまうという問題がある。この問題はデータベースのインピーダンスミスマッチと呼ばれている。不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理する方法が考えられるが、並列処理が中心となってきている今のアプリケーションには向いているとは言えない。これらの問題を解決するため、当研究室では、分散処理環境で動くことができるデータベースを目指して非破壊的木構造データベースJungleを開発している。木構造を扱えることによって、従来のRDBとは異なり、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、その木をそのままデータベースとして使用することも可能である。非破壊的木構造とは、データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。 これにより、データの書き込み中であっても、元のデータは変更されない為、読み込みも同時に行うことができる。Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。また、Index の構築も大幅なネックとなっていた。そこで、本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるJungleの書き出し速度の測定方法の提案をする。
 \section{非破壊的木構造データベースJungle}
 Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装されている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。
   %木のルートをAtomicに置き換えることで、木のアップデートを行う。変更前の木が残っているので、そのまま使用できる。変更されないノードは変更前と変更後のルートから共有されることになる。
@@ -94,11 +94,10 @@
         \caption{非破壊的木構造の編集}
          \label{fig:non_destructive_tree}
 \end{figure}
-Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。Jungleでは、子供からの親へのポインタは持たないため、親から子への片方向の参照しかできない。通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。
+Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。また、親と子相互で参照しあうことができる破壊的木構造データベースとは違い、非破壊的木構造であるJungleは、親から子への片方向の参照しかできない。通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。
 
 \section{Jungleの構成要素}
-\subsection*{[Index]}
-Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。既存の TreeMap では、一度 Index の複製を行い、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMap を使用し、それを用いて Index 実装を行なった。この TreeMap は、 Jungle と同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行なった際、前の版と最大限データを共有した新しい TreeMap を作成する。Jungle との違いは、木の回転処理が入ることである。これにより複数の版すべてに対応した Index をサポートすることが可能になった。
+
 \subsection*{[NodePath]}
 Jungle では、木のノードの位置を NodePath クラスを使って表す。 NodePath クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 NodePath クラスを用いて \textless -1,0,2,3 \textgreater を表している際の例を(図\ref{fig:nodepath})に示す。
  
@@ -109,7 +108,9 @@
         \caption{NodePath}
         \label{fig:nodepath}
 \end{figure}
- 
+
+\subsection*{[Index]}
+Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。既存の TreeMap では、一度 Index の複製を行い、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMap を使用し、それを用いてIndexは実装されている。この TreeMap は、 Jungle と同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行なった際、前の版と最大限データを共有した新しい TreeMap を作成する。JungleでIndexを実装した場合と違いは、木の回転処理が入るという点である。これにより複数の版すべてに対応した Index をサポートすることが可能になった。
 \subsection*{[非破壊TreeMap]}
 Jungle の Index は、Functional Java の非破壊 TreeMap を用いて実装を行なっている。しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行処理速度が落ちるなど、実用的な性能を持っていなかった。そのため、Jungleの性能も、TreeMap 部分がネックとなっていた。その問題を解決するため、 Jungle で使用する非破壊 TreeMap を作成した。TreeMap は、Red Black Tree のアルゴリズムを用いている。RedBlackTreeとは二分木探索の一つで、以下の条件を満たした木のことである。
 \begin{itemize}
@@ -255,9 +256,12 @@
 
 
 \section{分散環境でのJungleDBの書き出し実験方法の提案}
-
+Jungleは分散環境で動くデータベースを目指して開発している。そこで、Jungleの実用性を示すために、分散環境での通信速度の測定を行う必要がある。今回、実験で分散構造としてJungleの動くノード16台を木構造に接続する。この木のルートノードをルートjungleと呼び、末端ノードをリーフjungleと呼ぶ。
+<図>
+まず、末端のJungleにUserが書き込みをし、Jungleからuserにレスポンスが返ってくるまでの時間を測定する。次に、Jungleの変更がルートのJungleにコピーされるまでの時間の測定方法を提案するJungle同士の接続には、当研究室で開発している分散フレームワークであるAliceを用いる。
 \section{まとめ}
-本研究では、始めに破壊的木構造データベースであるJungleについて説明を行い、次にJungleの性能を上げるために実装した点を挙げ、最後に分散環境での Jungle の書き出し実験の手法について述べた。実装した点は、まず Jungle の Index の Update を高速化させるために、前の版の Index と値を共有しながら Update を行う、差分 Update の実装を行なった。次に、線形の木を正順で構築する際、木の変更の手間が O(n) になる問題を解決するために、 Differential Jungle Tree の実装をした。 Differential Jungle Tree は、自身の末尾のノードの情報を保持している。この末尾ノードを使用して、木の編集や検索を行う。次に、自動的に木のバランスを行い、最適な形の木構造を構築する Red Black Jungle Tree を実装した。 Red Black Jungle Tree は、自身が Index を構築する Default Jungle Tree により、編集できる。また、ノードは、木のバランスによって Path が編集ごとに変わってしまうため、属性名と属性値のペアでノードを指定できる、 Red Black Jungle Tree Editor の実装を行なった。今後の課題として、Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを使用してしまう。ある程度の単位で過去のデータの掃除を行いたい。Jungleは、過去の木に対するアクセスをサポートしているため、データの掃除を行うタイミングが明確ではない。なので、メモリから追い出すタイミングを定義する必要がある。%また、Jungleのパフォーマンスを出すために、データを最適化する必要がある。最適な木構造はアプリケーションによって違うため、Jungleの設計手法を確立させる必要がある。
+本研究では、始めに破壊的木構造データベースであるJungleについて説明を行い、次にJungleの性能を上げるために実装した点を挙げ、最後に分散環境での Jungle の書き出し実験の手法について述べた。実装した点は、まず Jungle の Index の Update を高速化させるために、前の版の Index と値を共有しながら Update を行う、差分 Update の実装を行なった。次に、線形の木を正順で構築する際、木の変更の手間が O(n) になる問題を解決するために、 Differential Jungle Tree の実装をした。 Differential Jungle Tree は、自身の末尾のノードの情報を保持している。この末尾ノードを使用して、木の編集や検索を行う。次に、自動的に木のバランスを行い、最適な形の木構造を構築する Red Black Jungle Tree を実装した。 Red Black Jungle Tree は、自身が Index を構築する Default Jungle Tree により、編集できる。また、ノードは、木のバランスによって Path が編集ごとに変わってしまうため、属性名と属性値のペアでノードを指定できる、 Red Black Jungle Tree Editor の実装を行なった。
+今後の課題として、Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを使用してしまう。ある程度の単位で過去のデータの掃除を行いたい。Jungleは、過去の木に対するアクセスをサポートしているため、データの掃除を行うタイミングが明確ではない。なので、メモリから追い出すタイミングを定義する必要がある。
 
 
 %参考文献