from KDD 2012 speaker: Kazuhiro Inaba

Slides:



Advertisements
Similar presentations
G ゼミ 2010/5/14 渡辺健人. パフォーマンスの測定 CUDA Visual Profiler CUDA の SDK に標準でついているパフォーマン ス測定用のツール 使い方: exe ファイルのパスと作業ディレクトリ指定して実 行するだけ 注意点 : GPU のコード実行後にプログラム終了前に,
Advertisements

組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
ヒストグラム5品種 松江城 出雲大社 石見銀山 三瓶山 アクアス しかしグラフで比較するのはめんどうなところがある 端的に1つの数字(代表値)で品種の特徴を表したい.
研究紹介 ネットワーク符号化 安永憲司 2008 年 5 月某日. 目次  ネットワーク上の通信  ネットワーク符号化 線形ネットワーク符号化 ネットワーク符号化の利点・欠点 ランダム線形ネットワーク符号化  まとめ  参考文献 2.
凸関数じゃないですか (最大値/最小値を求める問題) 目的関数を固定する (最大値/最小値を最小/最大化する問題)
ファイルキャッシュを考慮したディスク監視のオフロード
Lexical Permutation Sorting Algorithm
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
第11回 整列 ~ シェルソート,クイックソート ~
    有限幾何学        第8回.
言語処理系(4) 金子敬一.
Approximation of k-Set Cover by Semi-Local Optimization
Paper from PVLDB vol.7 (To appear in VLDB 2014)
Paper Introduction Of Hammers and Nails: An Empirical Comparison of Three Paradigms for Processing Large Graphs 発表者: Kazuhiro Inaba.
Observable modified Condition/Decision coverage
EMアルゴリズム クラスタリングへの応用と最近の発展
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
LogStructuredFileSystem Servey
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
第11回 整列 ~ シェルソート,クイックソート ~
プログラム実行履歴を用いたトランザクションファンクション抽出手法
領域分割手法について 2008年2月26日 中島研吾.
静的情報と動的情報を用いた プログラムスライス計算法
シャノンのスイッチングゲームにおけるペアリング戦略について
Data Clustering: A Review
Rコマンダーで分割プロットANOVA 「理学療法」Vol28(8)のデータ
決定木とランダムフォレスト 和田 俊和.
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
Speaker: Kazuhiro Inaba
離散数学 08. グラフの探索 五島.
“Separating Regular Languages with First-Order Logic”
ソフトウェア部品分類手法への コンポーネントランク法の応用
確率伝搬法と量子系の平均場理論 田中和之 東北大学大学院情報科学研究科
WWW上の効率的な ハブ探索法の提案と実装
ランダムグラフ エルデシュとレーニイによって研究された.→ER-model p:辺連結確率 N:ノード総数 分布:
レジスタの割付け 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第12章5節.
Anja von Heydebreck et al. 発表:上嶋裕樹
コンポーネントランク法を用いたJavaクラス分類手法の提案
量子系における 確率推論の平均場理論 田中和之 東北大学大学院情報科学研究科
タンパク質の進化 タンパク質は進化の過程でどのようにドメインを獲得してきたのだろうか? 今のタンパク質を調べることでわからないだろうか?
25. Randomized Algorithms
東京工業大学 情報理工学研究科 数理・計算科学専攻 千葉研究室 栗田 亮
計算量理論輪講 chap5-3 M1 高井唯史.
First Course in Combinatorial Optimization
プログラム理解におけるThin sliceの 統計的調査による有用性評価
VMが利用可能なCPU数の変化に対応した 並列アプリケーション実行の最適化
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
シミュレーション論Ⅰ 第7回 シミュレーションの構築と実施.
データ解析 静岡大学工学部 安藤和敏
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
全体ミーティング (5/23) 村田雅之.
Max Cut and the Smallest Eigenvalue 論文紹介
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
「マイグレーションを支援する分散集合オブジェクト」
メソッドの同時更新履歴を用いたクラスの機能別分類法
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
クラスタリングを用いた ベイズ学習モデルを動的に更新する ソフトウェア障害検知手法
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木
発表者: 稲葉 一浩 複雑ネットワーク・地図グラフ セミナー 2017/1/19
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
Jan 2015 Speaker: Kazuhiro Inaba
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
Speaker: Kazuhiro Inaba Paper Introduction from WSDM 2015
回帰テストにおける実行系列の差分の効率的な検出手法
ベイジアンネットワークと クラスタリング手法を用いたWeb障害検知システムの開発
プログラミング演習I 補講用課題
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Presentation transcript:

from KDD 2012 speaker: Kazuhiro Inaba Paper Reading: from KDD 2012 speaker: Kazuhiro Inaba

内容 巨大グラフは1台のメモリには乗らない 複数台に分割して格納・処理する必要がある どのようにグラフを分割するのが良いか?

