データベースからの知識獲得を効率化する理論とその実装に関する研究

データベースの大規模化やデータ収集技術の進歩にともない、複数のデータを効率的に処理することや、蓄積されたデータから知識を獲得することの重要性が増している。このことに着目し、9年度は既存のルール導出やアルゴリスムの性能を計算量の側面から再評価し、10年度にはそれらの効率を向上させることや情報獲得のために新たなアルゴリズムを提案することを目的とした。このテーマのもとで従来の研究成果を調査した結果、複数のコンピュータに分散して配置されたデータを統合して、知識や情報を獲得するまでの過程を効率化する並列処理効率化の問題に、これまで考慮されたことがない未提案の重要な問題があることを発見した。9年度は、この問題を組合せ最適化およびグラフ理論の枠組みで定式化することに成功した。10年度は、上記の問題を計算の複雑さの観点から厳密に評価することに成功すると同時に、その問題には効率的なアルゴリズムが期待できないことも判明した。そこでわれわれは、その問題を解く近似アルゴリズムを提案し、その理論的な精度を厳密に評価することに成功した。また、9年度の交付金によって導入された高性能のコンピュータをもちいて実験を行なうことにより、その近似アルゴリズムは、実用的にも十分な性能を有していることを確認することができた。さらに、その問題の一部のクラスに対しては、厳密な解法が存在することも発見し、そのアルゴリズムを設計した。これらの研究結果は、10年度中に論文として公表するには間に合わなかったが、すでに投稿予定のものも含めて、来年度以降に順次公表予定である。また本年度、データの統合処理に要するコストの評価に関する結果を公表した。

データベースの大規模化やデータ収集技術の進歩にともない、複数のデータを効率的に処理することや、蓄積されたデータから知識を獲得することの重要性が増している。このことに着目し、9年度は既存のルール導出やアルゴリスムの性能を計算量の側面から再評価し、10年度にはそれらの効率を向上させることや情報獲得のために新たなアルゴリズムを提案することを目的とした。このテーマのもとで従来の研究成果を調査した結果、複数のコンピュータに分散して配置されたデータを統合して、知識や情報を獲得するまでの過程を効率化する並列処理効率化の問題に、これまで考慮されたことがない未提案の重要な問題があることを発見した。9年度は、この問題を組合せ最適化およびグラフ理論の枠組みで定式化することに成功した。10年度は、上記の問題を計算の複雑さの観点から厳密に評価することに成功すると同時に、その問題には効率的なアルゴリズムが期待できないことも判明した。そこでわれわれは、その問題を解く近似アルゴリズムを提案し、その理論的な精度を厳密に評価することに成功した。また、9年度の交付金によって導入された高性能のコンピュータをもちいて実験を行なうことにより、その近似アルゴリズムは、実用的にも十分な性能を有していることを確認することができた。さらに、その問題の一部のクラスに対しては、厳密な解法が存在することも発見し、そのアルゴリズムを設計した。これらの研究結果は、10年度中に論文として公表するには間に合わなかったが、すでに投稿予定のものも含めて、来年度以降に順次公表予定である。また本年度、データの統合処理に要するコストの評価に関する結果を公表した。