Mercurial > hg > Papers > 2017 > tatsuki-master

--- a/abstract.tex	Wed Feb 01 09:14:57 2017 +0900
+++ b/abstract.tex	Fri Feb 03 09:50:28 2017 +0900
@@ -3,10 +3,10 @@
 木の変更は、変更を加えたノードから、ルートまでの経路の複製を行い、新しいルートをアトミックに入れ替えることでトランザクションを実現する。
 この方法により、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する。
 プログラムは、この木を内部のデータ構造として直接取り扱うことができる。
-また、汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。
+また、汎用の木構造を持つので、データベースを特に設計しなくてもあるがままの形で格納することが可能になっている。
 %しかし、木構造の形によっては、木の変更の手間が大きくなる・Indexの更新処理が極めて重いという面があった。

-本研究では、Jungleデータベースの大幅な改善を行い、既存のJungleとくらべて大幅な処理の高速化に成功した。
+本研究では、Jungleデータベースの改善を行い、既存のJungleとくらべて大幅な処理の高速化に成功した。
 また、Jungleを使用した例題アプリケーションを作成し、性能測定を行ったところ、木構造の形によって処理速度に差が出ることがわかった。

 \end{abstract}
--- a/introduciton.tex	Wed Feb 01 09:14:57 2017 +0900
+++ b/introduciton.tex	Fri Feb 03 09:50:28 2017 +0900
@@ -12,10 +12,11 @@
 プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。
 Jungleは分散構成も可能である。

-Jungleは、データの読み込みは高速に行える反面、木の変更の手間は木の形に依存しており、最悪の場合O(n)になってしまうという面があった。
-そこで、本研究では、Jungleの木の編集の高速化を行う。
-そのために、今までの汎用的な木ではなく、特定の形の木を格納することに特化した木を実装し、
-また、Indexの更新等に改善を行った。
+%Jungleは、データの読み込みは高速に行える反面、木の変更の手間は木の形に依存しており、最悪の場合O(n)になってしまうという面があった。
+Jungleは、読み込みは高速に行える反面、書き込みは木の形に依存しており、最悪の場合O(n)となってしまう。
+また、Indexの構築も大幅なネックとなっていた。
+そこで、本研究では、Jungleの木の構築・編集の改善を行う。
+そのために、今までの汎用的な木ではなく、特定の形の木を格納することに特化した木を実装し、Indexの更新等にも改善を行った。

 その後、実際にJungleを使用したアプリケーションを開発・運用する。
--- a/jungle.tex	Wed Feb 01 09:14:57 2017 +0900
+++ b/jungle.tex	Fri Feb 03 09:50:28 2017 +0900
@@ -19,7 +19,7 @@

 \section{破壊的木構造}
 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う。
-図\ref{fig:destractive}は破壊的木構造のにおけるデータ編集を表している。
+図\ref{fig:destractive}は破壊的木構造におけるデータ編集を表している。

 \begin{figure}[htpb]
   \begin{center}
@@ -71,6 +71,7 @@
 \end{center}
 \end{figure}

+\newpage
 \section{Either}
 Jungleは、失敗する可能性のある関数では返り値を{ \tt Either<A、B>}に包んで返す。
 AにはError、Bには処理に成功した際の返り値の型が入る。
@@ -113,7 +114,7 @@
 \section{JungleTree}
 Jungleは複数の木の集合で出来ている。
 Jungleの木は、変更を加えるためのEditor・検索を行うTraversreなどを保持しており、ユーザーはそれらを用いてデータにアクセスする。
-また、過去のバージョンの木に対するアクセスや、特定のノードのPathを検索する機能も持っている。
+過去のバージョンの木に対するアクセスや、特定のノードのPathを検索する機能も持っている。
 以下にJungleTreeクラスが提供しているAPI(表\ref{JungleTreeAPI})を記す
 \begin{table}[htb]
 \begin{center}
@@ -180,7 +181,7 @@
 JungleTree tree = jungle.getTreeByName("TreeName");
 TreeNode root = tree.getRootNode();
 Children children = root.getChildren();
-Either<Error,TreeNode> either = children.at(2);
+Either<Error,TreeNode> either = children.at(1);
 if (either.isA())
   return either.a();
 TreeNode child = either.b();
@@ -206,6 +207,8 @@
 Default Jungle Tree Editorは、Jungle Tree から、{\tt getTreeEditor()}を用いて取得する。
 表\ref{editor}にJungle Tree Editorインターフェースに定義されているAPIを記述する。

