木構造を用いた並列頻出パターンマイニングにおける動的負荷分散機構

摘要

大規模データベースから頻出パターンを効率的に発掘するのに、データ特性への適応が課題とされてきた．PCクラスタ上にFP-growthを基にした並列マイニングアルゴリズムを開発した．FP-growthが使用するFP-treeというデータ構造は分割が困難とされており、ノード間の処理負荷の偏りが増大する．提案する並列アルゴリズムは新たに導入されるpath depthとよばれるパラメータによって処理負荷を予測する．path depthは頻出パターンになりうるFP-treeの枝の長さから計算できる．しかしpath depthによる負荷分散制御はデータ特性依存パラメータを用いるため、未知のデータに対して、最適な値の決定が困難であった．本発表では、そのパラメータをマイニング実行中に最適化できる手法を提案する．