平成１１年度 情報科学研究科 博士学位論文内容梗概

	井上博之

「分散Webキャッシュシステムの自律分散化手法と
  キャッシュの適応制御に関する研究」

分散WWWキャッシュシステムに、各キャッシュの内容と状態を把握するための ヒントサーバを導入したモデルを提案する。提案システムの実装・評価を行な うことで、キャッシュサーバの構成の変化に対応して構成情報の管理が自動化 され、システムが自律分散動作していることを示す。また、提案システムの キャッシュ全体のヒット率が従来システムを理想的な設定で動作させた場合と 同一になることを示す。

また、衛星ネットワークを使った分散キャッシュシステムでは衛星リンクの 遅延や帯域が問題となるが、利用者のアクセスパターンの分析やWWW オブジェクトの性質を考慮したキャッシュの適応制御方式を提案・評価し、 従来のシステムと比較してキャッシュのヒット率、取得時間が改善される ことを示す。

	小板隆浩

「NUMAマルチプロセッサのおけるスケジューリング方式に関する研究」

本研究の目的は，クラスタ型の NUMA 型マルチプロセッサを対象に，プロセッサ スケジューリング方式とページプレースメント方式の相互作用を考慮し，両方式 を協調的に動作させることにより，プロセスを従来方式よりも効率良く実行する 方策について明らかにすることである．

本論文では，クラスタ型の NUMA マルチプロセッサを対象として，ホームクラス タという概念をもとにプロセッサスケジューリング方式とページプレースメント 方式が協調的に動作する手法について提案する．両方式のいくつかの組み合わせ を考え，提案方式の有効性をシミュレーションにより評価する．シミュレーショ ン結果から，プロセッサスケジューリング方式とページプレースメント方式がホー ムクラスタを中心に協調動作する方式は，他の方式に比べ最も良い性能を示した． さらに，提案方式を従来の動的なプロセッサスケジューリング方式と比較し，我々 の提案方式がすべての負荷条件において，最も効率良くプロセスを実行し，平均 応答時間を改善することを示す．

	小林和真

「インターネットにおけるネットワーク構成技術の
　高機能化に関する研究」

まず，モバイルセキュリティの実現を目指したアプローチとして，モバイルコンピュータなどの移動体に認証情報(パスポート)を付加する認証モデルを提案する．このモデルを資源割当てプロトコルであるDHCP(Dynamic Host Configuration Protocol)に適用し，そのセキュリティ機能を高めたDHCPA(DHCP with Authentication)の実現について述べる．次に，認証を前提としたDHCP環境でのネットワークへのアクセス制御を実現するために，モバイル認証ゲートウェイであるDAG(DHCP Access control Gateway)を提案し，その実装と評価を行う．

地域IX(Internet eXchange)を実現する時に問題となる経路制御についての新たな解決アプローチとして，送信者の持つソースアドレスを利用した新たな経路制御手法であるSTAR(Source address oriented Traffic Arrangement Router)を提案し，実装とその評価を行う．次に，この手法を含んだ地域インターネット構築モデルを定め，これを岡山県が推進する岡山情報ハイウェイ構想に適用し，構築モデルの有効性を検証する．本研究で確立した地域ネットワーク構築モデル，地域IX構築モデルは，地方自治体におけるネットワーク構築のモデルとして認知されており，地域ネットワーク構築に適用することで，域内の通信基盤を先進的な都市部なみに向上させることが可能となる．

	普天間智

「Internetにおける広域な動画像通信環境の構築に関する研究」

基盤技術の進歩，計算機の性能向上，圧縮技術の確立などにより Internet上で動画像通信を行う環境は整いつつあるが， 広域での動画像通信を実現するには，アプリケーションにおける格差， ネットワーク帯域における格差，ネットワーク帯域確保の困難さ， サーバマシン処理能力の限界を考慮した通信モデルや情報発信モデルを 構築する必要がある．本発表では，広域な動画通信環境実現の視点から 行った2つの研究について述べる．

まず，ユーザのInternet利用環境の違いを吸収することで広域な ビデオ会議を実現する研究として，アプリケーションプロトコルと データフォーマットを相互変換し，アプリケーションにおける格差， ネットワーク帯域における格差を吸収するアプリケーションゲートウェイ PRISM（PRactical Inter-videoconferencing System Model）を使った 通信モデルを提案する．
PRISMの設計と実装，および評価実験について述べ， PRISMがユーザの利用環境を吸収し，広域な動画像通信を実現できる プラットホームであることを示す．

