Mercurial > hg > Papers > 2015 > tatsuki-sigos

changeset 2:0b021791e15c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
slide
author tatsuki
date Tue, 26 May 2015 04:28:22 +0900
parents d6b62893378f
children 082148d6bf7f
files OSSIGOS.xmind slide/images/JungleDataConvert.graffle slide/images/JungleDataConvert.jpg slide/images/TreePersonJungle.jpg slide/images/ref.graffle slide/images/ref.jpg slide/slide.html
diffstat 7 files changed, 469 insertions(+), 119 deletions(-) [+]
line wrap: on
line diff
Binary file OSSIGOS.xmind has changed
--- a/slide/images/JungleDataConvert.graffle	Sun May 24 17:54:28 2015 +0900
+++ b/slide/images/JungleDataConvert.graffle	Tue May 26 04:28:22 2015 +0900
@@ -53,7 +53,7 @@
 	<array>
 		<dict>
 			<key>Bounds</key>
-			<string>{{380, 271}, {449, 118}}</string>
+			<string>{{352, 273.5}, {449, 118}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -128,7 +128,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{301.5, 70}, {58, 46}}</string>
+			<string>{{293.5, 79.5}, {58, 46}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -215,8 +215,8 @@
 			<integer>46</integer>
 			<key>Points</key>
 			<array>
-				<string>{610.5, 113}</string>
-				<string>{711.5, 161}</string>
+				<string>{582.5, 115.5}</string>
+				<string>{683.5, 163.5}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -254,8 +254,8 @@
 			<integer>45</integer>
 			<key>Points</key>
 			<array>
-				<string>{610.5, 113}</string>
-				<string>{509.5, 161}</string>
+				<string>{582.5, 115.5}</string>
+				<string>{481.5, 163.5}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -279,7 +279,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{615.5, 188}, {191.99999999999997, 62}}</string>
+			<string>{{587.5, 190.5}, {191.99999999999997, 62}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -323,7 +323,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{615.5, 161}, {191.99999999999997, 27}}</string>
+			<string>{{587.5, 163.5}, {191.99999999999997, 27}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -367,7 +367,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{413.5, 188}, {191.99999999999997, 62}}</string>
+			<string>{{385.5, 190.5}, {191.99999999999997, 62}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -411,7 +411,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{413.5, 161}, {191.99999999999997, 27}}</string>
+			<string>{{385.5, 163.5}, {191.99999999999997, 27}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -455,7 +455,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{514.5, 51}, {191.99999999999997, 62}}</string>
+			<string>{{486.5, 53.5}, {191.99999999999997, 62}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -499,7 +499,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{514.5, 24}, {191.99999999999997, 27}}</string>
+			<string>{{486.5, 26.5}, {191.99999999999997, 27}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -550,8 +550,8 @@
 			<integer>63</integer>
 			<key>Points</key>
 			<array>
-				<string>{271.5, 142}</string>
-				<string>{380.5, 142}</string>
+				<string>{268, 142}</string>
+				<string>{377, 142}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -780,7 +780,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2015-05-24 07:52:55 +0000</string>
+	<string>2015-05-25 03:55:39 +0000</string>
 	<key>Modifier</key>
 	<string>sister_clown</string>
 	<key>NotesVisible</key>
@@ -818,6 +818,16 @@
 			<string>int</string>
 			<string>0</string>
 		</array>
+		<key>NSPrinter</key>
+		<array>
+			<string>coded</string>
+			<string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAlOU1ByaW50ZXIAhIQITlNPYmplY3QAhZKEhIQITlNTdHJpbmcBlIQBKx1jaW5uYW1vbi5jci5pZS51LXJ5dWt5dS5hYy5qcIaG</string>
+		</array>
+		<key>NSPrinterName</key>
+		<array>
+			<string>string</string>
+			<string>cinnamon.cr.ie.u-ryukyu.ac.jp</string>
+		</array>
 		<key>NSRightMargin</key>
 		<array>
 			<string>float</string>
@@ -856,7 +866,7 @@
 		<key>ExpandedCanvases</key>
 		<array/>
 		<key>Frame</key>
-		<string>{{517, -221}, {1225, 925}}</string>
+		<string>{{517, 0}, {1225, 925}}</string>
 		<key>ListView</key>
 		<true/>
 		<key>OutlineWidth</key>
Binary file slide/images/JungleDataConvert.jpg has changed
Binary file slide/images/TreePersonJungle.jpg has changed
--- a/slide/images/ref.graffle	Sun May 24 17:54:28 2015 +0900
+++ b/slide/images/ref.graffle	Tue May 26 04:28:22 2015 +0900
@@ -52,8 +52,47 @@
 	<key>GraphicsList</key>
 	<array>
 		<dict>
+			<key>AllowLabelDrop</key>
+			<false/>
+			<key>Class</key>
+			<string>LineGraphic</string>
+			<key>Head</key>
+			<dict>
+				<key>ID</key>
+				<integer>65</integer>
+			</dict>
+			<key>ID</key>
+			<integer>90</integer>
+			<key>Points</key>
+			<array>
+				<string>{761.75329589843727, 325.26571428571424}</string>
+				<string>{545.62666666666655, 479.56571428571414}</string>
+			</array>
+			<key>Style</key>
+			<dict>
+				<key>stroke</key>
+				<dict>
+					<key>HeadArrow</key>
+					<string>FilledArrow</string>
+					<key>Join</key>
+					<integer>0</integer>
+					<key>Legacy</key>
+					<true/>
+					<key>TailArrow</key>
+					<string>0</string>
+				</dict>
+			</dict>
+			<key>Tail</key>
+			<dict>
+				<key>ID</key>
+				<integer>76</integer>
+				<key>Info</key>
+				<integer>4</integer>
+			</dict>
+		</dict>
+		<dict>
 			<key>Bounds</key>
-			<string>{{558.99997329711914, 309.5}, {142, 82}}</string>
+			<string>{{552.99997329711914, 309.5}, {154, 82}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -118,7 +157,7 @@
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
 
 \f0\fs48 \cf0 o:1\'82\'f0\'8e\'67\'82\'c1\'82\'c4\
-\'8e\'51\'8f\'c6\'82\'b7\'82\'e9}</string>
+\'91\'8a\'8c\'dd\'8e\'51\'8f\'c6\'82\'b7\'82\'e9}</string>
 			</dict>
 			<key>TextRelativeArea</key>
 			<string>{{0, 0}, {1, 1}}</string>
@@ -1375,7 +1414,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2015-05-24 08:48:57 +0000</string>
+	<string>2015-05-24 10:09:48 +0000</string>
 	<key>Modifier</key>
 	<string>sister_clown</string>
 	<key>NotesVisible</key>
@@ -1413,6 +1452,16 @@
 			<string>int</string>
 			<string>0</string>
 		</array>
+		<key>NSPrinter</key>
+		<array>
+			<string>coded</string>
+			<string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAlOU1ByaW50ZXIAhIQITlNPYmplY3QAhZKEhIQITlNTdHJpbmcBlIQBKx1jaW5uYW1vbi5jci5pZS51LXJ5dWt5dS5hYy5qcIaG</string>
+		</array>
+		<key>NSPrinterName</key>
+		<array>
+			<string>string</string>
+			<string>cinnamon.cr.ie.u-ryukyu.ac.jp</string>
+		</array>
 		<key>NSRightMargin</key>
 		<array>
 			<string>float</string>
@@ -1451,7 +1500,7 @@
 		<key>ExpandedCanvases</key>
 		<array/>
 		<key>Frame</key>
-		<string>{{735, 132}, {1121, 925}}</string>
+		<string>{{735, 252}, {1121, 925}}</string>
 		<key>ListView</key>
 		<true/>
 		<key>OutlineWidth</key>
Binary file slide/images/ref.jpg has changed
--- a/slide/slide.html	Sun May 24 17:54:28 2015 +0900
+++ b/slide/slide.html	Tue May 26 04:28:22 2015 +0900
@@ -102,15 +102,12 @@
 </div>
 
 <div>
+<h1>知的構造を格納するためのデータベース</h1>
 <font size=5>
-<h1>知的構造を格納するためのデータベース</h1>
-<li>
-<li>我々が扱っている知識は木構造であることが多い
-<li>RDBに木構造の格納する際は表に変換を行う必要があり、スキーマが煩雑になる
-<li>木構造のデータを直接格納できるデータベースが望ましい
-</li>
-
-<p>そこで、当研究室では非破壊木構造データベースJungleの開発を行っている</p>
+<p>我々が扱っている知識は木構造であることが多い。</p>
+<p>RDBに格納するためには煩雑なデータ設計を行わなければならない</p>
+<p>データ設計等を行うこと無く木構造を格納できるデータベースが望ましい</p>
+<p>そこで当研究室では、非破壊的木構造データベースJungleの開発をおこなっている</p>
 <p>Jungleの表現力、機能の十分性検証、及び性能実証実験を行いたい</p>
 <p>そのために、Jungle上に組織の許認可管理アプリケーションmaTrixを実装した</p>
 </font>
@@ -118,36 +115,44 @@
 
 
 <div>
+<h1>組織の中の許認可管理アプリケーションmaTrix</h1>
 <font size=5>
-<h1>組織の中の許認可管理アプリケーションmaTrix</h1>
-<p>maTrixとは、株式会社Symphonyが開発しているアカウント管理、許諾判定システムである</p>
-<p>人、組織、役割等の木構造データとポリシーファイルを持つ</p>
-<p>データ同士が参照を行うことで組織構造を表現しており、組織構造は版管理されている</p>
+<p>人、組織、役割等の木構造データを保持しており</p>
+<p>木構造のデータはIdでお互いに参照を行っている</p>
+<p>許認可の判断はアクセスルールが記述されたポリシーファイルにそって行われる</p>
 <p>ポリシーファイルは主に、誰が (Target)、何を (Redource)、どうできるか(Action) の3つの要素で記述されている</p>
-<p>maTrixはアクセス要求に応じたポリシーファイルを参照することで許認可の判断を行う</p>
 </font>
 </div>
 
 
 <div>
+<h1>非破壊的木構造データベースJungle</h1>
 <font size=5>
-<h1>非破壊的木構造データベースJungle</h1>
 <p>Jungleは、複数の木の集合からなり、木はノードの集合で出来ている</p>
 <p>ノードは、自身の子供のリストと、属性名(Key)と属性値(Value)のデータの組を持つ</p>
 <p>Jungleは、非破壊的木構造であるため、一度作成した木を破壊することはない</p>
-<p>そのため、書き込みと読み込みを同時に行うことができる</p>
-<p>木の編集は、ルートから編集を行うノードまでコピーし、新しい木構造を作成することで行う</p>
-<p>その際、変更がないノードは共有する</p>
+</font>
+</div>
+
+
+
+
+<div>
+<h1>Jungleのデータの編集</h1>
+<font size=5>
+<p>新しい木構造を作成することでデータの編集を行う</p>
+<p>変更がないノードは共有する</p>
 <img src="./images/non_destructive_tree_edit2.png">
 <p>木の更新は、ルートノードをCASを用いて入れ替えることで行う</p>
+<p>データの上書きが無いため、読み込み中にロックをかける必要がない</p>
 </font>
 </div>
 
 
 
 <div>
+<h1>Jungle上でのmaTrixのデータ構造の表現</h1>
 <font size=5>
-<h1>Jungle上でのmaTrixのデータ構造の表現</h1>
 <p>Jugnleは木構造のデータをそのまま格納できるため、maTrixのデータを一部を除きそのまま格納できる</p>
 <p>maTrixの人物TreeをJungleに格納した図の一部を以下に示す</p>
 <iframe src="images/TreePersonJungle.html" width="1000" height="1000"></iframe>
@@ -158,57 +163,52 @@
 
 <div>
 <font size=5>
-<h1>Jungleで表現出来ないmaTrixのデータ構造</h1>
-<p>Jungleのノードは１つの属性名に対し、１つの属性値しか持つことが出来ない</p>
-<p>しかしmaTrixには、１つの属性名に対し、複数の属性名がペアになることがある</p>
-<p>例として、人が所属している組織のIdなどである</p>
-<p>なので、Jungleに格納できる形式に変換を行う必要がある</p>
-<p>データの変換は、データを複数個のノードに分割して格納することで行う</p>
-<p>以下にデータ変換の例を示す</p>
-<iframe src="images/JungleDataConvert.html" width="1800" height="1000"></iframe>
-</font>
-</div>
-
-
-<div>
-<font size=5>
-<h1>Jungle上での組織構造の表現</h1>
-<p>maTrixでは、複数の木構造がお互いに参照を行うことで組織構造を表現している</p>
-<p>人や組織はそれぞれ異なるIdを保持している(p:1など)</p>
-<p>参照はIdを用いて行う</p>
-<p>→ノードIDの検索機能が必要となる</p>
-<iframe src="images/ref.html" width="1800" height="1000"></iframe>
+<h1>Jungle上でのIdを使った木の相互参照</h1>
+<p>組織構造は複数の木構造を持ち、お互いのノード参照し合っている</p>
+<p>ex. 人物と組織は、idを用いてお互いのノードを参照する</p>
+<img src="./images/TreePersonJungle.png">
 </font>
 </div>
 
 
 <div>
+<h1>JungleのIndex</h1>
 <font size=5>
-<h1>Jungle上でのIdを使った木の相互参照</h1>
-<p>組織構造は複数の木構造を持ち、お互いのノード参照し合っている</p>
-<p>ex. 人物は、そのロールの木の中のノードを参照する</p>
-<img src="./images/TreePersonJungle.png">
-<p>ロールの木のノードにID属性を用意し、異なるID値を割りふる</p>
-<p>ノードIDにより参照を可能にする</p>
-<p>→ノードIDの検索機能が必要となる</p>
+<p>Jungleは過去のTreeを全て保持しているため、Treeのversion毎にIndexを持っている必要がある</p>
+<p>version毎にIndexを作るとメモリを多量使用してしまう</p>
+<p>過去のIndexとデータを共有するIndexを実装した</p>
+<p>複数のversionのIndexがあっても、データの差分しかメモリは使用されない</p>
+</font>
+</div>
+
+<div>
+<h1>非破壊TreeMapの実装</h1>
+<font size=5>
+<p>当初は、FunctionalJavaのTreeMapを使用してIndexの実装を行った</p>
+<p>FunctionalJavaにはバグがあり、性能が出なかった</p>
+<p>新しく非破壊TreeMapを実装した</p>
+<p>TreeMapのアルゴリズムには赤黒木を採用した</p>
+<p>その結果Jungleの性能は劇的に向上した</p>
 </font>
 </div>
 
 
+
 <div>
+<h1>木構造の親を取得するIndex</h1>
 <font size=5>
-<h1>maTrixでの許認可管理</h1>
-<p>maTrixを用いた許認可は、組織構造だけでは判断されない</p>
-<p>アクセス可能な時間等のルールは組織構造では表現できないからである</p>
-<p>そこでアクセスルールを記述したポリシーファイルを用いて許認可管理を行う</p>
+<p>Jungleは子から親への参照は存在しないため、自身の親を返すParentIndexの実装を行った</p>
+</font>
+</div>
+
+<div>
+<h1>許認可Queryの実装</h1>
+<font size=5>
+<p>maTrixを用いた許認可は、ポリシーファイルを参照し行われる</p>
 <p>ポリシーファイルには、subject(誰が)、Resource(何に対して)、Action(何が出来るか)を記述する</p>
-
-<p>以下に許認可管理の流れを示す</p>
-<ul>
-<li>Aさん(Subject)が、学科のノートPC(Resource)の借りる(Action)ために、maTrixに貸出許可を求める</li>
-<li>maTrixはリポジトリから、貸出許可を与えるかを判断するためのポリシーを取得する</li>
-<li>ポリシーファイルを元に、組織構造にアクセスを行い許可を与えるかどうかを判断する</li>
-</ul>
+<p>maTrixにおける許認可判断において、データに対するアクセスは、subject部分でデータアクセス関数を用いて行う</p>
+<p>maTrixには、データアクセス関数が実装されている</p>
+<p>Jungle上にmaTrixを実装するにあって、データアクセス関数の実装を行った</p>
 </font>
 </div>
 
@@ -216,40 +216,168 @@
 <div>
 <font size=5>
 <h1>Treeの検索</h1>
-<p>Jungleの木をたどる Traverserを使用する</p>
+<p>データアクセス関数を実装するため、Traverserに検索関数findを実装する</p>
 <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
 InterfaceTraverser traverser = tree.getTraverser(boolean useIndex);
 </div>
 <p>TraverserはTreeのNodeを走破する機能を持ったクラスです</p>
 <p>TreeからgetTraverserで取得可能</p>
-<p>第一引数で　検索を行う際にIndexを使用するかどうかを選択できる</p>
+<p>引数で検索を行う際にIndexを使用するかどうかを選択できる</p>
+</font>
+</div>
+
+<div>
+<font size=5>
+<h1>Treeの検索</h1>
 <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
- public Iterator&lt;TreeNode&gt; nodeIterator = traverser.find(Query query,String key, String searchValue);
+ public Iterator&lt;TreeNode&gt; find(Query query,String key, String searchValue);
+ </div>
+<p>findは以下のように定義されており、引数に</p>
+ <p>探索の条件を記述する関数boolean condition(TreeNode)を定義したQuery</p>
+ <p>Indexを使う検索に使用するString 属性名、String 属性値のペア</p>
+ <p>の3つを取る</p>
+ <p>条件に一致したNodeのIteratorを返す</p>
+<p>Iteratorは、複数の値から１つずつ順番に取得するためのinterfaceである</p>
+ <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
+ public interface Query {<br>
+ &nbsp;&nbsp boolean condition(TreeNode _node);<br>
+ }
+ </div>
+ </font>
+ </div>
+
+<div>
+<h1>findの使用例</h1>
+<font size=5>
+<div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
+InterfaceTraverser personTraverser = personTree.getTraverser(true);<br>
+Iterator&lt;TreeNode&gt; personIdpairIterator = personTraverser.find((TreeNode node) -&gt; { <br>
+    &nbsp;&nbsp;String personId = node.getAttributes().getString("Person-id");<br>
+    &nbsp;&nbsp;if (personId.equals("p:4"))<br>
+    &nbsp;&nbsp;&nbsp;&nbsp;return true;<br>
+    &nbsp;&nbsp;return false;<br>
+    }, "Person-id", "p:4");<br>
+<br>
+if (personIdpairIterator.hasNext())<br>
+&nbsp;&nbsp;TreeNode node = personIdpairIterator.next();
 </div>
-<p>第一引数には、探索の条件を記述する関数boolean condition(TreeNode)を定義したQueryを受け取る</p>
-<p>第二、第三引数の、String key、String valueはIndexの取得に使用する</p>
-<p>条件に一致したNodeのIteratorを返す</p>
+<ol>
+<li>Treeから木の探索を行うInterfaceTraverserを取得する</li>
+<li>findを実行する。引数には、検索条件が記述されたQuery、Person-Id、p:4を与える。(以下Queryの中の解説)</li>
+<li>nodeから属性名Person-idとペアになっている属性値を取得する</li>
+<li>返り値がp:4と一致するかどうかを調べる</li>
+<li>一致した場合trueを一致しなかった場合falseを返す</li>
+<li>帰ってきたIteratorからNodeを取得する</li>
+</ol>
+</font>
+</div>
+
+<div>
+<h1>maTrix上での許認可判断例(1)</h1>
+<font size=5>
+<p>情報工学科の学生にのみ貸し出されるPCをAさんが借りようとした場合の許認可判断</p>
+<ol>
+<li>Aさん(Subject)が、学科のノートPC(Resource)の借りる(Action)ために、maTrixに貸出許可を求める</li>
+<li>maTrixは、PCの貸出許可を与えるかを判断するためのポリシーファイルを参照する</li>
+<li>データにアクセスしAさんの役割を取得する</li>
+<li>Aさんが情報工学科の役割を持っていた場合貸出許可を与える</li>
+</ol>
+<p>maTrixは、3番目の処理で役割を取得する関数roleIdsを使用している</p>
+</font>
+</div>
+
+<div>
+<h1>役割を取得する関数</h1>
+<font size=5>
+<p>roleIdsは、人、組織の役割を取得する関数</p>
 <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
-public interface Query {<br>
-&nbsp;&nbsp boolean condition(TreeNode _node);<br>
-}
+public&nbsp;Iterator&lt;String&gt;&nbsp;searchPersonRoleIds(String&nbsp;version,&nbsp;String&nbsp;id,&nbsp;LinkedList&lt;String&gt;&nbsp;filterIds)&nbsp;
+</div>
+<p>roleIdsは引数に</p>
+<li>検索を行う組織構造のversion</li>
+<li>役割を取得したい人 or 組織のId</li>
+<li>検索対象を絞り込むために使用するフィルター</li>
+<p>の3つをとります</p>
+</font>
+</div>
 
-</div>
+<div>
+<h1>roleIdsのフィルター</h1>
+<font size=5>
+<p>人や組織は、複数の組織に所属することが可能</p>
+<p>組織に所属する際に役割が与えられる</p>
+<p>例. 人が大学に所属していると、「学生」や「教授」という役割が与えられる</p>
+<p>フィルターを使うと組織が与える役割で結果を絞り込める</p>
 </font>
 </div>
 
 
 <div>
+<h1>roleIdsのコード</h1>
 <font size=5>
-<h1>JungleのIndex</h1>
-<p>indexを実装することで探索計算量がO(logN)となる</p>
-<p>Jungleは過去のTreeを全て保持しているため、Treeのversion毎にIndexを持っている必要がある</p>
-<p>version毎にIndexを作るとメモリを多量消費してしまう</p>
-<p>FunctionalJavaのTreeMapを使用してIndexの実装を行った</p>
-<p>データの更新が行われた際に、一度作られたIndexに対して更新を行わず、新しいIndexを構築します</p>
-<p>その際、過去のIndexとデータを共有している</p>
-<p>複数のversionのIndexがあっても、データの差分しかメモリは消費されない</p>
-<p>メモリの使用量を抑えつつ複数のversionでIndexを保持できる</p>
+<div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
+&nbsp;&nbsp;JungleTree&nbsp;personTree&nbsp;=&nbsp;getTree(version,&nbsp;"Person");<br>
+</div>
+<p>maTrixは組織構造を版管理している</p>
+<p>getTree(String Version, String TreeName)は、VersionとTreeNameで指定された木を返す</p>
+<p>今回はroleIdsの引数で指定されたversionの人物Treeを取得している</p>
+</font>
+</div>
+
+<div>
+<h1>roleIdsのコード</h1>
+<font size=5>
+<div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
+&nbsp;&nbsp;InterfaceTraverser&nbsp;traverser&nbsp;=&nbsp;personTree.getTraverser(useIndex);<br>
+&nbsp;&nbsp;Iterator&lt;TreeNode&gt;&nbsp;personNodeIterator&nbsp;=&nbsp;traverser.find((TreeNode&nbsp;node)&nbsp;-&gt;&nbsp;{<br>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;String&nbsp;nodeId&nbsp;=&nbsp;node.getAttributes().getString("Person-id");<br>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(nodeId.equals(id))<br>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true;<br>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false;<br>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;},&nbsp;"Person-id",&nbsp;id);<br>
+</div>
+<p>getTreeで取得したTreeから、getTraverserで木を探索する機能を持ったTraverserを取得する</p>
+<p>取得したTraverser.findで、属性名 Person-id、属性値 引数で指定されたidのペアを持つノードのIteratorを検索する</p>
+</font>
+</div>
+
+
+<div>
+<h1>roleIdsのコード</h1>
+<font size=5>
+<div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
+TreeNode PersonNode = personNodeIterator.next();<br>
+TreeNode parentOrganizationsNode = PersonNode.getChildren().at(5).b();<br>
+Iterator&lt;TreeNode&gt; OrganizationMappedByRoleIterator = parentOrganizationsNode.getChildren().iterator();<br>
+</div>
+<p>findで取得したノードから、その人が持っている役割を持つノードのIteratorを取得する</p>
+<p>idを持っているノードの5番目の子供の下に役割のデータが格納されている</p>
+<p>なので、PersonNode.getChildren().at(5).b();で5番目の子供を取得</p>
+<p>その下に役割のデータが入ったノードがあるので、子供のiteratorを取得している</p>
+</font>
+</div>
+
+<div>
+<h1>roleIdsのコード</h1>
+<font size=5>
+<div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
+for&nbsp;(;&nbsp;OrganizationMappedByRoleIterator.hasNext();&nbsp;)&nbsp;{<br>
+  &nbsp;&nbsp;TreeNode&nbsp;OrganizationMappedByRole&nbsp;=&nbsp;OrganizationMappedByRoleIterator.next();<br>
+  &nbsp;&nbsp;TreeNode&nbsp;organizationRefIdNode&nbsp;=&nbsp;OrganizationMappedByRole.getChildren().at(0).b();<br>
+  &nbsp;&nbsp;String&nbsp;organizationRefId&nbsp;=&nbsp;organizationRefIdNode.getAttributes().getString("text-organizationRefId");<br>
+  &nbsp;&nbsp;if&nbsp;(!filterIds.contains(organizationRefId)&nbsp;&&&nbsp;!filterIds.isEmpty())<br>
+  &nbsp;&nbsp;&nbsp;&nbsp;continue;<br>
+
+  &nbsp;&nbsp;TreeNode&nbsp;roleRefIdNode&nbsp;=&nbsp;OrganizationMappedByRole.getChildren().at(1).b();<br>
+  &nbsp;&nbsp;return&nbsp;roleRefIdNode.getAttributes().getString("text-roleRefId");<br>
+}<br>
+</div>
+<p>役割のデータが入ったノードのiteratorをfor文で回して役割を取得する</p>
+<p>iteratorで取得できるノードの0番目の子供には役割を与える組織名が</p>
+<p>1番目のノードには与えられる役割名を保持している</p>
+<p>0番目の子供から組織名を取得し検索結果の絞込を行う</p>
+<p>その後1番目のノードから役割名を返す</p>
+<p>このfor文はroleIdsの返り値のiteratorで呼ばれます</p>
 </font>
 </div>
 
@@ -257,61 +385,224 @@
 <div>
 <font size=5>
 <h1>木構造の親を辿るQuery</h1>
-<p>maTrixで許認可を判断する際に、木構造の親を辿る検索を行う必要がある</p>
+<p>maTrixで許認可を判断する際に、木構造の親を辿る検索が必要になる場合がある</p>
 <p>以下に親を辿る検索を行う例を記す</p>
 <ol>
 <li>Aさんが、maTrixに工学部の学生にのみ貸出を行っている書籍の貸出許可を求める</li>
 <li>Aさんの所属している組織の情報を取得する(情報工学科)</li>
 <li>情報工学科の親の情報を取得する(工学部)</li>
-<li>Aさんは工学部に所属しているため本の貸出を許可する</li>
+<li>maTrixは、Aさんに工学部に所属しているため本の貸出を許可する</li>
 </ol>
-<p>TreeNodeでgetを行うと、親Nodeを返すParentIndexを実装した</p>
-<p>3番目の処理でParentIndexを使用する</p>
+<p>3番目の処理で親Nodeを返すParentIndexを使用する</p>
+</font>
+</div>
+
+
+<div>
+<h1>親を辿るQueryのコード</h1>
+<font size=5>
+<p>以下に親の取得を行う部分のコードを記述する</p>
+<p>idには工学部のidが、orgNodeにはAさんが所属している組織のidを持ったノードが入っている</p>
+<div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
+do {<br>
+&nbsp;&nbsp;String orgId = orgNode.getAttributes().getString("Organization-id");<br>
+&nbsp;&nbsp;if (id.equals(orgId))<br>
+&nbsp;&nbsp;&nbsp;&nbsp;return true;<br>
+&nbsp;&nbsp;parentOrgNodeOptional = parentIndex.get(orgNode);<br>
+&nbsp;&nbsp;if (parentOrgNodeOptional.isPresent())<br>
+&nbsp;&nbsp;&nbsp;&nbsp;orgNode = parentOrgNodeOptional.get();<br>
+&nbsp;&nbsp;else<br>
+&nbsp;&nbsp;&nbsp;&nbsp;return false;<br>
+}while(true);<br>
+</div>
+<ol>
+<li>orgNodeから組織のidを取得する</li>
+<li>idと取得した組織のidを比較する</li>
+<li>一致した場合はtrueを、しなかった場合はorgNodeの親を取得する</li>
+</ol>
+<p>以上の処理を取得できる親ノードが無くなるまで行う</p>
+</font>
+</div>
+
+<div>
+<h1>ベンチマーク</h1>
+<font size=5>
+<p>Jungle上にmaTrixの実装を行ったので、性能測定を行った</p>
+<p>測定はmongoDBとの比較とマルチプロセッサー上でのJungleの読み書き性能の2つを行った</p>
+<p>木構造をそのまま格納できること、属性名を指定することで属性値が取得できるなど、Jungleと似た特徴を持っているmongoDBを比較対象に選択した</p>
+</font>
+</div>
+
+<div>
+<h1>測定環境</h1>
+<font size=5>
+<p>今回の測定は以下の環境で行った</p>
+<li>Mac OS X 10.10.2</li>
+<li>2*2.66 GHz 6-Core Intel Xeon</li>
+<li>Memory 16GB 1333MHz DDR3</li>
+<li>java 1.8.0-45</li>
+<li>mongoDB 3.0.2</li>
+<li>javascript V8JavaScriptengine</li>
 </font>
 </div>
 
 
 <div>
+<h1>mongoDBとの比較</h1>
 <font size=5>
-<h1>maTrixのポリシーファイルのInterpreter</h1>
-<p>Jungle上での許認可判断は、組織構造とポリシーファイルを参照して行う</p>
-<p>引数にポリシーファイルと、誰が(subject)、何に(Resource)、どうするか(Action)を取る</p>
-<p>返り値は、許可(Permit) or 拒否(Deny)がある</p>
-<p>実際にJungleの上で許認可判断が行えるようになった</p>
+<p>1万人のデータをmongoDBとJungleに格納し、データの読み込みにかかる時間の測定を行った</p>
+<p>各DBに挿入するデータは以下のような構造を持つ</p>
+<div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
+{PersonId: 固有のPersonId ,roleRefIds:ランダムな役割Id}<br>
+</div>
+</font>
+</div>
+
+<div>
+<h1>mongoDBとの比較</h1>
+<font size=5>
+<p>mongoDBでのデータの読み込みは以下のように行った</p>
+<div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
+&nbsp;&nbsp;var personData = db.person1.find({PersonId:"p:9"}).next();<br>
+&nbsp;&nbsp;var roleId = personData.roleId<br>
+</div>
+<p>dbからpersonIdがp:9のuserを取得する</p>
+<p>取得したuserのroleIdを取得する</p>
+</font>
+</div>
+
+<div>
+<h1>mongoDBとの比較</h1>
+<font size=5>
+<p>Jungleのデータの読み込みは以下のように行った</p>
+<div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;">
+InterfaceTraverser traverser = tree.getTraverser(true);
+&nbsp;&nbsp;Iterator&lt;TreeNode&gt;&nbsp;it&nbsp;=&nbsp;traverser.find((TreeNode&nbsp;node)&nbsp;-&gt;&nbsp;{<br>
+    &nbsp;&nbsp;String&nbsp;nodeId&nbsp;=&nbsp;node.getAttributes().getString("Person-id");<br>
+    &nbsp;&nbsp;if&nbsp;(nodeId.equals("p:9"))<br>
+    &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true;<br>
+    &nbsp;&nbsp;return&nbsp;false;<br>
+    },&nbsp;"Person-id",&nbsp;"r:9");<br>
+if (it.hasNext()) {<br>
+  &nbsp;&nbsp;TreeNode targetNode = it.next();<br>
+    &nbsp;&nbsp;String targetRoleId = targetNode.getAttributes().getString("roleId");<br>
+}<br>
+</div><br>
+<p>TreeからpersonIdがp:9のノードを取得する</p>
+<p>取得したノードからroleIdを取得する</p>
 </font>
 </div>
 
 <div>
+<h1>mongoDBとの比較</h1>
+<embed src="images/mongoJungleperfomance.svg" width="700" height="700" align="left"/>
 <font size=5>
-<h1>maTrixのポリシーファイルのInterpreter</h1>
-<p>Jungle上での許認可判断は、組織構造とポリシーファイルを参照して行う</p>
-<p>引数にポリシーファイルと、誰が(subject)、何に(Resource)、どうするか(Action)を取る</p>
-<p>返り値は、許可(Permit) or 拒否(Deny)がある</p>
-<p>実際にJungleの上で許認可判断が行えるようになった</p>
+<br>
+<p>Jungleの方がmongoDBより高速で動いた理由として、<br>通信の有無が大きい</p>
+<p>mongoDBはMongoShellからデータベースにアクセスする際に<br>通信を行っている</p>
+<p>それに対しJungleは、通信を行わないため高速に動作する</p>
+<p>また、データへのアクセスもmongoDBは<br>ディスクにあるデータに対しmmapを用いて行う</p>
+<p>Jungleは初めからメモリにあるデータにアクセスする</p>
+<p>その部分も差が出た理由の１つである</p>
+<p>その結果JungleはmongoDBの約500倍の性能が出ている</p>
 </font>
 </div>
 
 <div>
+<h1>マルチプロセッサー上でのJungleの読み書き性能</h1>
 <font size=5>
-<h1>今後の課題</h1>
-<li>分散版の実装</li><br>
-<li>maTrix専用のデータ構造の定義</li>
-<p>今は、maTrixのデータ構造をそのまま格納しているため、Jungleに合ったデータ構造を設計する</p>
+<p>Jungleがマルチプロセッサ上で性能が出るか測定を行った</p>
+<p>複数スレッドからJungleに読み込みだけを行った場合と、1スレッドだけ書き込みを行い続け、残りのスレッドで読み込み行った場合で測定を行った。</p>
+<embed src="images/transactionPersecond.svg" width="700" height="700"align="left"/>
+<br>
+<p>Jungleでは、書き込みと読み込みを同時に行っても<br>性能低下はおこらなかった</p>
+<p>ハイパースレッディングに引っかかるまでは<br>リニアに性能が出ている</p>
+<p>書き込みと読み込みを同時に行った場合、<br>読み込みのCPUCOUNTが2の時だけ性能が出ていない</p>
+<p>これは、書き込みを連続で行っているため<br>読み込みと書き込みで競合が起きている</p>
+<p>しかし読み込みのスレッドが増えると<br>読み込みが優先されるので性能が出るようになっている</p>
+<p>読み込みと書き込み同時に行っている方が<br>CPUCOUNT11で性能上昇が止まっているのは<br>書き込みに1スレッド使用しているからである</p>
+</font>
+</div>
+
+
+<h1>考察</h1>
+<font size=5>
+<p>性能評価では、JungleのほうがMongoDBより高速に動いたが、全てのアプリケーションにおいてJungleの方が早いわけではない</p>
+<p>Jungleは、木構造の形と使われ方がアルゴリズム的に一致している場合に性能が出る</p>
+</font>
+</div>
+
+<div>
+<h1>Jungleに向いているアプリケーション</h1>
+<font size=5>
+<p>Jungleは、書き込み時の処理が木の大きさで変わる</p>
+<p>そのため、比較的小さな木にデータがたくさんあり、木の深い部分に対し変更があまり行われないアプリケーションが得意</p>
+<p>また、書き込みより読み込みを重視したDBであるため、読み込みが多いアプリケーションが性能が出る</p>
+<p>そのため、Jungleの上に構築するアプリケーション例としてBBSやWEBページなどがある</p>
+</font>
+</div>
+
+<div>
+<h1>Jungleに不向きなアプリケーション</h1>
+<font size=5>
+<p>逆に、１つの大きな木に対し変更が頻繁に行われるようなアプリケーションは向いていない</p>
+<p>そういった場合、木を分割して複数の小さな木にすることで性能を上げることは可能である</p>
+<p>しかし、木を分割するための設計手法がまだ無いので、設計手法の確立は今後の課題である</p>
 </font>
 </div>
 
 
 <div>
+<h1>今後の課題</h1>
 <font size=5>
-<h1>まとめ</h1>
-<p>Jungle上で実用アプリケーションを構築できた</p>
-<p>その際に必要だった機能をJungleに追加した</p>
-<li>Query</li>
-<li>Index</li>
-<p>実際にポリシーファイルを読み込み許認可を行えた</p>
+<p>1. RDBとの比較</p>
+<p>&nbsp;&nbsp;もともとmaTrixはRDB上で動いているアプリケーションなので、RDB版maTrixとの性能測定を行いたい</p>
+<p>2.データの書き出し部分の改良</p>
+<p>&nbsp;&nbsp;Jungleはデータをディスクに書き出すことが可能である</p>
+<p>&nbsp;&nbsp;書きだしたデータを読み込む機能もあるのでトラブルが発生し、Jungleが強制終了されても元の状態に復旧できる</p>
+<p>&nbsp;&nbsp;しかし、今の実装は、データの書き出しはcommit時に毎回行っているため書き出しが非効率的である</p>
+<p>&nbsp;&nbsp;できれば複数回分の変更をバッファリングしておいて一気に書き出しを行いたい</p>
+<p>&nbsp;&nbsp;また、ある値を行ったり来たりするような、書き出す必要が無いデータもあるため、書き出す部分の最適化を行う必要がある</p>
+</font>
+</div>
+
+<div>
+<h1>今後の課題</h1>
+<font size=5>
+<p>3.過去のデータの掃除</p>
+<p>&nbsp;&nbsp;Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを消費する</p>
+<p>&nbsp;&nbsp;ある程度のタイミングで過去のデータをメモリから掃除する必要がある</p>
+<p>&nbsp;&nbsp;しかし、データを掃除するタイミングは、Jungle上に実装するアプリケーションによって変わるため、自明ではない</p>
+<p>&nbsp;&nbsp;そこを含め、データを掃除するAPIの設計を行う必要がある</p>
+<p>4.分散環境でのmaTrixの構築</p>
+<p>&nbsp;&nbsp;Jungleはもともと分散データベースである</p>
+<p>&nbsp;&nbsp;分散版Jungle上にmaTrixを構築し、性能測定を行いたい</p>
 </font>
 </div>
 
+
+<div>
+<h1>今後の課題</h1>
+<font size=5>
+<p>5.設計手法の確立</p>
+<p>&nbsp;&nbsp;Jungleは木構造のデータをそのまま格納できる</p>
+<p>&nbsp;&nbsp;木のサイズが大きいと、データ更新の負荷が大きくなるため分割を行う必要がある</p>
+<p>&nbsp;&nbsp;分割を行った木同士の参照はIdを用いた間接的なものになる</p>
+<p>&nbsp;&nbsp;このようにJungleはRDBと異なり格納するデータの自由度が大きい</p>
+<p>&nbsp;&nbsp;なのでJungleの設計手法を確立させる必要がある</p>
+</font>
+</div>
+
+<div>
+<h1>まとめ</h1>
+<font size=5>
+<p>当研究室で開発している非破壊的木構造データベースJungle上に許認可管理アプリケーションmaTrixを実装した</p>
+<p>その際必要になった検索APIやIndexの実装を行った</p>
+<p>またFunctionalJavaは性能が出なかったので、非破壊TreeMapを自作した</p>
+<p>その結果Jungleの性能は劇的に上昇した</p>
+<p>性能測定ではmongoDBより高速に動き、マルチプロセッサ上でも並列に動作した</p>
+</font>
+</div>
 </div> <!-- presentation -->
 </body>
 </html>