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

• Item type: SIG Technical Reports(1)
• 公開日: 2004-07-14
• タイトル: 木構造を用いた並列頻出パターンマイニングにおける動的負荷分散機構
• タイトル / 言語: en
• タイトル: Adaptive Load Balancing on Tree Based Parallel Frequent Pattern Mining
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 日本電信電話株式会社NTT情報流通プラットフォーム研究所
• 著者所属: 東京大学生産技術研究所
• 著者所属(英): en
• 著者所属(英): NTT Information Sharing Platform Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): Institute of Industrial Science, The University of Tokyo
• 著者名: イコプラムディオノ; 喜連川, 優
• 著者名(英): Iko, Pramudiono; Masaru, Kitsuregawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 大規模データベースから頻出パターンを効率的に発掘するのに、データ特性への適応が課題とされてきた．PCクラスタ上にFP-growthを基にした並列マイニングアルゴリズムを開発した．FP-growthが使用するFP-treeというデータ構造は分割が困難とされており、ノード間の処理負荷の偏りが増大する．提案する並列アルゴリズムは新たに導入されるpath depthと呼ばれるパラメータによって処理負荷を予測する．path depthは頻出パターンになりうるFP-treeの枝の長さから計算できる．しかしpath depthによる負荷分散制御はデータ特性依存パラメータを用いるため、未知のデータに対して、最適な値の決定が困難であった．本発表では、そのパラメータをマイニング実行中に最適化できる手法を提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Adaptability is a major challenge to efficiently mine frequent patterns from large scale databases. We develop FP-growth based parallel mining algorithms on a PC cluster. Since the FP-tree is a complex data structure it s difficult to partition and also increase the processing skew among nodes. The parallel algorithm employs a parameter called "path-depth" to estimate the workload from the minimum length of the tree-branches that possibly become frequent. Since the path depth is a data dependent parameter, we develop adaptive approaches to dynamically adjust the parameter during the execution.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 2004, 号 72(2004-DBS-134), p. 561-567, 発行日 2004-07-14
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会