Publication 論文 鈴村研究室 大規模データ処理・ストリームコンピューティング

INFORMATION AND COMMUNICATION ENGINEERS

Copyright ©2010 by IEICE

タヴシケダモヴヘ処理 よる゜ンェモベンシャエメネ処理 向

西井 俊 鈴村 豊太郎

東京工業大学 〒 _152-8550 東京都目黒区大岡山 _2-12-1

IBM ^{東京基礎研究所 〒} 242-8502 ^{神奈川県大和 鶴間} 1623-14

E-mail: [email protected], [email protected]

あら 大規模 成長 続 るエメネ構 を持 タヴシを，モ゚ャシ゜ヘ性を考慮 効率よ 解析 る ，タヴシ ケダモヴヘ処理を用い ゜ンェモベンシャエメネ処理を提案 る． 計算ペタャIncremental GIM-V^{を提案 ，タヴシ} ケダモヴヘ処理系IBM System S^{を用い 実装 評価を行い， より効率的 適用範} 広いタヴシケダモヴヘエメネ処 理 向 議論 る．人工タヴシ よる_PageRank 計算 よる評価 ，エメネ構 変化 及ぶ範 全体 _50% 内 ある

，゜ンェモベンシャエメネ処理 より_3.0倍 高 計算出来る を示 ．

ゥヴワヴチ タヴシケダモヴヘ処理，エメネ処理，_PageRank，_DSMS，_DSPS，_{System S}，_SPADE

Towards Incremental Graph Processing by Data Stream Processing

Shunsuke NISHII and Toyotaro SUZUMURA

Tokyo Institute of Technology 2-12-1 Ookayama, Meguro-ku, Tokyo, 152-8550 Japan

IBM Research - Tokyo 1623-14 Shimotsuruma, Yamato-shi, Kanagawa, 242-8502 Japan

E-mail: [email protected], [email protected]

Abstract We propose incremental graph processing using data stream processing, for effective analysis of large graph that evolves. We propose computation model “Incremental GIM-V” for this analysis, implement graph processing system using IBM System S, one of Data Stream Management System (DSMS), and evaluate its performance. Then we discuss more effective and more generally usable way to data stream graph processing. In evaluation about PageRank on artificial data, when the rate of range spread from changing graph points equals to or less than 50%, incremental graph processing makes computation speed 3.0~ times faster.

Keyword Data Stream Processing, Graph Processing, PageRank, DSMS, DSPS, System S, SPADE

1.

^入

近 ，大規模タヴシ処理 需要 高 り ある． 対象 るタヴシ ，エメネ構 を持 タヴシ 含 れる． 表的

，ゞゟノエメネや，_Twitterや_Facebook ソヴク ホャエメネ 挙 られる． ， よう エメネ構 を持 タヴ

シ 対 る 表的 処理 例 Google PageRank^{[1] 挙}

られる． よう エメネ処理₍ ，特 _Web利用ブ゜ッン エや_Web構 ブ゜ッンエ

[17,18]

を指 ₎を行う 研究 多 れ いる

[2,3]

， れら トッス処理 基 ある．トッス処 理 ，一旦タヴシを蓄積 ら解析を始 る． れ より確実 解析結果 得られる ，源タヴシ 生起 れ ら解析結果 を得る 期間 あり，解析 新鮮 失われ う． わ

，ソヴクホャエメネ ら得られる，瞬間的 話題性を 映 解析を行う 向い い い 言える．

本稿 ，タヴシケダモヴヘ処理

[4,5,6]

を用い エメネ処理 を行う を提案 る． 計算ペタャ ，Incremental PageRank^{[7] よ び ，}PEGASUS^[3] GIM-V (Generalized Iterative Matrix-Vector multiplication)^{を組 合わ} Incremental GIM-V^を提案

る．Incremental PageRank ^{トッス処理を効率よ 行う 手法}

ある ，タヴシケダモヴヘ処理 適用 る よう 利 ， 問題 生 る い 議論 る．

降 節 ， 第₂章 関連研究 い 述 る．本稿 提 案 るタヴシケダモヴヘエメネ処理 背景 ，第₃章 タヴシ ケダモヴヘ処理，第₄章 エメネ処理ペタャ_GIM-V Incremental

PageRank ^{概要 い 述 る． 後，第}5^{章 提案 る゜ンェ}

モベンシャエメネ処理ペタャIncremental GIM-V ^{い 説明 ，} 第₆章 実装，第₇章 評価 い 述 ，第₈章 議論を行 う．最後 ，第₉章 本稿 を述 る．

2.

^関連研究

大規模エメネ処理を行うクケゾヘ 関 る研究 ，_Google Pregel^[2]やィヴヅウヴベュン大学 _PEGASUS

[3]

挙 られる． れら トッス処理 基 エメネ処理クケゾヘ あり，大規模 タヴシを短時間 処理 る 複数 計算テヴチを用い 並列

散処理を行う る．_Pregel ，頂 処理 ベッ コヴグドックンエ より 復計算を行い，最終的 解析結果を得る． 様々 エメネ処理を実装 るよう ，_{C++ API} 形 ゜ンシヴネ ゟヴケを提供 いる． れ より，_PageRank

