# HG changeset patch # User suruga # Date 1492692399 -32400 # Node ID 07a31c08d082cf61a901107de24c3e142005cff6 # Parent 66a48dc3b319c9ea06691613c2c6a25d7c9b9ba6 add sigos_ver1_pdf diff -r 66a48dc3b319 -r 07a31c08d082 paper/.DS_Store Binary file paper/.DS_Store has changed diff -r 66a48dc3b319 -r 07a31c08d082 paper/sigos.aux --- a/paper/sigos.aux Thu Apr 20 21:24:15 2017 +0900 +++ b/paper/sigos.aux Thu Apr 20 21:46:39 2017 +0900 @@ -1,17 +1,7 @@ \relax +\newlabel{fig:persistent_data_tree}{{1}{1}} +\newlabel{fig:PushPopDemerit}{{2}{2}} +\newlabel{table:Diffetential API}{{1}{3}} +\newlabel{fig:EditDifferencialTree}{{3}{3}} +\newlabel{fig:EditDifferencialTree}{{4}{3}} \citation{cbc-lola} -\newlabel{fig:cbc_goto}{{1}{1}} -\newlabel{fig:persistent_data_tree}{{2}{1}} -\citation{*} -\bibstyle{ipsjunsrt} -\bibdata{sigos} -\bibcite{cbc-lola}{1} -\bibcite{cerium}{2} -\bibcite{alice}{3} -\bibcite{segment}{4} -\bibcite{opencl}{5} -\bibcite{cuda}{6} -\bibcite{gears}{7} -\newlabel{table:result}{{1}{2}} -\newlabel{fig:result}{{3}{2}} -\gdef\ipsj@lastpage{2} diff -r 66a48dc3b319 -r 07a31c08d082 paper/sigos.dvi Binary file paper/sigos.dvi has changed diff -r 66a48dc3b319 -r 07a31c08d082 paper/sigos.log --- a/paper/sigos.log Thu Apr 20 21:24:15 2017 +0900 +++ b/paper/sigos.log Thu Apr 20 21:46:39 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) 20 APR 2017 16:19 +This is e-pTeX, Version 3.14159265-p3.7-160201-2.6 (utf8.euc) (TeX Live 2016) (preloaded format=platex 2017.4.10) 20 APR 2017 21:39 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -192,41 +192,99 @@ (Font) Font shape `JY1/gt/m/n' tried instead on input line 84. LaTeX Font Info: External font `cmex10' loaded for size (Font) <7> on input line 84. -File: ./pic/cbc_goto.pdf Graphic file (type pdf) - <./pic/cbc_goto.pdf> -LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <7> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 106. -LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <7> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 106. 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 127. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 92. 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 127. -File: ./pic/persistent_date_tree.pdf Graphic file (type pdf) +(Font) Font shape `JY1/gt/m/n' tried instead on input line 92. + -<./pic/persistent_date_tree.pdf> -Overfull \hbox (22.76657pt too wide) in paragraph at lines 141--142 +LaTeX Warning: Reference `fig:non_destructive_tree' on page 1 undefined on inpu +t line 92. + +File: ./pic/non_destructive_tree.pdf Graphic file (type pdf) +<./pic/non_destructive_tree.pdf> +Overfull \hbox (22.76657pt too wide) in paragraph at lines 96--97 [] [] +LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <7> not available +(Font) Font shape `JT1/gt/m/n' tried instead on input line 98. +LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <7> not available +(Font) Font shape `JY1/gt/m/n' tried instead on input line 98. [1 ] -File: pic/twice_640.pdf Graphic file (type pdf) - (./sigos.bbl -Overfull \hbox (58.50209pt too wide) in paragraph at lines 25--26 -[]\OT1/cmr/m/n/9 : CUDA, https://developer.nvidia.com/category/zone/cuda- + +LaTeX Warning: Reference `fig:PushPopDemerit' on page 2 undefined on input line + 149. + +File: ./pic/PushPopDemerit.pdf Graphic file (type pdf) +<./pic/PushPopDemerit.pdf> + +LaTeX Warning: Reference `fig:PushPopDemerit' on page 2 undefined on input line + 157. + +[2] + +LaTeX Warning: Reference `table:Differential API' on page 3 undefined on input +line 163. + + +Overfull \hbox (367.5173pt too wide) in paragraph at lines 168--173 + [][][] + [] + + +LaTeX Warning: Reference `fig:EditDifferencialTree' on page 3 undefined on inpu +t line 180. + +File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf) +<./pic/EditDifferencialTree.pdf> +Overfull \hbox (20.23976pt too wide) in paragraph at lines 192--193 +[]\OT1/cmr/m/n/9 Editor \JY1/mc/m/n/9 が保持している木構造に対して \OT1/cmr/m/n +/9 addNewChild(<- [] -) [2] (./sigos.aux) ) + +LaTeX Warning: Reference `fig:PushPopDemerit' on page 3 undefined on input line + 198. + +File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf) +<./pic/EditDifferencialTree.pdf> +File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf) + <./pic/EditDifferencialTree.pdf> [3] + +LaTeX Warning: File `./pic/persistent_date_tree.pdf' not found on input line 25 +7. + + +I try without the new options + +! LaTeX Error: Cannot determine size of image (no BoundingBox). + +See the LaTeX manual or LaTeX Companion for explanation. +Type H for immediate help. + ... + +l.257 ...dth=80mm]{./pic/persistent_date_tree.pdf} + +? +! Emergency stop. + ... + +l.257 ...dth=80mm]{./pic/persistent_date_tree.pdf} + +Try typing to proceed. +If that doesn't work, type X to quit. + + Here is how much of TeX's memory you used: - 3066 strings out of 493693 - 42689 string characters out of 6149787 - 140093 words of memory out of 5000000 - 6613 multiletter control sequences out of 15000+600000 - 17648 words of font info for 68 fonts, out of 8000000 for 9000 + 3062 strings out of 493693 + 42951 string characters out of 6149787 + 145093 words of memory out of 5000000 + 6615 multiletter control sequences out of 15000+600000 + 17303 words of font info for 67 fonts, out of 8000000 for 9000 929 hyphenation exceptions out of 8191 - 30i,10n,49p,233b,385s stack positions out of 5000i,500n,10000p,200000b,80000s - -Output written on sigos.dvi (2 pages, 7680 bytes). + 30i,10n,49p,770b,377s stack positions out of 5000i,500n,10000p,200000b,80000s +Output written on sigos.dvi (3 pages, 22376 bytes). diff -r 66a48dc3b319 -r 07a31c08d082 paper/sigos.pdf Binary file paper/sigos.pdf has changed diff -r 66a48dc3b319 -r 07a31c08d082 paper/sigos.tex --- a/paper/sigos.tex Thu Apr 20 21:24:15 2017 +0900 +++ b/paper/sigos.tex Thu Apr 20 21:46:39 2017 +0900 @@ -89,18 +89,19 @@ \section{研究目的と背景} \section{非破壊的木構造データベースJungle} - Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装されている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。 + Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装さ +れている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。 %木のルートをAtomicに置き換えることで、木のアップデートを行う。変更前の木が残っているので、そのまま使用できる。変更されないノードは変更前と変更後のルートから共有されることになる。 - \begin{figure}[ht] +\begin{figure}[ht] \begin{center} \includegraphics[width=80mm]{./pic/non_destructive_tree.pdf} \end{center} \caption{非破壊的木構造の編集} \label{fig:persistent_data_tree} - \end{figure} - Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。Jungleでは、子供からの親へのポインタは持たないため、親から子への片方向の参照しかできない。 - 　通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。 - 　Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。 +\end{figure} +　Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。Jungleでは、子供からの親へのポインタは持たないため、親から子への片方向の参照しかできない。 +　通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。 +　Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。 \section{Index} 　Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。既存の TreeMap では、一度 Index の複製を行い、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMap を使用し、それを用いて Index 実装を行なった。この TreeMap は、 Jungle と同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行なった際、前の版と最大限データを共有した新しい TreeMap を作成する。Jungle との違いは、木の回転処理が入ることである。これにより複数の版すべてに対応した Index をサポートすることが可能になった。 @@ -146,7 +147,7 @@ \end{itemize} \section{Differential Jungle Treeの実装} - Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。そのため、木の編集の手間は、木構造の形によって異なる。特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。そこで、Jungleは、線形の木をO(1)で変更するPushPop の機能を持つ。PushPop とは、ルートノードの上に新しいルートノードを付け加える API である(図\ref{fig:PushPopDemerit} )。すると、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。 +　 Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。そのため、木の編集の手間は、木構造の形によって異なる。特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。そこで、Jungleは、線形の木をO(1)で変更するPushPop の機能を持つ。PushPop とは、ルートノードの上に新しいルートノードを付け加える API である(図\ref{fig:PushPopDemerit} )。すると、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。 \begin{figure}[ht] \begin{center} \includegraphics[width=70mm]{./pic/PushPopDemerit.pdf} @@ -154,13 +155,13 @@ \caption{PushPop} \label{fig:PushPopDemerit} \end{figure} - しかし、PushPopはルートノードを追加していくため、図\ref{fig:PushPopDemerit} のようにノードの並びが逆順になってしまう。Logなどの正順の木でなければデータを表現できない場合、木の編集時PushPop を使用できない。そこで、木の編集の手間を O(1) で、正順の木を構築できるDifferential Jungle Tree の実装を行なった。 Differential Jungle Tree は。木のバージョンごとに、自身の木の最後尾を表す末尾ノードを保持する。木の編集は、別途構築したSub Tree に対して破壊的に更新を行い、Commit 時に末尾のノードに Sub Tree を Append することで行う。この場合は木が破壊的に変更されているように見えるが、前の版の末端部分を超えてアクセスすることがなければ複数の版を同時に使用することができる。 +　しかし、PushPopはルートノードを追加していくため、図\ref{fig:PushPopDemerit} のようにノードの並びが逆順になってしまう。Logなどの正順の木でなければデータを表現できない場合、木の編集時PushPop を使用できない。そこで、木の編集の手間を O(1) で、正順の木を構築できるDifferential Jungle Tree の実装を行なった。 Differential Jungle Tree は。木のバージョンごとに、自身の木の最後尾を表す末尾ノードを保持する。木の編集は、別途構築したSub Tree に対して破壊的に更新を行い、Commit 時に末尾のノードに Sub Tree を Append することで行う。この場合は木が破壊的に変更されているように見えるが、前の版の末端部分を超えてアクセスすることがなければ複数の版を同時に使用することができる。 \paragraph* {Differential Tree Context} - Jungleの木はTreeContext というオブジェクトに自身の木の情報を保持している。Differential Jungle Tree では、現在の版の木構造の末尾ノードを保持することが可能な Differential Tree Context を作成した。 +　Jungleの木はTreeContext というオブジェクトに自身の木の情報を保持している。Differential Jungle Tree では、現在の版の木構造の末尾ノードを保持することが可能な Differential Tree Context を作成した。 \paragraph* {Differential Jungle Tree の作成} - Differential Jungle Tree を作成するためにJungle に、新しいAPIを実装した。(表\ref{table:Differential API}) + Differential Jungle Tree を作成するためにJungle に、新しいAPIを実装した。表(\ref{table:Differential API}) \begin{table}[ht] \begin{center}