問題 入力 出力 G = (V, E) 有向or無向グラフ k マシンの台数 ε 許容アンバランス度 ε 許容アンバランス度 出力 V1, V2, ..., Vk Vのdisjointな分割 |Vi| ≦ C = (1+ε)|v|/k or Σdeg(Vi)≦C = (1+ε)(Σdeg(V))/k (実験での値) |V|~40M, |E|~1G 2 ~ 100 2 ~ 5% (?)

問題 入力 出力 G = (V, E) 有向or無向グラフ k マシンの台数 ε 許容アンバランス度 ε 許容アンバランス度 出力 V1, V2, ..., Vk Vのdisjointな分割 |Vi| ≦ C = (1+ε)|v|/k or Σdeg(Vi)≦C = (1+ε)(Σdeg(V))/k (実験での値) |V|~40M, |E|~1G 2 ~ 400 2 ~ 5% (?) 評価基準: {(u,v)∈E | u∈Va, v∈Vb, a≠b} が少ないほど良い

Streaming 入力は v∈V が1つずつ順に渡される G = (V, E) 有向or無向グラフ k マシンの台数 ε 許容アンバランス度 出力 V1, V2, ..., Vk Vのdisjointな分割 入力は v∈V が1つずつ順に渡される 各 v を受け取るたびに、(ほぼ)すぐに その partition 番号を出力しなければならない v の近傍に関する情報のみ使ってよい

この論文の内容 ストリームの順番 パーティション番号を割り当てる ヒューリスティクス 3 種類 (DFS, BFS, RANDOM) 8 種類 (後述) の組み合わせで評価実験

ヒューリスティクス 1. Balanced : 現在最小のパーティションに 2. Chunking : 端から順に詰める 3. Hashing : ランダム

ヒューリスティクス 4. Deterministic Greedy where 近傍に多いパーティションを選ぶ 4-1. w(t, i) = 1 unweighted 4-2. w(t, i) = 1 - |Pt(i)|/C linear 4-3. w(t, i) = 1 – exp( |Pt(i)|/C ) exponential ただし既に |P(i)|=C な i を除く (と思われる)(以下同様)

ヒューリスティクス 5. Randomized Greedy where 近傍に多いパーティションに行く確率を高める 5-1. w(t, i) = 1 unweighted 5-2. w(t, i) = 1 - |Pt(i)|/C linear 5-3. w(t, i) = 1 – exp( |Pt(i)|/C ) exponential

ヒューリスティクス 6. Triangle where vを足したら三角形が最も増えるパーティション 6-1. w(t, i) = 1 unweighted 6-2. w(t, i) = 1 - |Pt(i)|/C linear 6-3. w(t, i) = 1 – exp( |Pt(i)|/C ) exponential

ヒューリスティクス 7. Balance Big 閾値より degree の高いノードは “Balanced” 閾値より degree の低いノードは Deterministic Greedy

(Buffering) ヒューリスティクス C 個まで入力ノードを貯めておくことを許す 8. Prefer Big バッファに C 個のノード ID を読み込む loop { if バッファに閾値より degree の高いノードがある then そのノードを “Balanced” で分配 バッファに 1 個新たに読み込む else C個のノードを “Deterministic Greedy” で分配 バッファに新たに C 個のノード ID を読み込む }

(Buffering) ヒューリスティクス C 個まで入力ノードを貯めておくことを許す 9. Avoid Big C個のバッファの範囲で低degreeノードを 先に処理。“Deterministic Greedy” で 10. Greedy EvoCut C個のバッファの範囲でクラスタリング by EvoCut [Andersen&Peres STOC‘09] クラスタ単位で “Deterministic Greedy”

Watts & Strogatz Nature 1998 実験 Finite Element Mesh Social Watts & Strogatz Nature 1998 Holme&Kim Phys.Rev.E 2002 Social

実験:ヒューリスティクス間の比較

k-1 / k Linear Det. Gr. Offline (METIS)

Linear Det. Gr.

Greedy EvoCut

の全データセットでの平均

実験:分割数・グラフサイズの影響

Linear Det. Gr. Offline (METIS)

4 partition Offline (METIS) Linear Det. Gr.

実験:実際の計算速度への効果

PageRank 計算のパフォーマンス SPARK Framework ( http://spark-project.org/ ) Naive実装と Partition 間の通信を減らす実装 |E|=77M k=100 ε=2% 0.99 0.61

PageRank 計算のパフォーマンス |E|=1.3G k=400 ε=2% 0.997 0.913

Further Reading http://arxiv.org/abs/1212.1121 Random order + Linear Deterministic Greedy が Random order + Linear Random Greedy に勝る理由の分析をしている [McSherry 2001] のモデルで LDG はクラスタを復元するが LRG はしない [McSherry 2001] Erdos-Reny の拡張。ノードが k 色に彩色されている 辺を貼る確率は P = k * k matrix で与える このdraftでは p = Pii > Pik = q のケースを解析

まとめ 著者曰く BFS がよい Linear Deterministic Greedy がよい 感想 ...