割 用い
大規模 2 部 処理
雁瀬 優
†
鈴村豊太郎
‡
東京工業大学工学部情報工学 † 東京工業大学/IBM 東京基礎研究所‡ 1.研究背景
近 、 ン 評 価 指 標 し
Graph500[1] 策定 、大規模
処理 注目 集 い .大規模 処
理 必 要 中 、 株 式 市 場 や
ッ ン ン
、 処 理 要 求
多 数 存 在 し 、 論 文 、 大 規 模
対 し 処 理 適 応 際
問題点 解決策 提示 . 2.問題提起
2.1 処理 System S
処理 、始点･終点 いう
概 念 い 情 報 列 呼 、
蓄 積 く ン 上
逐 的 プ ン 処 理 し い く 計 算
あ . 処理 様々 処
理 抽 象 化 汎 用 化 、 幅 広 い 処 理 対 し 応 用 洗 練 処 理 系 し
い 点 従 来 音 声 や 動 画
ン 異 い . う 処理系
一 し 開発 い System S [2] 図 直 感 的 処 理 記 述 SPADE いう言語 用意 、様々 処理 実現し い .SPADE
例や ペ 詳細 い 論文[2] 詳
細 記載 い 省略 、SPADE 簡
易 記 述 高 い 柔 軟 性 兼 備 え 効 率 的
開発 可能 い .
2.2 処理 処理
大 規 模 処 理 研 究 盛
行 わ い 、 大 規 模
処 理 研 究 MapReduce 基 盤 し PEGASUS[3] 、 ッ 処 理 中 心 研 究 行
わ い . 処理 解析 先
行研究 [4] あ 、未 発展途上 段階 あ . 一 方 処 理 べ 情 報 増
一途 辿 、 処理 可
能 抜 本 的 処 理 方 法 改 善 必 要 不 可 あ .本論文 時系列上 変化 激しく、
逐 処 理 困 難 あ
大規模 2 部 対し、 処
理 行う 目的 し い . 処 理 い う 観 点 場 合 、 処 理 要 素 増 伴 う 各 処 理 計 算 増
え 、 処 理 回 数 増 考 慮 し く い.
2.3既存 処理 問題点
大規模 2 部 解析処理 例 し H. Tong[5] 提 唱 any-time-answer 目 的
2 部 解 析 Fast-
Single-Update FSU 存 在 .FSU 、 ン 法 Random Walk with Restart RWR 法 用い 2 部 間 関連
性 解 析 、 差 更 新 行
う 、 毎 回 べ 要 素 計 算 し 直 手法 比較し 計算 減 手法 あ .
大規模 2 部 ッ 的 処理 実時間
内 行 う 可 能 い う 点 非 常
大 意 味 持 、 増 大
各 処 理 計 算 増 点 あ 、 処 理 い う 観 点 見 、 上 流 ッ 情 報 到 着 頻 度 内
処 理 終 え い
処理 く し う 問題 .
3.本研究 提案手法 実装
ソ ッ ワ 代 表 大 規 模
持 性 質 一 し 、 ニ
構 造[6] い う 特 徴 存 在 し い . ニ 構 造 ッ 密 集 合 士 疎 ッ 繋 い 構 造 あ 、 割 し 計 算 し あ 程 度 処 理 精 度 保 知 い .本研究 そ 性質 利用し 高速解析手法 提 案 し 、 実 装 評 価 行 . 本 手 法
処 理 要 求 頻 度 、 必
要 処 理 速 度 達 成 割 数
適 選 、 各 並 列 散 処 理
、 処理 実現 .実装
処理系 System S 、 割 METIS[7] 、2 部 関連
性 求 し FSU 用い .対
Data Stream Processing for Large-Scale Bipartite Graph using Graph Partition
†Masaru Ganse, Information Science and Engineering , Tokyo Institute of Technology
‡ Toyotaro Suzumura,
Tokyo Institute of Technology/IBM Research-Tokyo
象 2 部 、頂点 動的 変化 考え 、 割数 決定 静的 行 . 4. 実験 評価
4.1評価対象 プ ン
評 価 対 象 し 匿 掲 示 ッ 間 関 係性解析 選択し .匿 掲示 一
集合体 例:ニ
中 ッ ッ (例:事件 A い )、
書 込 あ ン 存 在 し 、
ID あ 程度 期間 通常一日 自
己 一性 保証 . プ ン選択
基 準 し 、 匿 掲 示 時 系 列 特 有 プ 侵 害 問 題 考 慮 必 要 く 、 、 一 ッ 終 了 し 場 合
ッ 例:事件 A い 2 移 必要 あ 時 系 列 上 ッ 間 関 係 明 確
あ いう 2 点 あ .2 部 頂点
群 し ID ッ 、 ッ し
ン 用い . し 性質
性 質 依 存 、 今 回 用 い 2 日間 数25532、 ッ 数492、 ッ 数 85656 、 更新要求 均
約2 一回あ 計算 . 4.2実験環境
測定 ッ 情報 送信 し 1
Dual Socket Opteron 242
1.6GHz,Memory 8GB 、計算 し 4
Phenom 9850 2.5GHz, Memory 8GB 用 い 、
各 1GbE ッ ワ 接続 い
．ソ 全 共通 、OS
CentOS 5.2、gcc 4.1.2、InfoSphere Streams 1.2.0 System S 用い ．
4.3評価
割 、 計 算 時 間 図 １ う
変化し、 割数5 い 計算時間 1
処理 0.007 、 割数 し 場合 計算
時間 0.40 比較し 57 倍 高速化 実現し
.高速化比率 構造 一意
い 、 処 理 要 求
集 中 し 、 計 算 減 少 し 処 理 頻 度 減 少 し 場 合 割 最 悪 、
処 理 要 求 均 一 振 、 計 算 処 理 頻 度 両 者 最 減 少 し 場 合 割 最
善 計 算 考 え 、 あ 程 度
予測 立 .一方 、図 2 一
ッ 書 込 限 界 達 し ッ
移 際 関 係 性 推 定 処 理 回 数
割 数 測 定 し い 、 散
処理回数 変化 く、2 部 関連性
推 定 特 定 部 関 係 し い
明 .
5. 今後 展望
割 行 い 、 推 定 処 理 回 数 増 や く、 割前 比較し 処理時間 57
倍減 成 し .今後 展望 し 、
動 的 散 数 決 定 や 、 動 的 頂 点 追 対
応 構築 求 .
参考文献 [1] http://www.graph500.org/ [2] 浦 紘 也, 雁 瀬 優, 鈴 村 豊 太 郎.
処 理 系 System S Hadoop 統 合 実 行 環 境. ComSys 2010
[3] U.Kang, et.al. PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations. ICDM 2009
[4] Aggarwal C.C., Online Analysis of Community Evolution in Data Streams, SDM 2005
[5] H. Tong, et.al. Proximity Tracking on Time- Evolving Bipartite Graphs. SDM 2008.
[6] M.E.J Newman. Fast Algorithm for Detecting Community Structure in Networks. Phys. Rev 2004.
[7] G. Karypis, et.al. Multilevel k-way partitioning scheme for irregular graphs. JPDC 1998.
図1： 割 計 算 高 速 化 比 率
図2： ッ 間 関 連 性 割 数 変 化