次に，Internet上で広域に動画像情報を発信する研究として， サーバマシンの処理能力の限界，ユーザのInternet利用環境の違い， 帯域確保の困難さを考慮して設計した，全国高等学校野球選手権大会の Internet中継システムについて述べる．
そして，設計したシステムを実際に運用して得られたアクセス傾向に ついて説明し，大規模な情報発信を達成でき，設計したシステムが Internetのマスメディア化に有効であることを示す．

	権娟大

「Computational Complexity of Finding Correlated Items
　in Market Basket Databases」

また，サポートに関するいくつかの弱点が指摘されている．本研究ではサポー トに代わるいくつかの尺度を提案する．これらの尺度のもとで，あるアイテム 集合中のアイテム間の関連性を示す値が与えられた閾値を越えるならば，その アイテム集合を高共起度集合と呼ぶ．高共起度集合問題を「与えられた大きさ をもつ高共起度集合が存在するか否か」を判定する問題として形式的に定義し， どの尺度に対してもこの問題がNP完全であることを示す．さらに，すべての高 共起度集合が効率良く求められるデータベースの部分クラスを提案する．

	相良かおる

「英文契約書の電子化文書に関する研究」

　(a)　「語の基本形」とは, 対象となる語から, 語形を変化 させる屈折接辞を取り除いた「語幹」から, さらに語の 品詞を変える派生接辞を取り除いたものをいう.
「語の基本形」を導入することで, 本研究で作成した技術 取引契約に関する用語辞書に含まれる5,804種の語を 2,854語にまとめることができる.

　(b)契約書には, 条項ごとに内容がまとめられているという 特徴がある.そこで, 索引語を抽出する際に使われる TF.IDF法を用いて, 前述の書式集に含まれる34条項を 対象に重要語を求め, 出版社の異なる書式集から抽出 したデータをもとに条項名の推定を行った.
元の語による重要語を用いた場合は79%の正しさで 推定ができた.さらに, 「語の基本形」を導入することで, 86%の正しさで推定できることを確認した.

　(c)語の統語関係を意識した名詞間の類似度の定義を行い, ファジイ類似関係行列を使って, 書式集に含まれる894種の 名詞99個の同値類を求め, 人手により見直し, 34種の 類義語句データを作成した.

　（２）長文で複雑な契約書の条文から統語構造を抽出する 手法の提案を行い, 試作プログラムを作成した. ここでの「統語構造の抽出」とは, 修飾−被修飾関係, 主部・述部などを独立に抽出することをいう.

	石水隆

「BSP モデル上の並列アルゴリズムに関する研究」

本論文では, BSP(Bulk-Synchronous Parallel) モデルおよび BSP* モデル上で， 選択問題を解く並列アルゴリズムおよび全最近点問題を解く並列アルゴリズムを 提案する. BSP モデルおよび BSP* モデルはバリア同期という緩い同期に基づ いた並列計算のためのモデルであり，非同期式並列計算モデルと呼ばれる．これ らのモデルでは，具体的な通信の特性などは同期周期 L, 通信命令実行時間 g， 通信パケットサイズ B といったパラメタにより抽象化されている．

	高崎智也

「順序回路の無閉路構造に基づく部分スキャン設計ならびに
  高位合成に関する研究」

まず，順序回路の無閉路構造の一つである，内部平衡構造に基づく 拡張部分スキャン設計法を提案する．この拡張部分スキャン設計に おいて，スキャン化にともなう面積オーバヘッドを小さくするための， フリップフロップと信号線を選択する方法を述べる．ベンチマーク 回路に対する実験結果では，提案した拡張部分スキャン設計が小さい 面積オーバーヘッドで実現できることを示す．

さらに，無閉路構造に基づく部分スキャン設計のためのデータパスの テスト容易化高位合成法を提案する．本合成法は，テスト容易性を 考慮しない従来手法と比較して，リソース数(面積)を増やすことなく， 無閉路化のためのスキャンレジスタ数の小さいレジスタ転送レベルの データパスを合成することができる．

	花川典子

「Project Management Methods Adaptable
　to Software Development Paradigm Shifts」

The other method is a new model for estimating development periods, whennew development environments and techniques are used in projects. The model considers productivity's variation which is caused by developers' learning. Productivity increases as an activity progresses, because the developers become more familiar with the new environments and technologies over time.

