Mercurial > hg > Papers > 2017 > suruga-sigos

changeset 5:bec6eb1e0297

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
sigos_3
author suruga
date Fri, 21 Apr 2017 00:30:14 +0900
parents 0c8bb16afb8d
children 8cf4c8681595
files paper/.DS_Store paper/README.txt paper/sigos.aux paper/sigos.dvi paper/sigos.log paper/sigos.pdf paper/sigos.tex
diffstat 7 files changed, 100 insertions(+), 89 deletions(-) [+]
line wrap: on
line diff
Binary file paper/.DS_Store has changed
--- a/paper/README.txt	Thu Apr 20 23:50:20 2017 +0900
+++ b/paper/README.txt	Fri Apr 21 00:30:14 2017 +0900
@@ -14,4 +14,10 @@
 
 Code \ref{src: "src"フォルダの中のコードのファイル名}で、文章中にコードの指定ができる。 
 
-\lstinputlisting[label=src:ファイル名, caption=Enqueue]{./src/ファイル名.拡張子}
\ No newline at end of file
+\lstinputlisting[label=src:ファイル名, caption=Enqueue]{./src/ファイル名.拡張子}
+
+-特殊文字は文字とローマ字巻き込まないように気をつける。
+ex.)
+ \textless-1,0,2,3\textgreater    ->  \textless -1,0,2,3 \textgreater
+
+! \textless に関係ない文字もくっついて、認識できなくてerror起こす。
--- a/paper/sigos.aux	Thu Apr 20 23:50:20 2017 +0900
+++ b/paper/sigos.aux	Fri Apr 21 00:30:14 2017 +0900
@@ -1,19 +1,20 @@
 \relax 
-\newlabel{fig:persistent_data_tree}{{1}{1}}
-\newlabel{fig:PushPopDemerit}{{2}{2}}
+\newlabel{fig:non_destructive_tree}{{1}{1}}
+\newlabel{fig:nodepath}{{2}{2}}
+\newlabel{fig:PushPopDemerit}{{3}{3}}
 \newlabel{table:Diffetential API}{{1}{3}}
-\newlabel{fig:EditDifferencialTree}{{3}{3}}
 \newlabel{fig:EditDifferencialTree}{{4}{3}}
+\newlabel{fig:EditDifferencialTree}{{5}{4}}
+\newlabel{fig:EditDifferencialTree}{{6}{4}}
 \citation{*}
 \bibstyle{ipsjunsrt}
 \bibdata{sigos}
 \bibcite{cerium}{1}
-\newlabel{fig:EditDifferencialTree}{{5}{4}}
-\newlabel{table:Diffetential API}{{2}{4}}
 \bibcite{alice}{2}
 \bibcite{segment}{3}
 \bibcite{opencl}{4}
 \bibcite{cuda}{5}
 \bibcite{gears}{6}
 \bibcite{cbc-lola}{7}
+\newlabel{table:Diffetential API}{{2}{5}}
 \gdef\ipsj@lastpage{5}
Binary file paper/sigos.dvi has changed
--- a/paper/sigos.log	Thu Apr 20 23:50:20 2017 +0900
+++ b/paper/sigos.log	Fri Apr 21 00:30:14 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 23:46
+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 00:29
 entering extended mode
  restricted \write18 enabled.
  %&-line parsing enabled.
@@ -171,84 +171,81 @@
 )
 \openout1 = `sigos.aux'.
 
-LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 40.
-LaTeX Font Info:    ... okay on input line 40.
-LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 40.
-LaTeX Font Info:    ... okay on input line 40.
-LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 40.
-LaTeX Font Info:    ... okay on input line 40.
-LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 40.
-LaTeX Font Info:    ... okay on input line 40.
-LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 40.
-LaTeX Font Info:    ... okay on input line 40.
-LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 40.
-LaTeX Font Info:    ... okay on input line 40.
-LaTeX Font Info:    Checking defaults for JY1/mc/m/n on input line 40.
-LaTeX Font Info:    ... okay on input line 40.
-LaTeX Font Info:    Checking defaults for JT1/mc/m/n on input line 40.
-LaTeX Font Info:    ... okay on input line 40.
+LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 36.
+LaTeX Font Info:    ... okay on input line 36.
+LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 36.
+LaTeX Font Info:    ... okay on input line 36.
+LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 36.
+LaTeX Font Info:    ... okay on input line 36.
+LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 36.
+LaTeX Font Info:    ... okay on input line 36.
+LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 36.
+LaTeX Font Info:    ... okay on input line 36.
+LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 36.
+LaTeX Font Info:    ... okay on input line 36.
+LaTeX Font Info:    Checking defaults for JY1/mc/m/n on input line 36.
+LaTeX Font Info:    ... okay on input line 36.
+LaTeX Font Info:    Checking defaults for JT1/mc/m/n on input line 36.
+LaTeX Font Info:    ... okay on input line 36.
 \c@lstlisting=\count113
 LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <14.4> not available
-(Font)              Font shape `JT1/gt/m/n' tried instead on input line 86.
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 82.
 LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <14.4> not available
