Mercurial > hg > Papers > 2011 > kazz-jssst
changeset 5:6a2f974ffe04
add abstract
author | kazz <kazz@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Sun, 07 Aug 2011 20:42:50 +0900 |
parents | 7d0cee5cc2de |
children | 86f7239450ef |
files | paper/kazz-jssst.tex |
diffstat | 1 files changed, 9 insertions(+), 27 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/kazz-jssst.tex Sun Aug 07 19:23:21 2011 +0900 +++ b/paper/kazz-jssst.tex Sun Aug 07 20:42:50 2011 +0900 @@ -27,24 +27,24 @@ \begin{document} % 論文のタイトル -\title{自己調整二分木の並列操作} +\title{DataSegment API を用いた分散フレームワークの設計} % 著者 % 和文論文の場合,姓と名の間には半角スペースを入れ, % 複数の著者の間は全角スペースで区切る % -\author{上田 和紀 +\author{赤嶺 一樹, 河野真治 % % ここにタイトル英訳 (英文の場合は和訳) を書く. % -\ejtitle{Concurrent Operations on Splay Trees.} +\ejtitle{Design of Distributed Application Framework with DataSegment API} % % ここに著者英文表記 (英文の場合は和文表記) および % 所属 (和文および英文) を書く. % 複数著者の所属はまとめてよい. % -\shozoku{Kazunori Ueda}{早稲田大学理工学部情報学科}% -{Dept.\ of Information and Computer Science, Waseda University} +\shozoku{Kazuki Akamine, Shinji Kono}{琉球大学理工学研究科情報工学専攻}% +{Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus} % % 出典情報は \shutten とすれば出力される. %\shutten @@ -59,16 +59,8 @@ % % 和文アブストラクト \Jabstract{% -SleatorとTarjanによる自己調整二分木(splay tree)に対して並 -列操作を可能にする操作アルゴリズムを提案する.提案するアル -ゴリズムは,同一の木に対する複数の更新・挿入・削除操作のパイプライン的並 -列実行を許し,かつ操作系列のスループット(単位時間内に処理可能な -操作の個数)とレスポンス(個々の操作の償却計算量 -(amortized complexity))を両立させることを目的としている. -スループットの最適性と挿入操作の対数的レスポンスについては -理論的結果を示す.削除操作は,木の形状に関する良い性質を保つ -にもかかわらず,Sleatorらの枠組みでは最適性が証明できない. -このことについても論じる.} + 本研究室では、分散フレームワークとして、 Linda を拡張した FederatedLinda を開発してきた。しかし、分散用の API として、 in/out/read だけでは足りないことが判明した。また、分散 KVS には、 read/write/update といった API があるが、同期する機構は備わっていないため、ゲームなどのリアルタイムプログラム用途にそのまま利用することはできない。\\ +そこで、 Linda の待ち合わせ可能な API と一般的な KVS の持つデータベースの API の中間になるような DataSegment API を設計する。本研究室では、その DataSegment API を用いた分散フレームワークを開発する。} % % 英文アブストラクト(大会論文には必要なし) % \Eabstract{} @@ -77,18 +69,8 @@ \section{はじめに} -自己調整二分木(スプレー木, splay tree) \cite{ST85}は,アクセスした節 -点に対して扁平化(splaying)操作(\ref{subsection:splaying}節) -を施すことにより,木の形状を動的に最適化す -る二分探索木の総称であり, -% -% さまざまなアク -% セスパターンに対して木の形状が動的に最適化してゆく二分木であり, -% -多くの強力な性質が成り立つことがわかっている.本論文では, -同一のスプレー木に対する複数の挿入削除等の操作 -のパイプライン的並列実行を可能にする方法を検討する.目標は,下記の要請を満たす -操作アルゴリズムを得ることである. + + % \begin{enumerate} \item ({\bf レスポンス}) 通常のスプレー木の操作と同様,