The thesis also presents a prototype tool based on the proposed method and model. The prototype can be used to establish more accurate plans at the beginning of software development projects. The established plans in the prototype define a more exact sequence of development phases and milestones. Moreover, the plans show development periods which are influenced by variation of productivity by developers' learning.

	藤尾正和

「Japanese Dependency Structure Analysis based on a Lexicalized 
  Statistic Model」

If we want to achieve a higher rate of accuracy, it is necessary to use much information. However, it causes a problem of increasing complexities of models and the effect of sparse-data problem is also unevitable.

The basic statistical model is not so much complex as other statitistical parsers in the literature of a computational statistical parser. We stick to a statistical model of simple setting aiming at an easy implementation and efficiency of parsing. Instead, we address the problem of subordinate clauses and coordinate structures, which are among the major causes of difficulty in the syntactic analysis of a Japanese sentence. And we propose statistical partial parse and redundant parse methods.

This dissertation discusses on four topics on dependency analysis of a Japanese sentence.

　1. How to use stochastic information of surface clues to syntactic disambiguation.
　2. How to achieve higher precision or recall based on a basic statistical model.
　3. How to acquire and use scope embedding preference of subordinate clauses, for
　 　 syntactic disambiguation.
　4. How to integrate coordinate structure dection and syntactic disambiguation.

	堀井千夏

「ディジタル図書館のための概念情報を用いた
　文献検索手法に関する研究」

文書特徴量の抽出処理としては，概念の出現頻度分布から主題の内容を求め，単 語の出現頻度分布から主題の強調度を求める．両者を用いて文書の特徴量を算 出し，これを主題として検索に用いている．

	堀謙太

「コンピュータを用いた遺物復元における接合箇所検出と
  破片輪郭の表現」

本発表ではまず，接合箇所検出において，特定の対象に対する依存性を排除する方法について議論する．特定の対象に依存しない形状表現としては、曲線不変量のような形状不変量が挙げられる．曲線不変量は従来，接合箇所検出のような，部分的な形状の照合には不向きであるとされてきた．しかし，破片輪郭全体を曲線不変量で表現するのではなく，あらかじめ破片輪郭をいくつかのセグメントに分割し，各セグメントの形状表現に曲線不変量を適用することで，遺物破片輪郭の部分的な形状の比較に適用することが可能となる．実験により，考古学の遺物復元のような，特定の形状に依存しない接合箇所検出に対する曲線不変量の適用の有効性を示す．

さらに，特定の形状に対する依存性を持たず，かつ，破片輪郭の部分的形状を柔軟に表現する破片輪郭情報の表現モデル，および，そのモデルを使用した接合箇所検出法について議論する． 破片輪郭の表現モデルとしては，グラフモデルに階層構造を付加した，いわゆる階層グラフモデルを適用する．接合箇所検出の方法としては，階層グラフモデルの階層構造に着目し，幅優先で接合箇所を探索するアプローチを使用した．遺物破片の2次元輪郭に対する実験結果から，階層構造の適用により，輪郭分割において細かいパラメータ調整が不要な接合箇所検出の実現が可能であることを示す．

	守屋宣

「無待機分散アルゴリズムに関する研究」

(1)フェーズ内システムとよばれる同期式共有メモリシステムにおいて, 時計 合わせ問題に対する無待機分散アルゴリズムについて考察する. ここで時計合 わせ問題とは, システム内のプロセスが保持する局所時計の値を一致させる問 題である. まず, フェーズ内システム上の無待機時計合わせアルゴリズムにお いて, 同期時間とよばれる評価尺度の下界がプロセス数nに対しn-2であること を示す. 次に, 同期時間がオーダ的に最適な無待機時計合わせアルゴリズムを 提案する. また, 一時故障耐性を意味する自己安定性とよばれる性質を有し, さらに空間複雑度が有界であるような, 同期時間がオーダ的に最適な無待機時 計合わせアルゴリズムの提案も行う.

(2)同期式メッセージパッシングシステム上に線形化可能性を保証する共有オ ブジェクトを実現する無待機分散アルゴリズムの考察を行う. まず, 放送モデ ルとして信頼放送モデル, 無信頼放送モデルを導入し, 局所時計モデルとして 非同期時計モデル, u-同期時計モデルを導入する. そして, 放送モデル, 局所 時計モデルのすべての組合せに対してread/write-レジスタを無待機に実現す るアルゴリズムを提案する. また, 信頼放送モデル上で先に挙げた２種類の局 所時計モデルに対して一般オブジェクトを実現する無待機分散アルゴリズムも 提案する.

	安室喜弘