-(Font)              Font shape `JY1/gt/m/n' tried instead on input line 86.
-LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <10.95> on input line 86.
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 82.
 LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <8> on input line 86.
-LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <12> not available
-(Font)              Font shape `JT1/gt/m/n' tried instead on input line 86.
-LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <12> not available
-(Font)              Font shape `JY1/gt/m/n' tried instead on input line 86.
+(Font)              <10.95> on input line 82.
 LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <7> on input line 86.
-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 95.
-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 95.
-
-
-LaTeX Warning: Reference `fig:non_destructive_tree' on page 1 undefined on inpu
-t line 95.
-
+(Font)              <8> on input line 82.
+LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <12> not available
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 82.
+LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <12> not available
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 82.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <7> on input line 82.
 File: ./pic/non_destructive_tree.pdf Graphic file (type pdf)
-<./pic/non_destructive_tree.pdf>
+ <./pic/non_destructive_tree.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 101.
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 96.
 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 101.
- [1
-
-
-]
-File: ./pic/PushPopDemerit.pdf Graphic file (type pdf)
- <./pic/PushPopDemerit.pdf> [2]
-
-LaTeX Warning: Reference `table:Differential API' on page 3 undefined on input 
-line 166.
-
-
-Overfull \hbox (0.80186pt too wide) in paragraph at lines 172--172
-[][]| 
- []
-
-
-Overfull \hbox (18.31381pt too wide) in paragraph at lines 171--176
- [][][] 
- []
-
-File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf)
-<./pic/EditDifferencialTree.pdf>
-LaTeX Font Info:    Try loading font information for OML+cmr on input line 194.
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 96.
+LaTeX Font Info:    Try loading font information for OML+cmr on input line 106.
 
 
 (/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 194.
+(Font)              Font shape `OML/cmm/m/it' tried instead on input line 106.
+ [1
+
+
+]
+File: ./pic/nodepath.pdf Graphic file (type pdf)
+
+<./pic/nodepath.pdf>
+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 131.
+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 131.
+File: ./pic/PushPopDemerit.pdf Graphic file (type pdf)
+ <./pic/PushPopDemerit.pdf> [2]
 