[1]

，最短路問題

[8]

，₂ 部ブッスンエ

[9]

，コプェメケシモンエ ゚ハモォヴクミン 実 装 れ いる． ，計算途中 故 生 ，スゟッ ェフ゜ンダを作成 ， ら復帰 る 耐故 性を考慮

実装 れ いる．計算性能 ，_Google社内 ₃₀₀カ゚

ら るェメケシ ，₁₀億頂 ，₁₂₇₁億辺 ら るエメネ 対 るクンエャソヴケ 最短路問題を，_700~800 解 る． PEGASUS MapReduce^{[10] 処理系 ある}Hadoop^{[11]を用い アヴ} ハンソヴケ エメネ処理クケゾヘ ある．_PEGASUS ，_PageRank， Random Walk with Restart (RWR)^{[12]，直 推定[13]，連結成 推定}

処理 実装 れ いる． ， れら 処理 共通 る計算 構

を，GIM-V (Generalized Iterative Matrix-Vector multiplication) ^いう， 行列 パェダャ 乗算₍ 乗法₎を一般化 抽出 ，

構 基 い 計算 最適化を行 いる．計算性能 ， Yahoo! M45 Hadoop^{ェメケシを含} 90 ^{計算機を用い ，}5.9 万頂 ，_2.82億辺 ら るエメネ 対 る_PageRank 計算を_50~100

解 る．_Pregel，_PEGASUS ，計算時間 タヴ

シ 大 ₍辺 数₎や計算機 数 逆数 線形 ケォヴャ る． エメネ処理 う ，特 _PageRankを高 計算 る手法 ， Incremental PageRank^[7]，Adaptive PageRank^{[14] ある．}Incremental

PageRank ^{，成長 続 るエメネ構 対 ，ある時}

PageRank ^{計算を， れより 古い時} PageRank ^計算結果

を利用 高 解 手法 ある．Adaptive PageRank ^，PageRank

乗法 よる計算 ，頂 束 異 る

を利用 ， 束 頂 ら 計算対象 ら除外 い 計算を る手法 ある．本研究 ，タヴシケダモヴヘエメ

ネ処理 高 化 ， れら _PageRank 高 計算手法を

り入れる を議論 る．

3.

^{タヴシケダモヴヘ処理}

タヴシケダモヴヘ処理 ，始 ･終 いう概念 い情報 列をケダモヴヘ び， ケダモヴヘを蓄積 る アンベ ペモ 逐次的 ド゜ハメ゜ン処理 い 計算ドメジ゜ヘ あ る．タヴシケダモヴヘ処理 様々 処理 抽象化ン汎用化 れ

り，幅広い処理 対 応用 る洗練 れ 処理系

られ いる 従来 音声や動画 ケダモヴプンエ 異

いる． よう 処理系 一 開 れ いる_System

S ^{[5,6,15] タヴシネュヴ ら直感的 処理を記述 る}SPADE

いう言語 用意 れ り，様々 タヴシケダモヴヘ処理を実現

いる．_SPADE カヴチ例やアヒヤヴシ 詳細 い 論文

[15]

詳細 記載 れ いる 省略 る ，_SPADE 簡易 記述

高い柔軟性を兼 備え り効率的 クケゾヘ開 能 いる．

4.

^{エメネ処理ペタャ}

^概要

本稿 提案 る゜ンェモベンシャエメネ処理ペタャIncremental GIM-V ^{基 る ，}GIM-V(PEGASUS)^{[3]， よ び} Incremental PageRank^{[7] い 説明 る．}

4.1 GIM-V

GIM-V (Generalized Iterative Matrix-Vector multiplication)^{[3] ，行} 列 パェダャ 乗算を一般化 ある．_n×_n行列_{M n}次 元パェダャ_v 乗算を行い，パェダャ_v' を得る計算

v_{’ = M}^×v を，要素 式 表わ ，

v_’i = ^Σ_i=1ⁿ M_ij^×v_j

る． 計算 ，乗算 総和 入 ₃ 演算 ら る． れらを一般化 ，₃ 演算を れ れ関数 _combine2,

combineAll, assign ^{，式 通り る．}