「運動の制約を考慮した手の3次元CGモデリングに関する研究」

このモデルは手の構造を表す関節を持った骨格構造とその上を覆う皮膚モデル とによって構成される。指などの関節の角度の設定によって手の基本的な姿勢 を作り、手の骨格の形状と関節間の角度の情報を用いて皮膚表面の形状を決定 しレンダリングを行う．

骨格構造を用いて姿勢を生成する機構には，人間が手を動かす時の指の関節の 間、及び指と指との間の姿勢の相互関係を制約としてモデリングし採り入れる。 制約を表現するために用いるパラメータは実際の手の動きを計測することによ り決定した。皮膚モデルには手の実計測により得られたレンジデータをもとに 作成し，実写のテクスチャとシェーディングをブレンドすることにより手の皮 膚の質感を自然に再現する。

本手法により、手の3次元形状を作り出す時のパラメータ数を削減し，非常に 煩雑とされる姿勢データシーケンスの作成作業を軽減できるだけでなく、容易 に自然な姿勢や運動を作り出すことが可能になる。最後に，提案モデリング手 法の有効性をCGアニメーションを作成することによって示す。

	唐元生

「Optimality and Ruling-Out Conditions and Their Evaluation Methods
for Soft-Decision Iterative Decoding Algorithms for Binary Linear
Block Codes」

This thesis mainly deals with the design and the evaluation of optimality conditions and ruling-out conditions for iterative soft-decision decoding algorithms.

At first, a sufficient condition, denoted Cond _opt,h, for the optimality of a decoded codeword based on h reference words are derived for any iterative soft-decision decoding algorithms for binary block codes which are based on the generation of a series of codeword candidates.

Next, for some concrete iterative soft-decision decoding algorithms, such as Chase-type decoding algorithms, some generalizations of Chase algorithm, the iterative minimum weight trellis search (MWTS) decoding algorithm, GMD-like decoding and multistage GMD-like decoding, some more effective optimality conditions and some ruling-out conditions are proposed.

Then, a class of nonlinear integer programming problems (IPPs) which can be used to evaluate the proposed testing conditions are shown. For some particular cases, the IPPs are solved completely. Especially, the IPP related to the optimality condition Cond_opt,h, denoted P(Q^*_h), is investigated. The IPP P(Q^*_h) has been solved for h3 in literature. For h5, it is shown that the IPP P(Q^*_h) can be split uniformly into a few simpler sub-IPPs, the number of variables of each sub-IPP is only half of that of the original IPP. By use of this splitting, an effective algorithm for solving the IPP P(Q^*₄) is given. The number of operations of additions and comparisons of real numbers, which is the dominant factor of the computational complexity of the algorithm, is shown to be of order N², where N is the length of the code.

An improvement of the optimality condition Cond_opt,h, is proposed further by use of partial information of the distance profile of the code. Some methods for evaluating the improved optimality condition for some particular cases are shown.

The first five search centers of the multistage Chase-type decoding algorithm that consists of a series of Chase-type decodings for which the next search center is chosen as the best one among the words that have not been visited are also determined. The number of operations of additions and comparisons of real numbers for the determination of the search centers is shown to be of order τ, where τ is the number of errors that can be corrected in an iterative step of a Chase-type decoding.

	佐藤健哉

「移動経路情報を利用した移動体通信アーキテクチャに関する研究」

本研究は，一般の携帯情報機器と異なり，車載情報機器における移動特性，通 信手段，利用情報の特徴を利用した情報通信の効率化を図る移動体通信アーキ テクチャに関するものである．具体的には，以下の3項目から構成される．

(1) 帯域が狭いパーソナル通信，連続的に通信を行えない専用狭域通信，必要 データ出現まで待ち時間が発生するデータ放送，これらの特徴を活かし併用す ることで，階層構成を採る情報を効率的に配信する方式を提案し，その実装モ デルの構築を行った．

(2) パーソナル通信，データ放送では，データ取得完了までの遅延が大きいた め，データの先行取得(プリフェッチ)が必要となる．利用情報を位置依存情報 に限定し，移動経路を考慮することで，データの取得・管理を効率的に行える キャッシュ方式の提案，評価，実装を行った．

(3) 専用狭域通信は，通信範囲が狭く不連続で，データを効率的に転送できな い問題がある．車両側の移動経路情報を利用することで，効率よく通信可能な 空間的時間的資源割当てプロトコル(STRAP)を提案した．また，実環境想定モ デル上でてシミュレーションを用い，STRAPの有効性を評価した．