-Overfull \hbox (14.58702pt too wide) in paragraph at lines 194--195
+LaTeX Warning: Reference `table:Differential API' on page 3 undefined on input 
+line 172.
+
+
+Overfull \hbox (0.80186pt too wide) in paragraph at lines 178--178
+[][]| 
+ []
+
+
+Overfull \hbox (18.31381pt too wide) in paragraph at lines 177--182
+ [][][] 
+ []
+
+File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf)
+<./pic/EditDifferencialTree.pdf>
+Overfull \hbox (14.58702pt too wide) in paragraph at lines 200--201
 []\OT1/cmr/m/n/9 Editor \JY1/mc/m/n/9 が保持している木構造に対して \OT1/cmr/m/n
 /9 addNewChild(
  []
@@ -257,11 +254,11 @@
 <./pic/EditDifferencialTree.pdf> [3]
 File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf)
  <./pic/EditDifferencialTree.pdf>
-Overfull \hbox (18.31381pt too wide) in paragraph at lines 235--240
+Overfull \hbox (18.31381pt too wide) in paragraph at lines 241--246
  [][][] 
  []
 
-(./sigos.bbl [4]
+[4] (./sigos.bbl
 Overfull \hbox (58.50209pt too wide) in paragraph at lines 21--22
 []\OT1/cmr/m/n/9 : CUDA, https://developer.nvidia.com/category/zone/cuda-
  []
@@ -277,12 +274,12 @@
 
  ) 
 Here is how much of TeX's memory you used:
- 3079 strings out of 493693
- 43047 string characters out of 6149787
+ 3082 strings out of 493693
+ 43101 string characters out of 6149787
  145093 words of memory out of 5000000
- 6628 multiletter control sequences out of 15000+600000
+ 6630 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,943b,329s stack positions out of 5000i,500n,10000p,200000b,80000s
 
-Output written on sigos.dvi (5 pages, 31916 bytes).
+Output written on sigos.dvi (5 pages, 32724 bytes).
Binary file paper/sigos.pdf has changed
--- a/paper/sigos.tex	Thu Apr 20 23:50:20 2017 +0900
+++ b/paper/sigos.tex	Fri Apr 21 00:30:14 2017 +0900
@@ -1,12 +1,8 @@
-%\documentclass[a4j,12pt]{jreport}
 \documentclass[techrep]{ipsjpapers}
-%\documentclass{jarticle}
 \usepackage[dvipdfmx]{graphicx}
 \usepackage{url}
 \usepackage{listings,jlisting}
 \usepackage{enumitem}
-%\usepackage{comment}　
-%コメントアウト用package
 
 
 \lstset{
@@ -91,22 +87,32 @@
 \section{研究目的と背景}
 
 \section{非破壊的木構造データベースJungle}
-  Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装さ
-れている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。
+Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装されている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。
   %木のルートをAtomicに置き換えることで、木のアップデートを行う。変更前の木が残っているので、そのまま使用できる。変更されないノードは変更前と変更後のルートから共有されることになる。
 \begin{figure}[ht]
-        \begin{center}
-            \includegraphics[width=60mm]{./pic/non_destructive_tree.pdf}
-        \end{center}
+    \begin{center}
+        \includegraphics[width=60mm]{./pic/non_destructive_tree.pdf}
+    \end{center}
         \caption{非破壊的木構造の編集}
-        \label{fig:persistent_data_tree}
+         \label{fig:non_destructive_tree}
 \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 をサポートすることが可能になった。
+Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。既存の TreeMap では、一度 Index の複製を行い、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMap を使用し、それを用いて Index 実装を行なった。この TreeMap は、 Jungle と同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行なった際、前の版と最大限データを共有した新しい TreeMap を作成する。Jungle との違いは、木の回転処理が入ることである。これにより複数の版すべてに対応した Index をサポートすることが可能になった。
+\section{NodePath}
+Jungle では、木のノードの位置を NodePath クラスを使って表す。 NodePath クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 NodePath クラスを用いて \textless -1,0,2,3 \textgreater を表している際の例を(図\ref{fig:nodepath})に示す。
+ 
+  \begin{figure}[htpb]
+    \begin{center}
+        \includegraphics[width=60mm]{./pic/nodepath.pdf}
+    \end{center}
+        \caption{NodePath}
+        \label{fig:nodepath}
+\end{figure}
+ 
 \section{非破壊TreeMap}
 　Jungle の Index は、Functional Java の非破壊 TreeMap を用いて実装を行なっている。しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行処理速度が落ちるなど、実用的な性能を持っていなかった。そのため、Jungleの性能も、TreeMap 部分がネックとなっていた。その問題を解決するため、 Jungle で使用する非破壊 TreeMap を作成した。TreeMap は、Red Black Tree のアルゴリズムを用いている。RedBlackTreeとは二分木探索の一つで、以下の条件を満たした木のことである。
 \begin{itemize}
@@ -227,7 +233,7 @@
 　Jungle は木に編集を加えた際、ルートから編集を行う位置までのノードをコピーする。その為、木の編集の手間は木の大きさにも依存している。バランスの取れた木構造を構築することで、編集の手間をO(log n)にすることは可能だが、Default Jungle Tree の場合、ユーザーがPath を用いて、バランスを取りながら木を構築する必要がある。しかし、ユーザーが全ての木構造の形を把握し、バランスの取れた木を構築するのは困難である。そこで、自動で木のバランスを取り、最適な形の木構造を構築する機能を持つ Red Black Jungle Tree を実装した。バランスは、木の生成時に特定の Balance Key を決定し、それを使って行う。木のバランスを取るアルゴリズムは、前述した非破壊 TreeMap と同じものを使用する。しかし、木の編集を加えた際、木がどのようにバランスを取るか予想するのは困難であるため、木構造自体がデータを表現していない場合に限る。また、自身の木構造が、Balance Key  を使った Index と同じ働きを持つため、木のCommit 時に別途 Index を構築する必要が無い、といったメリットもある。
 
 \paragraph* {Red Black Jungle Tree の作成}
-　Red Black Jungle Tree を作成するため、Jungle に新しいAPIを実装した。(表)
+    Red Black Jungle Tree を作成するため、Jungle に新しいAPIを実装した。(表)
 
 \begin{table}[htb]
   \begin{center}
@@ -241,7 +247,8 @@
 \end{table}
 
 \paragraph* { NodePath の拡張}
- Red Black Jungle Tree は、ノードを追加・削除するたびに木のバランスが行われ、各ノードの Path が変わってしまう。その為、数字を使った NodePath では、編集を加える際、編集対象のノードの Path を毎回調べる必要がある。その問題を解決するために、NodePath を拡張した Red Black Tree Node Path を作成し、属性名 BalanceKey 属性値 value のペアでノードを指定できるようにした。 Red Black Jungle Node Path は、引数に String 型の BalanceKey と ByteBuffer 型の value を取る。
+    Red Black Jungle Tree は、ノードを追加・削除するたびに木のバランスが行われ、各ノードの Path が変わってしまう。その為、数字を使った NodePath では、編集を加える際、編集対象のノードの Path 
+を毎回調べる必要がある。その問題を解決するために、NodePath を拡張した Red Black Tree Node Path を作成し、属性名 BalanceKey 属性値 value のペアでノードを指定できるようにした。 Red Black Jungle Node Path は、引数に String 型の BalanceKey と ByteBuffer 型の value を取る。
  %サンプル要りますでしょうか
   Red Black Tree Node Path で指定できる属性名は、木の生成時に宣言した属性名しか使用できない。これは、Red Black Jungle Tree が木の生成時に宣言した属性名でソートされているからである。