v_’i = assign(v_i, combineAll(

combine2(M_i1, v₁), …, combine2(Min^{, v}n⁾⁾⁾

，行列 要素 型_(TM)，パェダャ 要素 型_(Tv)，_combine2 戻り値 型_(Tc) ，実数型(float, double)^{やノヴモ゚ン型}(bool) ハモプゾ゛ノ ，配列や構 体 を る 能 ある． れ れ 関数 写像を書 ，

combine2 : T_M^× T_v^→ T_c combineAll : T_c ^配列→ T_v

assign : T_v^× T_v^→ T_v る．

エメネ処理 ，行列_Mをエメネ 隣接行列₍各辺 値₎，パ

ェダャ_vを各頂 値 扱い，_GIM-V 計算を 復的 行う

，様々 エメネ処理を行う る． ，_Mij 値 ，_j ら_i 辺 重 を表わ いる．

PEGASUS ^，GIM-V^{ペタャ 計算を}MapReduce(Hadoop)

実行 いる． _MapReduce計算 ₂ケゾヴグ _MapReduce

ら る． ，ケゾヴグ_{1 MapReduce} ，エメネタヴシ 入力₍辺，

頂 ₎を_Map グミノ ら行い，_Reduceグミノ _jをゥヴ

combine2()^{を実行 ， 出力をケゾヴグ}2 MapReduce ^入力

える．ケゾヴグ₂ ，_Mapグミノ _Reduceグミノ タヴシを投入 ，_Reduceグミノ _iをゥヴ combineAll(),

assign()^{を実行， 束 場合 全計算を終了 ，再度 復}

る場合 ケゾヴグ_{2 MapReduce} 出力をケゾヴグ_{1 MapReduce}

入力 える．

，_PEGASUS

[3]

，_GIM-Vを用い ，_PageRank，Random Walk

with Restart^{，直 推定，連結成 推定 ゚ャガモゲヘを実装 い}

る．

4.2 Incremental PageRank

Incremental PageRank Computation^{[7] ， 展 るエメネ 対 る}

高 _PageRank 計算方法 ₁ ある．ある時 エメネ_(G1)

対 る_PageRank 計算結果 得られ いる ， 計算結果

を利用 ，更新 れ エメネ_{(G2) PageRank} を計算 る．

Incremental PageRank ^， G1 G2^{を比較 ，新 追加}

れ 頂 ，モンェ構 変化 頂 ， よび れら らモンェ を辿 到達 る頂 _(VQ)， れ 外 ，_VQ 辺を張 い る頂 _(Vb)， 他 _{(Vu) 3} 集合 る． ，集合 V_Q ^{新 追加 れ 頂 ，モンェ構 変化 頂 を元} 幅優先探索を行う 求 る る． れら 集合 う

，_{Vb Vu G1 PageRank}を 利用 る ，後

述 る ケォヴャ を行え よい．_VQ 関 ，構 変

化 より新 _PageRankを計算 必要 ある ，_VQ

1. ^{エメネ 計算内容 よる 類}

V

V

V

^{変化し い頂点，辺}

変化した頂点，辺

V

: ( ^{変化頂点集合} )

変化した頂点から到達可能

/ GIM-V ^{の計算対象}

V

: ( ^{無変化頂点集合} : ^境界 )

V

^以外で， V

^{隣接する頂点} / ^{計算対象外}

V

: ( ^{無変化頂点集合} )

V

, V

^以外 / ^{計算対象外}

V_b ^{構 ら}PageRank ^{計算を行う．}

G1 G2 ^{，エメネ 含 れる頂 数 異 る} (n_G1, n_G2)^，

構 変化 い頂 _{(Vb, Vu) PageRank} 変化 生 る．

，_G1 求 い _PageRank 値を_G2 合う値 変換 る

必要 ある．具体的 ，_{G1 PageRank} 値 _(nG1/nG2)を乗算 れ よい． 計算を ケォヴャ ぶ． ，新 追加 れ

頂 対 _PageRank計算 初期値 _(1/nG2)を えれ

よい．

よう 計算方法を用いれ ，_{G1 G2} 間 _VQ 属 るテ

ヴチ 割合₍変化率₎ れ い ，_PageRank 計算を高

行う る．

5.

゜ンェモベンシャエメネ処理ペタャ

^提案

本節 ，提案 る゜ンェモベンシャエメネ処理ペタャ ある

Incremental GIM-V ^{説明， よび れ よる゚ャガモゲヘ 実装方}

法₍ハュエメプンエペタャ₎ 説明を行う．

5.1 Incremental GIM-V

本稿 用い タヴシケダモヴヘ処理 よるエメネ処理

計算ペタャ ある，Incremental GIM-V ^{い 説明 る．}Incremental

GIM-V ^{大筋 枠組} Incremental PageRank ^{同様 ， 頂}

を₃ 集合_{(VQ, Vb, Vu)} る． れら う ，_VQ い

GIM-V ^{計算を再度行う必要 ある ，}V_b^，V_u ^い

要 ． ，実 ₃ 集合 れる ある

時 エメネ 対 る_GIM-V 計算結果 既 得られ いる場合

あり， う い場合 最初 計算時 ， 頂

V_Q ^{属 る る．} 3 ^{集合 関係を} 1 ^{示 ．}

後， 前 ら存在 頂 値 対 ，必要 ら ケォヴャを 行い，新 追加 れ 頂 計算 初期値を設定 る． 後，

V_Q V_b ^対 GIM-V ^{計算を行う． ，}V_b ^{含 れる頂}

GIM-V combine2^{関数 を実行 ，}combineAll, assign 省略 る．

5.2 ^{ハュエメプンエペタャ}

Incremental GIM-V^{を計算ペタャ 時，゜ンシヴネゟヴケ}

を提供 り， れらを゚ャガモゲヘ 実 装 る必要 ある． ，_GIM-V 演算 あるcombine2, combineAll,

assign ^{ある． う ，}assign ^{入処理 ，頂}

束 定 記述 る必要 ある． ₃ 関数 加え，ケォヴ ャを行う関数_scale ，頂 初期値を設定 る_init 必要 る． 関数 他 ，行列 要素₍辺 重 ₎，パェダャ 要素₍頂 値₎， よび_combine2 戻り値 型_{(TM, Tv, Tc)} ， 復計算 限回数

IT_LIMIT^{を定義 る必要 ある． を実装 る ，エメネ}

処理 ゚ャガモゲヘをIncremental GIM-V ^{計算ペタャ 実行} るよう る．

れら ゜ンシヴネゟヴケ ，後述 るUDOP(Worker) ^参照 る_C++ バッジネ゙゜ャ 提供 れ り，゚ャガモゲヘ実装 者 バッジネ゙゜ャ ゾンハヤヴダを元 ， 記 関数定義，型定 義 よびブェュ定義を行う．

Incremental GIM-V ^{実装 れる゚ャガモゲヘ ，}GIM-V ^実装 能 ある 必要条件 ある ， れ 加え よう 性

質を満 望 い．

ン _変化 生 ，変化率_(VQ 割合₎ 大 ら い _: 扱うタヴシ 無向辺エメネ 場合や，有向辺エメネ ある 変化 生 変化率 大 る場合，計算内容 影響 生 い ，゜ンェモベンシャベソッチ よる計算範

縮 よる高 化 見込 い．

性質 より，無向辺エメネを扱う゚ャガモゲヘ ある Random Walk with Restart ゜ンェモベンシャベソッチ 適

い．

ン 復計算 より計算結果 徐々 束 ，゚ャガモゲヘ 復 回数を問わ い _: 例え _PEGASUS 実装 れる直 推 定゚ャガモゲヘ

[13]

，求 る直 値₌計算 復回数 ある ， 復回数を減ら 計算時間を短 る手法 使え

い． 6.

^実装

Incremental GIM-V ^{計算ペタャを}IBM System S ^{実行 る}

，_SPADE よりクケゾヘ 実装を行 ．本節 クケゾヘ

実装 い 説明 る．

本クケゾヘ ，エメネ 各頂 序数_{(0, 1, 2,} …₎ より_IDを割 り当 られる． ，エメネ処理 並列計算 より行われる．各頂 処理を担うハュコケ ノュッェ _K個_(K 正 整数₎ ら れ， ₂中 _W1~WK れ 対応 る．頂 i (0, 1, 2, ^…) ^処理 を担う ，(i mod K + 1)^{番目 ノュッェ ある．}

6.1 ^{タヴシネュヴ}

2 ^{クケゾヘ タヴシネュヴ を示 ． 中 各頂 アヒヤ} ヴシ₍ハュコケ₎を表 ，矢印 タヴシ 流れ₍タヴシケダモヴヘ₎を表 わ ．実装 用い アヒヤヴシ ，_Source(タヴシ 入力₎，_Sink(タ ヴシ 出力₎，_Split(タヴシ 割₎，_Bundle(タヴシケダモヴヘを

る_{) 4}種類 組 込 アヒヤヴシ ，_Master(エメネ処理全体 管理₎，_Worker(エメネ処理 並列実行_{) 2}種類 _UDOP(マヴギ定義 アヒヤヴシ₎ ある．

中 各アヒヤヴシ 動作 い 説明 る． ， 中 _K 値，_Workerアヒヤヴシ よび れ 付随 るアヒヤヴシ(Sink, Split,

Bundle) ^{並列数を表わ ． ，各アヒヤヴシ 処理 れ 対応}

るハュコケ ₁ 立 られ，並列実行 れる． れら ハュコケ 複数 計算機間 渡 配置 る 能 ある． ン Source(G) : クケゾヘ エメネタヴシ 入力を行う．

(^{辺 値}M_ij^{を設定 る})

ン Split(G) : エメネタヴシを担当 る Worker ^{渡 ．} (^各M_ij ^値をj ^{類 る})

ン Source(M) : エメネ処理 開始 ^{を 付 る．} ン Master(M) : エメネ処理全体 管理，

復計算 同期 管理を行う．

ン Sink(M) : エメネ処理 要 ^{時間 ュエ情報を出力 る．} ン Worker(W1~WK) : エメネ処理 ベ゜ン ^{る部 を実行}

る．_a(=1, …_{, K)} 番 アヒヤヴシ ，a = (j mod K + 1)^を満 頂 _j 情報_{(vj, Mij for} ∀_i)を保持 る．

ン Sink(W1~WK) : 各 Worker ^{担当 る頂 対 る} エメネ処理 計算結果を出力 る．

ン Split(W1~WK), Bundle(W1~WK) : Worker 間 タヴシ 流れを 制御 る．_Worker(Wa) ら_Worker(Wb) タヴシ 流れ ， Split(Wa) Bundle(Wb)^{を る．}

ン Bundle(M) : Worker ^{らMaster タヴシ 流れを束 る．}

6.2 ^{エメネ処理 流れ}

エメネ処理 流れ い 説明 る． ，エメネ処理 開始

Source(M) ^らMaster ^{タヴシ 入力} より行われる．処理全体

流れ 機 _VQ 出 _Vb 出 _GIM-V計算 結果

出力 ₅ ネゟ゜ゲ ら る． う _VQ 出 _GIM-V

計算 ₂ 復計算を行う ，複数 ケゾッハ ら る．

Master ^{，各ネゟ゜ゲ各ケゾッハ 開始を各}Worker ^伝え，Worker 間 通信 よりケゾッハを実行 ，実行 完了 を₍ 復計算

束 否 含 _)Master 伝える．全 _Worker ら

ケゾッハ 実行完了通知を_Master ら，次 ケゾッハ 進 ． よう 流れ 計算を進 い ．

エメネ処理 各ネゟ゜ゲ い 説明 る．

ン 機 _: エメネタヴシ 入力を 付 る． 機ネゟ゜ゲ 外 ネゟ゜ゲ エメネタヴシ 入力 行われ 場合， 機ネゟ゜ゲ

戻 らエメネタヴシ 入力を 映 る．構 更新

れ 頂 を_VQ 録 ，新 追加 れ 頂 _init()

を実行 る．エメネ処理 開始 る ，_VQ 出ネゟ゜ゲ 移 行 る．

ン _VQ 出 _: 機ネゟ゜ゲ， 直前 ケゾッハ _VQ 追加 れ 頂 ら，隣接 る頂 対 新 _VQ 追加 るベ ッコヴグを 行 る． ベッコヴグ _Worker間 通信を通 行 れる．全 ベッコヴグ 行 れ 後，ベッコヴ グを 頂 を_VQ 追加 る．新 _VQ 追加 れ 頂 存在 る場合 う一度 ネゟ゜ゲ ケゾッハを 実行 ，存在 い場合 _Vb 出ネゟ゜ゲ 移行 る．

ン _Vb 出 _{: VQ} 録 れ い い頂 ら，隣接 る頂 対

VQ ^{録 れ い い 問い合わ るベッコヴグを 行}

る．全 ベッコヴグ 行 れ 後，ベッコヴグを 頂 らベッコヴグを 行 頂 対 ，_Vb 追加 るベッコヴグを 行 る．再び全 ベッコヴグ 行 れ 後，ベッコヴグを 頂 を_Vb 追加 る．最後 ，

元々存在 い 頂 対 _scale()を実行 ，_GIM-V計算ネ

ゟ゜ゲ 移行 る．

ン GIM-V 計算 : VQ Vb ^{録 れ いる頂 ら，隣接}

る頂 対 _combine2() 計算結果 ベッコヴグを 行

る．ベッコヴグを 頂 _VQ 録 れ いる ら ，ベッコヴグを元 combineAll()^{を逐次実行 い ．全}

ベッコヴグ 行 れ 後，_VQ 録 れ いる頂

combineAll() ^{計算を完了 ，}assign()^{を実行 る． ，}

各頂 _assign() 束 う 定を行い，全

頂 束 場合 結果出力ネゟ゜ゲ 移行 ， う

れ う一度_GIM-V計算ネゟ゜ゲ ケゾッハを実行 る．

，ケゾッハ 事 回数 既定 復回数_{(IT_LIMIT)} 達

場合 結果出力ネゟ゜ゲ 移行 る．

ン 結果出力 : 各頂 ^{計算結果をクケゾヘ ら出力 る． 後，} 全 頂 を_{VQ, Vb} ら 録解除 ， 機ネゟ゜ゲ 戻る． 7.

^評価

本クケゾヘを用い Incremental PageRank ^{性能を，通常}

GIM-V PageRank^{計算 比較 ，計算時間を評価 る．}

7.1 ^実験条件

実験時 計算機環境 ，AMD Phenom X4 2.5GHz L2 512KB (4

cores), Memory 8GB ^{ら る計算機を}5 ^{用い ． う} 1

Master^{ハュコケやエメネ入力 実行}( 2^中 M, G ^対応) ^{用い ，}

残り _{4 Worker}ハュコケノュッェ 実行_{( 2}中 _W1~WK

対応₎ 用い ． れら 計算機 _1Gbps ゜ヴキヅッダ 接続

れ いる． ，_OSやプチャゞゟ゚ 全計算機共通 _CentOS 5.22.6.18-92.el5 AMD64, gcc4.1.2, InfoSphere Streams 1.2 (System S)^を

用い ．_Workerハュコケノュッェ 並列数_{K 64} あり，₄

計算機 対 れ れ₁₆ハュコケノュッェ 配置 ．

7.2 ^{評価゚ハモォヴクミン}Incremental PageRank

Incremental GIM-V ^{各゜ンシヴネゟヴケ}(4.3^節)^{を よう} 実装 れ ，本クケゾヘを用い Incremental PageRank ^計算を実 行 る．

ン _{TM, Tv, Tc : double(}倍精度浮動 数 数型₎ ン combine2(Mij^{, v}j^{) = M}ij^×vj

ン combineAll(x[]) = 0.85×sum(x[]) + 0.15/n ン _{assign(vi, vi_new) = vi_new}

ン _assign 束 定 _{: abs((vi_new-vi)/vi) < 1.0}×₁₀

-5

ン _{scale(vi) = vi×(nG1/nG2)} ン _{init(vi)=1.0/n} ン IT_LIMIT = 32

，エメネ入力 _Mij 値 ，_j ら_i 辺 張られ い る場合 値を1.0/out-degree(j) ^{れ いい． ，}out-degree(j)

j ^{ら 出向辺 数を表 ．}

7.3 ^{実験タヴシ}

実験 用い エメネ ， 記 通り 生成 人工タヴ

シを用い ． ， 示 _r 値₍変化率_{) 0%, 10%, …, 100%}

10^{通り 値を用い ．}

ン G1 : 頂 数10000，^{各頂 ら 出向辺 数 対数正規 (μ}

=4.0, ^σ=1.3, ^均値127.1) ^{従い無作 生成} (Pregel^[2] 実験タヴシ 準拠₎． ，辺を生成 る前 頂 を₃ 集合(A0, A1, B) ^る．集合A0 ^{頂 数}10000^×(1-r)-100 あり，集合_A0，_A1 対 出向辺を持 ．集合_A1 頂

数₁₀₀ あり，全 集合 対 出向辺を持 ．集合_B

頂 数₁₀₀₀₀×_r あり，集合_B 対 出向辺を持 ．

生成 れ 辺 総数 約₁₂₇万弱 る．

ン G2 : G1 を元 ，集合 B ^{ら無作 100頂 選び， ら} 出向辺を無作 再設定 る． ， 出向辺 集合_B

対 張られ いる．頂 数 _G1 同様₁₀₀₀₀，辺

総数 約₁₂₇万弱 る．

れ より，_{G1 G2} 間 変化率_(VQ 割合_{) r(=0%, …, 100%)} 2. ^{エメネ処理クケゾヘ タヴシネュヴ}

Source (M)

Source (G)

Master (M)

[UDOP]

Split (G)

Bundle (M)

Worker(W1) [UDOP]

〃_(W2) [UDOP]

〃_(WK) [UDOP] Sink

(W1)

〃 (W2)

〃 (WK)

Split (W1) ^〃 (W2) ^〃 (WK)

Bundle (W1)

^〃 (W2) ^〃 (WK)

り，_Vb 割合 _1% る． よう 状態 ，_G1 対 る PageRank ^{計算結果 得られ いる ，}Incremental GIM-V ^よ

る_{G2 PageRank} 計算 通常 _GIM-V よる_PageRank 比

程度 計算 る 評価 ．

7.3 ^実験結果

Incremental GIM-V ^よる G1 ^{計算結果を利用} G2

PageRank ^{計算， よび通常} GIM-V ^よるG2 PageRank ^計

算 要 時間_(95%信頼区間₎を ₃ ， 度比_(GIM-V 計算

時間÷Incremental GIM-V ^計算時間)^を 4 ^{，計算時 復回数} を ₅ 記 ． ， 復回数 限 ₃₂回 設定 れ いる．

， ₃ ，Incremental GIM-V ^{計算時間 う ，}V_Q, V_b ^計算

要 時間 _GIM-V計算 要 時間 構成比 るよう

ハュッダ れ いる． ，通常 _GIM-V 計算 ，_VQ 出，

V_b ^{出 ネゟ゜ゲ 省略 ，全 頂 対} PageRank^を計算

るようクケゾヘ 変更を加え 実行 ．結果より，Incremental GIM-V V_Q, V_b ^{計算 要 る時間 変化率 依ら} 1.0~1.5

あり，_GIM-V 計算時間 復回数 依存 変化

Incremental GIM-V^{全体 計算時間 ，変化率や所要 復回数 より}

大 変化 る ． ，Incremental GIM-V^を用いる

より，通常 _GIM-V 比 ，変化率 _50% 内 あれ _3.0

倍 _PageRankを計算 る 出来る ．

ら ， 結果 ら，Incremental GIM-V^{を用いる ，変化率}

い 計算 る り，一方，変化率 大 ある程度高 計算 る ． れ ， 前 解析 結果を利用 る ， 束 要 る 復回数 る

よる 推測 る． ，人工タヴシ生成時 タヴシ構 大 ら 生 る より，変化率 よら パヴケメ゜

ン₍通常 _GIM-V) 計算時間 大 異 る結果 いる．

8.

^議論

8.1 ^{大規模エメネ 対応}

回実装 クケゾヘ ， 記 通り 改善 あ

り，ある程度 大 エメネを処理 い いう問題 生 いる．

，_{System S} 各ハュコケ₍アヒヤヴシ₎ 動作 い 説明

る．各ハュコケ タヴシ₍シハャ₎処理を行うケヤッチ ₁

あり，同時 ₁ シハャ 処理 い．あるシハャ 処理 中 シハャ 到着 場合，一旦ハュコケ トッネ゙₍ゥポヴ₎ 保存 ，現在 シハャを処理 終え ら，トッネ゙ 保存 れ いる次 シハャを処理 る． トッネ゙ 大 制限 あ り，トッネ゙ 埋 場合 ， ハュコケ シハャを投 よう いるハュコケ ，トッネ゙ 空 る 処理を中断 らう．

，本稿 実装 クケゾヘ _Workerハュコケ 処理を説

明 る．_Workerハュコケ エメネ処理 流れ ， _Master ら

行 れるケゾッハ開始ベッコヴグ₍シハャ₎を 付 る． シ

ハャ 処理中 ，他 _Worker 多 ベッコヴグを 行 よう

る． 行先 _Worker ，ケゾッハ開始ベッコヴグを処理

いる最中 ある ，_Worker間ベッコヴグ 直 処理 れ

，トッネ゙ 保存 れる． ，_Worker間ベッコヴグ 数 あ

り多 い場合 ，ケゾッハ開始ベッコヴグ 処理 終了後，

Worker^{間ベッコヴグ 処理を進 る る．一方，ベッコヴ}

グ 多い場合 トッネ゙ 埋 い，ベッコヴグ 行元

Worker ^{ハュコケ 行先 トッネ゙ 空 る 処理を中}

断 よう る． ， 行先 ハュコケ 他 ハュコケ ベッコヴグを 行 よう ，ハュコケ 処理を中断

いる． よう ，トッネ゙ よりタッチュッェ 似 状態 生 い，全 ハュコケ 処理を中断 う．

記 り 理 より，実 ゞゟノエメネ 準

大 を持 エメネを処理 い． ，本稿 エ

メネ クケゾヘ 評価を行 ．

8.2 Incremental GIM-V ^{性能最適化 向}

本稿 提案 る計算ペタャ Incremental GIM-V ^，Incremental

PageRank ^{いうトッス処理 よる}PageRank^{計算を高 行う手法}

を元 いる． ，Incremental GIM-V ^{正確 エメネ解析}

を行う る ，タヴシケダモヴヘ処理 依然計 3. ^変化率(r)^毎 Page Rank^{計算時 る}

Incremental GIM-V(V_Q, V_b^計算 /^全体) GIM-V ^計算時間(95%^信頼区間)

4. ^変化率(r)^毎 Page Rank^{計算時 る} Incremental GIM-V GIM-V ^{対 る計算 度比}

5. ^変化率(r)^毎 Page Rank^{計算時 る} Incremental GIM-V GIM-V ^復回数

1.2 1.4 1.1 1.0 ^1.3 1.1 1.2 1.0 1.1 1.5 1.4 1.5

4.3 4.4 ^{6.0 5.5} 9.1

6.6 10.7

13.0 11.2

6.8 7.4

27.2

26.0 ^27.0 25.8 ^26.9 28.7

26.9 26.9 26.8

7.5

0.0 5.0 10.0 15.0 20.0 25.0 30.0 35.0 40.0

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

計算時間(秒)

変化率_(r)

Incremental GIM-V (VQ, Vb^計算) Incremental GIM-V (^全体) GIM-V

5.0 6.3

5.9

4.5 ^4.7

2.9 4.4

2.5

2.1 ^2.4

0.0 1.1

1.0 2.0 3.0 4.0 5.0 6.0 7.0

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

Incremental GIM-V速度比

変化率_(r)

1 29

21 23

15 22

13 18

16 13

7 9

32

9

0 4 8 12 16 20 24 28 32

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

反復回数(上限32回)

変化率_(r) Incremental GIM-V GIM-V

算時間 り る． ，_5.1節 述 通り，無向辺エメネ や変化率 大 る有向辺エメネ 高 化 見込 い．実

処理時間を考慮 ， ₃より，_{VQ, Vb} 範 計算を行う

約₁₀₀万辺 約_1.0~1.5 り，決 無視 る 短

い時間 い．

，Incremental GIM-V ^{計算範 より ら 計算範 を}

短 る 計算時間を短 る 必要 考えられる．例 え ，構 変化 頂 ら距離 _1~3程度 近い頂 を計 算 る， 方法 考えられる． ，_GIM-V計算 復回数 関 ，本稿 クケゾヘ ， 束 る ，あるい 既定 復回数 達 る 復計算を行 いる． ，₁回 エメネ 処理ェ゠モあ り 復回数を ら 減ら 考えられる． 例え ， 束 定を行わ 既定 短い回数_(1~3 回程度₎ 復計算を行う ， 束 定 要 る計算時間を短縮 る 考 えられる．あるい ，Adaptive PageRank^{[14] 手法を用い ，計算}

束 頂 計算対象_(VQ) ら除外 る よる計算 高 化 見込 る．

よう 簡略化 手法 ，正確 エメネ処理を行う い． ，タヴシケダモヴヘ処理 トッス処理を組 合わ る手法

[16]

より，タヴシケダモヴヘ処理 空 時間 トッス処理を 行う 性格 解析を行う手法 考えられる．

9.

^{後 課題}

本稿 ，タヴシケダモヴヘ処理を用い エメネ処理を行う を 提 案 ， 計 算 ペ タ ャ _PEGASUS

[3]

よ び Incremental PageRank^{[7] ら習} Incremental GIM-V^{計算ペタャを}

提案 ， ， Incremental GIM-V ^{基 エメネ処理を行}

う ，タヴシケダモヴヘ処理系_{System S}を用い エメネ処理クケ ゾヘを実装 ． 評価 ，人工的 タヴシを用い

PageRank ^{計算を行い，一定 条件 ヂ゜ヴノ エメネ処理より}

高 計算 る を示 ．

本稿 ，_8.1節 述 理 より実 ゞゟノエメネを用い

評価を行う ， 後実装を改善 大規模

エメネを扱えるよう ，実タヴシを使 十 評価を行う必 要 ある．

，本クケゾヘ ，エメネ処理 開始 シ゜プンエをタヴシ 到達依存 外部 ら カブンチ 制御 いる． れをタヴ シケダモヴヘ処理 適 形 る ，タヴシ到達あるい 時間経過 伴 ，適 シ゜プンエ エメネ処理を開始 るよ う い．

最後 ， 回 Incremental GIM-V ^{評価゚ハモォヴクミン}

PageRank ^{を用い ，他 ゚ハモォヴクミン い 適}

用 い 検討 ，評価 る必要 ある．

謝辞

本研究 一部 学研究費補助金ン挑戦的萌芽研究（課題番

:22650017) ^{助成 よ 行われ ．}

参 考 文 献

[1] L. Page, S. Brin, R. Motwani and T. Winograd, “The PageRank Citation Ranking: Bringing Order to the Web”, Stanford Digita l Libra ry Technologies, January 1998.

[2] G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser and G. Czajkowski,

“Pregel: A System for Large-Scale Graph Processing”, ACM 2010.

[3] U Kang, C. E. Tsourakakis and C, Faloutsos,

“PEGASUS: A Peta-Scale Graph Mining System -

Implementation and Observations”, ICDM 2009. [4] D. J. Abadi, Y. Ahmad, M. Balazinska, U. Cetintemel,

M. Cherniack, J.-H. Hwang, W. Lindner, A. S. Maskey, A. Rasin, E. Ryvkina, N. Tat bul, Y. Xing and S. Zdonik, “The Design of the Borealis Stream Processing Engine”, In P roc. CIDR, pages 277.289, 2005.

[5] J. Wolf, N. Bansal, K. Hildrum, S. Parekh, D. Rajan, R. Wagle, K.-L. Wu and L. Fleischer, “SODA: An Optimizing Scheduler for Large -Scale Stream-Based Distributed Computer Systems_”, Midd lewa r e, 2008.

[6] B. Gedik, H. Andrade and K.-L. Wu, “A Code Generation Approach to Optimizing High-Performance Distributed Data Stream Processing”, In P roc. USENIX, pages 847-856, 2009.

[7] P. Desikan, N. Pathak, J. Srivastava and V. Kumar,

“Incremental Page Rank Computation on Evolving Graphs”, ACM 2005.

[8] B. V. Cherkassky, A. V. Goldberg and T. Radzik,

“Shortest paths algorithms: Theory and experimental evaluation_”, Mathematical Programming 73, 1996, 129 -174.

[9] T. Anderson, S. Owicki, J. Saxe and C. Thacker,

“High-Speed Switch Scheduling for Local-Area Networks”, ACM Trans. Comp. Syst. 11(4), 1993, 319-352.

[10] J. Dean and S. Ghemawat, “Mapreduce: Simplified data processing on large clusters”, OSDI, 2004. [11] “Hadoop information”, http://hadoop.apache.org/ . [12] J.-Y. Pan, H.-J. Yang, C. Faloutsos and P. Duygulu,

“Automatic multimedia cross-modal correlation discovery”, ACM SIGKDD, Aug. 2004.

[13] U. Kang, C. Tsourakakis, A. Appel, C. Faloutsos and J. Leskovec, “Hadi: Fast diameter estimation and mining in massive graphs with hadoop_”, C MU -ML-08 -11 7, 2008.

[14] S. Kamvar, T. Haveliwala and G. Golub, “Adaptive methods for the computation of PageRank_”, Lin ea r Alg eb r a a nd its App lica tio n s 386 (2004) 51-65.

[15]^{松 浦 紘 也}, ^{雁 瀬 優}, ^{鈴 村 豊 太 郎}, _“タ ヴ シ ケ ダ モ ヴ ヘ 処 理 系 _{System S Hadoop} 統 合 実 行 環 境_”, Co mSys 2010.

[16]^{松 浦 紘 也}, ^{鈴 村 豊 太 郎}, “タ ヴ シ ケ ダ モ ヴ ヘ 処 理 ト ッ ス 処 理 る 動 的 負 荷 散_”, 電 子 情 報 通 信 学 会 技 術 研 究 報 告_{. D E ,} タ ヴ シ 工 学 110(107), 69-74, 2010-06-21.

[17] G. Chang, M. J. Healey, J. A. M. McHugh and J. T. L. Wang, “Mining the World Wide Web: An Information Search Approach (The Kluwer International Series on Information Retrieval, 10)”, Kluwer Academic Pub 2001/6/1.

[18] G. Chang, ^{梅 村 恭} , M. J. Healey, ^{藤 井 敦}, J. A.M. McHugh, J. T.L. Wang, ^{武 善 行}, “Web^{ブ ゜} ッ ン エ_{” (}翻 訳_), 共 立 出 版 2004/01.