本論文では，上記手法により，パーソナル通信，専用狭域通信，データ放送特 有の問題点を軽減し，かつ，それぞれ固有の利点を活かし併用することで，情 報を効率的に配信・管理を行なう移動体通信アーキテクチャの提案，評価，実 装についての報告としてまとめた．

	楳田敏之

「医用超音波動画像を利用した実時間遠隔医療システムに関する研究」

本研究では、医用超音波動画像遠隔医療を実施するのに、医用画像を撮影終了 後に伝送して診断する、従来の医用画像を用いた遠隔医療システムを用いると、 医用超音波動画像診断装置の臓器を実時間で画像化できる利点を有効に活用で きない点を解決するため、医用超音波動画像を実時間で圧縮し、ディジタル回 線を用いて遠隔地に伝送する実時間医用超音波動画像遠隔医療システムを提案 する。また、提案システムは、遠隔地の専門医が医用超音波動画像の撮影者に 対して、撮影方法を適切に指示することを可能とする。その上、診断に必要と なる医用超音波動画像領域だけを伝送することで、低速で品質の低いディジタ ル回線を用いた遠隔医療を可能とする。

提案システムが医用超音波動画像を利用した遠隔医療に有効であることを示す ため、提案システムの構築を行い、Integrated Service Digital Network (ISDN)回線、国内衛星回線、国際衛星回線を用いた、さまざまな遠隔医療実験 を専門医を交えて行い、提案システムは回線容量や回線品質に関わらず、円滑 に医用超音波動画像遠隔医療を実施できることを明らかにした。

	桐島俊之

「注視点の学習と選択制御に基づく身振りの実時間画像認識」

コンピュータハードウェア性能の急速な向上は，次世代の利用者情報環境である仮想現実感（ＶＲ：バーチャルリアリティー）環境構築のための利用者インタフェースの開発を可能としている．

仮想現実感システムでは，利用者の身振りを実時間で高速に追跡・認識することが要求されるが，従来の画像処理に基づく身振り認識手法では，認識対象とする身振りの数や性質に制限を設けたり，インターフェースとして利用する際に発生する追加的負荷により処理速度が低下するなどの問題があった．

これらの問題に対処するために，本研究では，身振り認識の際に重要な役割を果たす画像特徴集合に認識システムを選択的に適応させることを目的とした多注視点身振り認識法（QVIPS）を提案し，さらに任意速度で安定した身振り認識処理を実現することを目的とした多注視点選択制御手法を提案する．

また，提案手法の応用例として（１）インタラクティブビデオシステム（仮想現実感への応用）（２）手話画像データベース検索システム（検索への応用）の開発を行った．

本発表では，提案手法の有効性を示す評価実験の結果と、応用システムの動作例をビデオを交えて報告する。

	宗像浩一

「Studies on Integration of Heterogeneous Information Sources」

まず最初に，メディエータが連言（conjunctive）問合わせを受けて，データ構造が 異なり内容が不整合を持つ複数の情報源から得られる最大限のデータを、結合を用い て統合するための手法を述べる．このためには，アウタージョイン（outerjoin）， 述語，および外部関数が必須となることを示し、これらを用いた問合わせ処理手順の 作成アルゴリズムを述べる．

次に，自己記述形式のオブジェクトモデルを用いて異種情報源を統合するための，問 合わせ処理方式を提案する．このデータモデルは構造が単純なため，種々のデータモ デルに基づくデータをこのデータモデルに変換することが可能である。しかしその反 面，このデータモデルに基づいて問合わせ処理を行うためには，従来の関係データベ ースで用いられていた問合わせ処理では対処できない種々の問題が発生する．そこで それらを解決するための手法を示し，これにより異種情報源から柔軟に所望の情報を 取得できることを示す．

最後に，一定周期で発生するデータで構成される周期データ列において，周期が互い に異なる場合に，これらを統合するための処理方式を提案する．各データ列から1個 ずつのデータを選択してデータ組合せを得るための基準として，鮮度と同期度を提案 し、さらに両者を線形結合した評価関数を定義する．まずデータの同期度に着目して いくつかの性質を明らかにし，同期度の上限を決定する．そして評価関数に基づいた 最適データ組合せを得るための，問合わせ処理の枠組みを示す．最後にこれを，実シ ステムに適用する例を検討し，単純なデータ選択方法に比べて同期度がほぼ半減する ことを示す．