文献

J-GLOBAL ID：201502221851761409   整理番号：15A0447049

共通項目セットを有する接続部分グラフを抽出する並列化

Parallelization of Extracting Connected Subgraphs with Common Itemsets

著者 (5件)： OKUNO Shingo (Kyoto Univ., Kyoto, JPN) ,  HIRAISHI Tasuku (Kyoto Univ., Kyoto, JPN) ,  NAKASHIMA Hiroshi (Kyoto Univ., Kyoto, JPN) ,  YASUGI Masahiro (Kyushu Inst. of Technol., Fukuoka, JPN) ,  SESE Jun (Tokyo Inst. of Technol., Tokyo, JPN)
資料名： 情報処理学会論文誌トランザクション プログラミング(Web)  (情報処理学会論文誌 プログラミング(Web))
巻： 7  号： 3  ページ： 22-39 (WEB ONLY)  発行年： 2014年07月14日 
JST資料番号： U0474A  ISSN： 1882-7802  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,接続されたすべての部分グラフを抽出するための並列アルゴリズムを提示している。それらの各々は,そのうちのサイズが与えられた閾値以上である一般的なアイテムセットを共有し,その中の任意のグラフから各頂点が項目セットに関連付けられている。また,タスク並列言語Tascellを使用して,このアルゴリズムの実装を提案した。この種のグラフマイニング社会的または生物学的ネットワークの分析に適用することができる。筆者らはすでにこの問題のCOPINEと呼ばれる効率的な逐次探索アルゴリズムを提案している。COPINEはその次の部分グラフに対応する枝を分岐することによって動的に成長する木構造の探索空間を削減する:すでに閾値より小さい項目セットを有し,同一の項目セットと既存のサブグラフを有する。サブツリー(タスク)の固有のセットが各ワーカーに割り当てられている並列検索において,過剰プルーニングを回避するために,我々は別のワーカーによって登録されたテーブルエントリを参照しているとき,ワーカーに一定の制限を置く必要がある。筆者らは,この制限を導入することによりCOPINESの拡張として並列アルゴリズムを設計した。実装の問題は,可能な限り,他の,ワーカーによって登録された多くのエントリを,ワーカーが安全に使用できるように,テーブルエントリを効率的に共有する方法です。筆者らは2つの共有方式を実施した:被害者の,ワーカーが自分のテーブルのコピーを作成し,被害者がそのタスクを分割することによって,タスクを生成し,それを盗みワーカーに割り当てる時,それを盗みワーカーに手渡す,また,(2)ロックによって制御された単一のテーブルは,ワーカー間で共有される。実際のタンパク質ネットワークを使用して,これらの実装を評価した。その結果,単一のテーブルの実装では,16,ワーカーにより,約4倍の高速化を達成した。(翻訳著者抄録)

シソーラス用語： *知識獲得 ,  グラフ ,  知識ベース ,  *負荷分散 ,  動的系 ,  *プログラミング言語 ,  並列処理 ,  *並列アルゴリズム ,  *アルゴリズム ,  探索問題 ,  木構造 ,  *探索アルゴリズム ,  *動的負荷分散
準シソーラス用語： *グラフマイニング ,  並列言語

分類 (1件)： 計算理論  (JB02000A)

引用文献 (25件)：

• Newman, M.E.J.: The Structure and Function of Complex Networks, SIAM REVIEW, Vol.45, No.2, pp.167-256 (2003).
• Russell, M.: Mining the Social Web: Analyzing Data from Facebook, Twitter, LinkedIn, and Other Social Media Sites, O'Reilly Media (2011).
• Seki, M. and Sese, J.: Identification of Active Biological Networks and Common Expression Conditions, Proc. 8th IEEE International Conference on Biolnformatics and BioEngineering, BIBE '08, pp.1-6 (2008).
• Sese, J., Seki, M. and Fukuzaki, M.: Mining Networks with Shared Items, Proc. 19th ACM International Conference on Information and Knowledge Management, CIKM ' 10, pp.1681-1684 (2010).
• Hiraishi, T., Yasugi, M., Umatani, S. and Yuasa, T.: Backtracking-based Load Balancing, Proc. 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '09, pp.55-64 (2009).

タイトルに関連する用語 (3件)： 接続部分 ,  グラフ ,  並列化