二次記憶上の大規模グラフの処理に関する研究

博士論文

大規模データの管理と活用を目的とする計算機応用分野の拡大と,各応用分野におけるデータの大規模化,多様化が進んでいる.それらの応用分野に対応する計算機システムの構築に際し,複数の応用プログラム間での統合的なデータ利用と,効率的な二次記憶上データの管理が要求される.そのような要求への対応のため,データベース領域の技術を用いた汎用性の高いソフトウェア部品やデータベース管理システムの供給が望まれている．ところが,従来のデータベース分野の研究では,対象とする応用分野を主に事務処理などの限られた領域に限定していたため,それらの分野で扱われることの少なかった多くの問題については,十分な研究がなされていなかった.そのような,多くの応用分野において重要であるにもかかわらず,従来データベース分野においては十分な研究が行われて来なかった問題の例として,グラフ上の問題に帰着する問題群があげられる.本研究では,大規模グラフ上の問題に帰着可能であるような多くの応用分野の問題に対して有効である.データベース管理システムの機能もしくはソフトウェア部品として利用可能である手法を提案する.本研究では,二次記憶上の大規模グラフに適した最短路探索アルゴリズムである,DFアルゴリズムと,大規模グラフの走査に適したページ置換手法である,KNC-Dページ置換の2つの手法を提案する.DFアルゴリズムはDijkstraの最短路探索アルゴリズムと本質的に同一の原理にしたがって動作する単一始点最短路探索アルゴリズムであり,応用分野に固有のデータ性質に関する知識を必要とせずに,Dijkstraの最短路探索アルゴリズムと比較して少ない二次記憶参照数で最短路を計算する.KNC-Dページ置換手法は,今日データベースの分野で一般に用いられているLPUページ置換手法に基づく必要時ページ置換手法である.KNC-Dページ置換を用いることにより,グラフに対する多くの演算に共通するデータ参照の特徴を利用した効率的バッファ管理が可能である.

1998