+\newpage
+
 \begin{table}[htb]
   \begin{center}
     \caption{Editorに実装されているAPI}
@@ -237,6 +240,8 @@

 以下に{\tt JungleTreeEditor}クラスを用いて、木の編集を行うサンプルコードを記述する。

+\newpage
+
 \begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode]
 JungleTreeEditor editor = tree.getTreeEditor();
 DefaultNodePath editNodePath = new DefaultNodePath();
@@ -293,7 +298,7 @@

 関数{\tt find}は、第一引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Query}を。
 第二、第三引数には、Indexを用いた絞込に使用する{\tt String key、String value}を取り、条件に一致したノードの{\tt Iterator}を返す。
-{\tt 関数find}の使用例を以下に記す
+{\tt 関数find}の使用例を以下に記す。

 \begin{lstlisting}[frame=lrbt,label=find,numbers=left]
 InterfaceTraverser traverser = tree.getTraverser(true);
@@ -321,11 +326,11 @@

 結果として、{\tt ryukyu}に所属する、名前が{\tt kanagawa}のデータを持つノードが取得できる。

+検索の際に使用する Index の実装については次節に記述する。

 \section{Indexの実装}
-前節で述べた、検索の際に使用するIndexの実装を行った。
 Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。
-よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要があった。
+よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。
 既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。
 その問題を解決するため、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。
 このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。
@@ -334,7 +339,7 @@
 以下にJungleにおけるIndexの型を記述する

 \begin{lstlisting}[frame=lrbt,label=index,numbers=left]
-TreeMap<String key,TreeMap<String attribute,List<TreeNode> node> index> indexMap
+TreeMap<String key,TreeMap<String attribute,List<TreeNode> nodeList> index> indexMap
 \end{lstlisting}

 JungleのIndexは{\tt IndexMap}内に保持されている。
--- a/jungleUpdatePoint.tex	Wed Feb 01 09:14:57 2017 +0900
+++ b/jungleUpdatePoint.tex	Fri Feb 03 09:50:28 2017 +0900
@@ -9,33 +9,30 @@
 Jungleの木は、Indexの更新をCommit時に Full Updateで行っている。
 そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。

-前の木との差分だけIndexを更新する機能をJungleに追加することで、この問題を解決した。
+Index の更新処理を高速に行えるようにするため、
+前の木との差分だけIndexを更新する機能を Jungle に追加した。


 \section{Differential Jungle Treeの実装}
 Jungleの木の変更の手間は木の形によって異なる。
 特に線形の木は、変更の手間がO(n)となってしまう。
-線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ
-しかし、PushPopは、木の並びが逆順になってしまう。
-なので、正順の木を構築する際には使用できない。
+線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ。
+しかし、PushPopは木の並びが逆順になってしまうため、正順の木を構築する際には使用できない。
 その問題を解決するために、Differential Jungle Treeの実装を行った。
 Differential Jungle Treeは、木のバージョンごとに、自身の末尾のノードを保持する。

-Differential Jungle Treeの木の編集は、Differential Jungle Tree Editor を使って行う。
-編集時、Differential Jungle Tree Editor は、自身が保持しているSub Treeに対して、破壊的な編集を行う。
-そして commit 時に、構築した Sub Tree を末尾ノードに Append することで木の編集を行う。
-また、データの検索時は、自身が保持している末尾ノード以下のSub Treeを検索対象から除外することで、木構造の版管理を行っている。
+Differential Jungle Tree は、木を破壊的に更新するが、編集・検索時に、末尾ノードを使用することで、過去の木の形を残すことが可能となっている。
+

 \section{Red Black Jungle Tree}
 Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。
 Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を構築できる。
 そこで、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。
 Red Black Jungle Tree は、生成時に木のバランスを取る際に使用する属性名(Balance Key)を指定する。
-ノードの挿入・削除時、Balance Keyを用いて木のバランスを取る・
+そして、ノードの挿入・削除時、Balance Keyを用いて木のバランスを取る・

 Red Black Jungle Tree の木の編集は、Red Black Jungle Tree Editorを用いて行う。
 ノードの挿入時に、木のバランスを取るための属性値が必要になるため、ノードと値の挿入を同時に行うAPIを実装した。

 Red Black Jungle Treeの検索は、Balance Key を用いた検索は極めて高速に行える。
 しかし用いなかった場合は、全探索を行うためO(n)になってしまう。
-
Binary file master_paper.pdf has changed