狠狠撸

狠狠撸Share a Scribd company logo

大规模グラフアルゴリズムの最先端

?
?
Takuya Akiba
Takuya Akiba
1 of 51
Download to read offline
2012/01/12 PFI セミナー 大規模グラフアルゴリズムの 最先端 秋葉 拓哉 (@iwiwi)
挨拶 ? 自己紹介 – 秋葉拓哉 / @iwiwi – 東京大学 コンピュータ科学専攻 M1 – アルゴリズム系の研究室 – プログラミングコンテストが好き – 2009 年にインターンさせてもらって以来アルバイト アリ本 （グラフの話もあるよ） 1
いろんなグラフ 道路?交通ネットワーク ? 頂点：交差点，駅など ? 辺：道，路線など やりたいことの例 ? 案内，交通管制 ? 輸送や災害のための解析 ? 地理情報と絡めたサービス ? … 2
いろんなグラフ ソーシャルネットワーク ? 頂点：人 ? 辺：人間関係 やりたいことの例 ? 「知り合いかも？」とか ? 重要度?影響度の解析 ? コミュニティ解析 ? 情報の伝播力の解析 ? … (MentionMap で作成) 映画 3
いろんなグラフ ウェブグラフ ? 頂点：Web ページ ? 辺：リンク関係 やりたいことの例 ? PageRank, HITS ? Web ページの関連性 ? … (Gephi HTTP Graph) 「ネットは広大」 4
大規模グラフ処理の需要 界隈 種類 頂点数 (辺数はもっと) OR 等 交通ネットワーク 全米：> 2 × 107 Twitter：> 2 × 108 人 ソーシャルネットワーク? Web 等 Facebook：> 5 × 108 人 Web グラフ Google：> 109 ページ 生物情報 タンパク質間相互作用など > 109 アメリカ国土安全保障省： 国防 (?) 謎 > 1015 [Kolda+’04] ? みんなデカいグラフを処理したいんだ！ ? 馬鹿げたサイズのものもある ? 他にも一杯あると思います 5
アカデミックな方々の関心 ? アルゴリズム界隈はもちろん ? VLDB (データベース界のトップ会議) – 2011 では “Graph Data” なるセッションが 3 つ ? SC (HPC 界のトップ会議) – 2010 でセッション “Graph Algorithms” ? 多分他でも… 6
HPC 界の関心 [http://blog.goo.ne.jp/sdpaninf/e/fdd6d1c59516418ccae7514a6512b0d1] ? Top500 の新しい仲間 ? スパコンをグラフの処理能力で格付け ? 日本は現在 TSUBAME が 3 位 7
日本のアカデミック界でも関心 [http://blog.goo.ne.jp/sdpaninf/e/87c8bf7886310ecfab1e56c8967e4b1e] JST CREST にも超大規模グラフに挑戦するチーム 8
インダストリアルからも関心 Graph DB 大人気！ 9
話すこと アルゴリズムの話をします (いっぱい話すので概要です) ? アルゴリズム界隈での話題 – 特に道路ネットワークでの最短路 ? DB 界隈での話題 最短路 – 特に複雑ネットワークでの最短路 ばっかり… ? HPC 界隈での話題 (??_?｀) – 特に並列分散環境での最短路 （大げさなタイトルに してすみませんでした） 10
特に道路ネットワークでの最短路 1. アルゴリズム界隈の話題 (画像: Google Maps) 11
アルゴリズム界隈 河原林先生 ? トップ会議 (日本が誇る世界のトップ!!) – STOC, FOCS, SODA, … – 理論系．証明．証明のためのアルゴリズム． oxyさんも まけてない!! – 実装して意味のあるアルゴリズムは少ない． ? 実験系アルゴリズムの会議 – ALENEX, SEA, ESA (engineering track), … – 実装して良い感じのアルゴリズムはこっちに． – 最近すこし良い感じなんですか？ ? SEA: workshop → symposium，ALENEX: workshop → meeting SODA, ALENEX は来週京都で開催!! アメリカ以外での開催は多分はじめて!! 岩間先生 (oxy 神のとこの先生) の還暦祝いという噂 12
実験系界隈でのグラフアルゴリズム ? Graph Partitioning, Graph Clustering – 超流行，最近だと毎回 2,3 本は論文がある – 去年，5 年ぶりの DIMACS Implementation Challenge の題材に – グラフを良い感じに分割したい – 様々な応用: ソーシャルネットワーク解析，分散処理，CV，… ? その他，計算困難問題 – クリークカバー (ALENEX’12), TSP (SEA’11), シュタイナー木 (ALENEX’10), … ? その他，基礎的な操作 – 最短路と仲間 (いっぱい), トポロジカルソート (ALENEX’11), 直径, … 13
最短経路クエリ処理 1. 前処理 前計算 データ 活用 2. クエリ処理 「本郷から駒場」 「30 分です」 「中野から秋葉原」 「20 分です」 「札幌から那覇」 「7 時間です」
道路ネットワークでの最短路クエリ ? 構造を活かしやすい ? 様々な効率的な技法 有名な手法 ? A*, ALT [HNR’72, IHI+’94, GH’05, …] ? Reach Pruning [Gut’04, …] ? Highway Hierarchy […] ? Transit Nodes […] 最新の手法 ? Highway Dimension [Abraham+, SODA’10] + ? Hub-Based Labeling Algorithm [Abraham+, SEA’11] 15
Dijkstra → 双方向 Dijkstra Dijkstra 双方向 Dijkstra s t s t 最短路が得られている 両側からやると 頂点が広がってゆく 余計な頂点が減る． アルゴリズム． 16
三角不等式 ? ???????????? ??????, ?????? ? グラフ ?????? 上での ??????, ?????? の最短距離 ? ???????????? ??????, ?????? ≤ ???????????? (??????, ??????) + ???????????? (??????, ??????) ? ???????????? ??????, ?????? ≥ ???????????? ??????, ?????? ? ???????????? (??????, ??????) ★今回はこっち(下界) (?????? は任意の頂点)
A*, ALT アルゴリズム A* ALT s v s t t l 人工知能等の探索でもお馴染み． ランドマークの頂点を用意． 近そうなところから探索． そこからの距離と三角不等式で 距離の下界を推定し A*． この辺は実装が楽，速度はそこそこ． (state-of-the-art と比べると全然) 18
双方向 Dijkstra + Reach Pruning の効果 Dijkstra 双方向 Dijkstra 双方向 RE [http://research.microsoft.com/en-us/people/goldberg/hwd.pdf] やばすぎ！効果絶大！ 19
Highway Dimension [Abraham+, SODA’10] ? これらの手法はヒューリスティクスだった – 「なんとなく」うまくいきそうな手法 – 実験してみるとたしかにうまくいく ? うまくいくことを解析したい！ → 道路ネットワークを数理的にモデル化 ? 道路ネットワーク ≒ “Highway Dimension” の 小さいグラフ [Abraham+, SODA’10] 「ある程度の距離になる最短路は， 必ず限られた頂点のどれかを通る」 （限られた頂点≒大都市的な． で，Highway Dimension が小さい ≒限られた頂点集合が割りと小さい．定義はもっとフォーマル） 20
Hub-Labeling Algorithm [Abraham+, SEA’11] ? Hub-Labeling Algorithm – DB 界隈で 2-Hop と呼ばれるものと同じ – 各頂点に関して，中継点候補を前計算 あらゆる頂点対について， 最短路を与える共通の頂点対が 存在するようにしておく 前計算アルゴリズムの性能で， 中継点のサイズが違ってきて， 小さくできるほど良い ? Highway Dimension が小さいというモデルで解析をする と，これが凄い速そう → 少し工夫して実装してみたら実際爆速!! 21
Hub-Labeling Algorithm [Abraham+, SEA’11] はやいｗｗｗｗ 5 ランダムアクセスぐらい？ 22
特に複雑ネットワークでの最短路 2. データベース界隈の話題 23
会議と話題 ? DB 系の会議: SIGMOD, VLDB, ICDE, CIKM, EDBT, … – Web, IR 界隈とも近い – インダストリアルとの距離が近い – プラクティカルな話題が多い ? グラフデータベース，分散グラフ処理系 ? グラフアルゴリズム – パターン検索，コミュニティ抽出，頻出パターン抽出 – RDF のクエリ処理，構造のある検索 – Uncertain Graph 上での各種処理 (枝に不確定性) – 到達可能性クエリ，最短路クエリ (亜種もいっぱい) 24
最短路クエリの応用例: Social Search
最短路クエリの応用例: Social Search
最短路クエリの応用例: Context-Aware Search 「木」 を検索
最短路クエリの応用例: Context-Aware Search 「木」 を検索
最短路クエリの応用例 ? Social Search – Social Network: 人を頂点，枝を友人関係 ? Context-Aware Search – Web Graph: ページを頂点，枝をリンク これらのグラフ上での最短距離を 結果のランキングの指標に使う
复雑ネットワークでの最短路クエリ ? 構造がカオス ? 交通ネットワークと比べ難しい 有名な手法 ? 2-HOP [Cohen+, SODA’02] [Cheng+, EDBT’09] ? 対称性の活用 [Xiao+, EDBT’09] ? ランドマーク系 (近似) [Potamias+, CIKM’09] [Das Sarma+, WSDM’10] [Gubichev+, CIKM’10] 最新の手法 ? 木分解による Core-Fringe 構造の活用 [Wei, SIGMOD’10] [Akiba+, EDBT’12] ← Christian さん 河原林先生 → 30
三角不等式 ? ???????????? ??????, ?????? ? グラフ ?????? 上での ??????, ?????? の最短距離 ? ???????????? ??????, ?????? ≤ ???????????? (??????, ??????) + ???????????? (??????, ??????) ★今回はこっち(上界) ? ???????????? ??????, ?????? ≥ ???????????? ??????, ?????? ? ???????????? (??????, ??????) (?????? は任意の頂点)
上界による最短距離推定 (単一ランドマーク) ? ???????????? ??????, ?????? ≤ ???????????? (??????, ??????) + ???????????? (??????, ??????) ★ u これをそのまま使う s t 1. 前処理 – 頂点 ?????? を1つ選ぶ（ランドマーク） – ???????????? (?, ??????), ???????????? ??????,? を全頂点に対し前計算しておく (幅優先探索) 2. クエリ処理 ???????????? ??????, ?????? = ???????????? ??????, ?????? + ???????????? (??????, ??????)
上界による最短距離推定 (複数ランドマーク) ランドマークを単一 (?????? ) から複数 (??????) にしよう ? ???????????? ??????, ?????? ≤ ???????????? (??????, ??????) + ???????????? (??????, ??????) ★ 複数頂点に使う s t 1. 前処理 – 一定数の頂点集合 ??????を決める（ランドマーク） – 各 ?????? ∈ ??????に対し ???????????? (?, ??????), ???????????? ??????,? を全長点に対し前計算 (BFS) 2. クエリ処理 ???????????? ??????, ?????? = min{ ???????????? ??????, ?????? + ???????????? (??????, ??????)} ??????∈??????
ランドマークの選択 ? ランドマークの選び方で近似性能が大きく変わる – ベースライン：ランダム ? 実は次数が大きいものから選ぶだけで良くなる！ [Potamias+’09] – 他にも Closeness Centrality や Graph Partitioning を使う方法 – 労力の割に大差ないかも [Potamias+’09, Table2] 34
複雑ネットワークの Core-Fringe 構造 [Lu’00] 複雑ネットワークは 以下の 2 つ (3 つ) に分けられる ? 密な “Core” Core ? 木に近い “Trails” ? (“Middle Layer”) Fringe よりフォーマルには，モデル (恣意的な可視化) の仮定のもとで証明可 35
木分解の活用 [Wei’10], [Akiba+’12] 木分解 ? グラフ → 頂点集合の木 ? どちらかというと理論界の道具 ? グラフが“木っぽい”とオイシイ (よりフォーマルには木幅が小さいと良い) 複雑ネットワーク ? 全体としては木っぽくない ? しかし Fringe 部分は木っぽい！ – 木分解してウマウマ ? Core はやっぱしんどい – 諦めるor頑張る 36
木分解の活用 [Akiba+’12] 数 M 頂点?辺ぐらいまでなら厳密解で爆速クエリ処理 クエリ時間 (μs) それ以上はシンドイので，近似手法と組み合わせる （5 M 頂点，70 M 辺 → 数十 μs，数％エラー） 37
特に並列分散環境での最短路 3. HPC 界隈の話題 38
会議と話題 ? HPC 系の会議: SC, ICS, ISCA, … ? 話題 （全て並列or分散） – 連結成分分解 – BFS, SSSP (最短路) – Eigenvector (PageRank, HITS) –… 特に IBM と LLNL 辺りが力いれてる SC? でバイオリンを弾く 平木先生 39
並列?分散環境でのグラフアルゴリズム グラフアルゴリズムの性質 ? ランダムなアクセスパターン ? データの再利用がない → 時間的局所性?空間的局所性の両方が超低い ? 並列化はとても難しい – 簡単には逐次を超えられない 40
Graph 500 日本では CREST スパコンのベンチマーク (超デカいグラフ) のチームの方々 ? 現在 BFS のみ でやっています ? 次に SSSP が入るという噂 ? 更にその次は極大独立集合 ? グラフは難しいので，ベンチマークとしては逆に良い – Top 500 の LINPACK は “簡単” ? ? 将来の需要も考慮 ? 現状，アルゴリズム?実装の優劣も大きく影響 – 配られてるリファレンス実装はスケールしない – まだまだアプローチに「決定版」がない – アツい！ （しかしスパコンのベンチマークになっているかは謎） 41
並列 BFS (共有メモリ) 並列 BFS の基本アルゴリズム 1. キューに始点入れる 2. キューが空でない間: ←このループを並列に – キューから頂点 v だす – v に隣接する全頂点で未訪問のものをキューに追加 42
並列 BFS (共有メモリ) の最適化 [Agarwal+’10] 基本 ? 到達したかのフラグをビットセットに – キャッシュミス減 ? ロックする前に値みてからロック ソケット超えの最適化 ? ソケットごとにキューを別に (inter-socket queue) – ソケット内での push とソケット外への push を別に – ソケット外から push されたのは後でまとめて処理 – 良い感じの lock-free queue ? Inter-socket キューの処理の batching – 何個か頂点まとめて push/pop → 通信を整理
実験結果 (性能向上) Nehalem-EX 8 コア × 4 ソケット (= 32 コア) [Agarwal+’10, Figure 5]
分散 BFS (クラスタ) [Buluc+’11]他 繰り返す 1 次元分割 × = 隣接行列 距離 i で到達可能な 距離 i+1 で到達可能な 頂点集合 頂点集合 全体全通信が必要となりスケールしない 45
分散 BFS (クラスタ) [Buluc+’11]他 繰り返す 2 次元分割 ■ ■ ■ ■ ■ ■ × = + ■ ■ ■ ■ ■ ■ 隣接行列 距離 i で到達可能な 距離 i+1 で到達可能な 頂点集合 頂点集合 通信が √n 倍程度減る (n はノード数) （しかし，これをベースに頑張り 40K コア使っても， SMP 32 コアの数十倍程度とかだったりしたりしなかったり…？) 46
終わりです：まとめ ? アルゴリズム界隈の話題： 道路ネットワーク – A*, ALT, Highway Dimension, Hub-Labeling ? DB 界隈の話題：複雑ネットワーク – Landmark, Core-Fringe Tree-Decomposition ? HPC 界隈の話題：並列分散 – ソケット超えの最適化，1D/2D 分割法 ありがとうございました （?__________?）／ 47
宣伝 48
宣伝 第二版が出ます!! ? 4 つの新トピック – 計算幾何 – 枝刈り探索 – 分割統治法 – 文字列アルゴリズム ? 練習問題コーナー ? 発展内容コーナー 49
宣伝 第二版が出ます!! ? 4 つの新トピック – 計算幾何 – 枝刈り探索 – 分割統治法 – 文字列アルゴリズム ? 練習問題コーナー ? 発展内容コーナー よろしくお願いします！ 1/27 発売！ 50

More Related Content

大规模グラフアルゴリズムの最先端

  • 1. 2012/01/12 PFI セミナー 大規模グラフアルゴリズムの 最先端 秋葉 拓哉 (@iwiwi)
  • 2. 挨拶 ? 自己紹介 – 秋葉拓哉 / @iwiwi – 東京大学 コンピュータ科学専攻 M1 – アルゴリズム系の研究室 – プログラミングコンテストが好き – 2009 年にインターンさせてもらって以来アルバイト アリ本 （グラフの話もあるよ） 1
  • 3. いろんなグラフ 道路?交通ネットワーク ? 頂点：交差点，駅など ? 辺：道，路線など やりたいことの例 ? 案内，交通管制 ? 輸送や災害のための解析 ? 地理情報と絡めたサービス ? … 2
  • 4. いろんなグラフ ソーシャルネットワーク ? 頂点：人 ? 辺：人間関係 やりたいことの例 ? 「知り合いかも？」とか ? 重要度?影響度の解析 ? コミュニティ解析 ? 情報の伝播力の解析 ? … (MentionMap で作成) 映画 3
  • 5. いろんなグラフ ウェブグラフ ? 頂点：Web ページ ? 辺：リンク関係 やりたいことの例 ? PageRank, HITS ? Web ページの関連性 ? … (Gephi HTTP Graph) 「ネットは広大」 4
  • 6. 大規模グラフ処理の需要 界隈 種類 頂点数 (辺数はもっと) OR 等 交通ネットワーク 全米：> 2 × 107 Twitter：> 2 × 108 人 ソーシャルネットワーク? Web 等 Facebook：> 5 × 108 人 Web グラフ Google：> 109 ページ 生物情報 タンパク質間相互作用など > 109 アメリカ国土安全保障省： 国防 (?) 謎 > 1015 [Kolda+’04] ? みんなデカいグラフを処理したいんだ！ ? 馬鹿げたサイズのものもある ? 他にも一杯あると思います 5
  • 7. アカデミックな方々の関心 ? アルゴリズム界隈はもちろん ? VLDB (データベース界のトップ会議) – 2011 では “Graph Data” なるセッションが 3 つ ? SC (HPC 界のトップ会議) – 2010 でセッション “Graph Algorithms” ? 多分他でも… 6
  • 8. HPC 界の関心 [http://blog.goo.ne.jp/sdpaninf/e/fdd6d1c59516418ccae7514a6512b0d1] ? Top500 の新しい仲間 ? スパコンをグラフの処理能力で格付け ? 日本は現在 TSUBAME が 3 位 7
  • 9. 日本のアカデミック界でも関心 [http://blog.goo.ne.jp/sdpaninf/e/87c8bf7886310ecfab1e56c8967e4b1e] JST CREST にも超大規模グラフに挑戦するチーム 8
  • 10. インダストリアルからも関心 Graph DB 大人気！ 9
  • 11. 話すこと アルゴリズムの話をします (いっぱい話すので概要です) ? アルゴリズム界隈での話題 – 特に道路ネットワークでの最短路 ? DB 界隈での話題 最短路 – 特に複雑ネットワークでの最短路 ばっかり… ? HPC 界隈での話題 (??_?｀) – 特に並列分散環境での最短路 （大げさなタイトルに してすみませんでした） 10
  • 13. アルゴリズム界隈 河原林先生 ? トップ会議 (日本が誇る世界のトップ!!) – STOC, FOCS, SODA, … – 理論系．証明．証明のためのアルゴリズム． oxyさんも まけてない!! – 実装して意味のあるアルゴリズムは少ない． ? 実験系アルゴリズムの会議 – ALENEX, SEA, ESA (engineering track), … – 実装して良い感じのアルゴリズムはこっちに． – 最近すこし良い感じなんですか？ ? SEA: workshop → symposium，ALENEX: workshop → meeting SODA, ALENEX は来週京都で開催!! アメリカ以外での開催は多分はじめて!! 岩間先生 (oxy 神のとこの先生) の還暦祝いという噂 12
  • 14. 実験系界隈でのグラフアルゴリズム ? Graph Partitioning, Graph Clustering – 超流行，最近だと毎回 2,3 本は論文がある – 去年，5 年ぶりの DIMACS Implementation Challenge の題材に – グラフを良い感じに分割したい – 様々な応用: ソーシャルネットワーク解析，分散処理，CV，… ? その他，計算困難問題 – クリークカバー (ALENEX’12), TSP (SEA’11), シュタイナー木 (ALENEX’10), … ? その他，基礎的な操作 – 最短路と仲間 (いっぱい), トポロジカルソート (ALENEX’11), 直径, … 13
  • 15. 最短経路クエリ処理 1. 前処理 前計算 データ 活用 2. クエリ処理 「本郷から駒場」 「30 分です」 「中野から秋葉原」 「20 分です」 「札幌から那覇」 「7 時間です」
  • 16. 道路ネットワークでの最短路クエリ ? 構造を活かしやすい ? 様々な効率的な技法 有名な手法 ? A*, ALT [HNR’72, IHI+’94, GH’05, …] ? Reach Pruning [Gut’04, …] ? Highway Hierarchy […] ? Transit Nodes […] 最新の手法 ? Highway Dimension [Abraham+, SODA’10] + ? Hub-Based Labeling Algorithm [Abraham+, SEA’11] 15
  • 17. Dijkstra → 双方向 Dijkstra Dijkstra 双方向 Dijkstra s t s t 最短路が得られている 両側からやると 頂点が広がってゆく 余計な頂点が減る． アルゴリズム． 16
  • 18. 三角不等式 ? ???????????? ??????, ?????? ? グラフ ?????? 上での ??????, ?????? の最短距離 ? ???????????? ??????, ?????? ≤ ???????????? (??????, ??????) + ???????????? (??????, ??????) ? ???????????? ??????, ?????? ≥ ???????????? ??????, ?????? ? ???????????? (??????, ??????) ★今回はこっち(下界) (?????? は任意の頂点)
  • 19. A*, ALT アルゴリズム A* ALT s v s t t l 人工知能等の探索でもお馴染み． ランドマークの頂点を用意． 近そうなところから探索． そこからの距離と三角不等式で 距離の下界を推定し A*． この辺は実装が楽，速度はそこそこ． (state-of-the-art と比べると全然) 18
  • 20. 双方向 Dijkstra + Reach Pruning の効果 Dijkstra 双方向 Dijkstra 双方向 RE [http://research.microsoft.com/en-us/people/goldberg/hwd.pdf] やばすぎ！効果絶大！ 19
  • 21. Highway Dimension [Abraham+, SODA’10] ? これらの手法はヒューリスティクスだった – 「なんとなく」うまくいきそうな手法 – 実験してみるとたしかにうまくいく ? うまくいくことを解析したい！ → 道路ネットワークを数理的にモデル化 ? 道路ネットワーク ≒ “Highway Dimension” の 小さいグラフ [Abraham+, SODA’10] 「ある程度の距離になる最短路は， 必ず限られた頂点のどれかを通る」 （限られた頂点≒大都市的な． で，Highway Dimension が小さい ≒限られた頂点集合が割りと小さい．定義はもっとフォーマル） 20
  • 22. Hub-Labeling Algorithm [Abraham+, SEA’11] ? Hub-Labeling Algorithm – DB 界隈で 2-Hop と呼ばれるものと同じ – 各頂点に関して，中継点候補を前計算 あらゆる頂点対について， 最短路を与える共通の頂点対が 存在するようにしておく 前計算アルゴリズムの性能で， 中継点のサイズが違ってきて， 小さくできるほど良い ? Highway Dimension が小さいというモデルで解析をする と，これが凄い速そう → 少し工夫して実装してみたら実際爆速!! 21
  • 23. Hub-Labeling Algorithm [Abraham+, SEA’11] はやいｗｗｗｗ 5 ランダムアクセスぐらい？ 22
  • 25. 会議と話題 ? DB 系の会議: SIGMOD, VLDB, ICDE, CIKM, EDBT, … – Web, IR 界隈とも近い – インダストリアルとの距離が近い – プラクティカルな話題が多い ? グラフデータベース，分散グラフ処理系 ? グラフアルゴリズム – パターン検索，コミュニティ抽出，頻出パターン抽出 – RDF のクエリ処理，構造のある検索 – Uncertain Graph 上での各種処理 (枝に不確定性) – 到達可能性クエリ，最短路クエリ (亜種もいっぱい) 24
  • 30. 最短路クエリの応用例 ? Social Search – Social Network: 人を頂点，枝を友人関係 ? Context-Aware Search – Web Graph: ページを頂点，枝をリンク これらのグラフ上での最短距離を 結果のランキングの指標に使う
  • 31. 复雑ネットワークでの最短路クエリ ? 構造がカオス ? 交通ネットワークと比べ難しい 有名な手法 ? 2-HOP [Cohen+, SODA’02] [Cheng+, EDBT’09] ? 対称性の活用 [Xiao+, EDBT’09] ? ランドマーク系 (近似) [Potamias+, CIKM’09] [Das Sarma+, WSDM’10] [Gubichev+, CIKM’10] 最新の手法 ? 木分解による Core-Fringe 構造の活用 [Wei, SIGMOD’10] [Akiba+, EDBT’12] ← Christian さん 河原林先生 → 30
  • 32. 三角不等式 ? ???????????? ??????, ?????? ? グラフ ?????? 上での ??????, ?????? の最短距離 ? ???????????? ??????, ?????? ≤ ???????????? (??????, ??????) + ???????????? (??????, ??????) ★今回はこっち(上界) ? ???????????? ??????, ?????? ≥ ???????????? ??????, ?????? ? ???????????? (??????, ??????) (?????? は任意の頂点)
  • 33. 上界による最短距離推定 (単一ランドマーク) ? ???????????? ??????, ?????? ≤ ???????????? (??????, ??????) + ???????????? (??????, ??????) ★ u これをそのまま使う s t 1. 前処理 – 頂点 ?????? を1つ選ぶ（ランドマーク） – ???????????? (?, ??????), ???????????? ??????,? を全頂点に対し前計算しておく (幅優先探索) 2. クエリ処理 ???????????? ??????, ?????? = ???????????? ??????, ?????? + ???????????? (??????, ??????)
  • 34. 上界による最短距離推定 (複数ランドマーク) ランドマークを単一 (?????? ) から複数 (??????) にしよう ? ???????????? ??????, ?????? ≤ ???????????? (??????, ??????) + ???????????? (??????, ??????) ★ 複数頂点に使う s t 1. 前処理 – 一定数の頂点集合 ??????を決める（ランドマーク） – 各 ?????? ∈ ??????に対し ???????????? (?, ??????), ???????????? ??????,? を全長点に対し前計算 (BFS) 2. クエリ処理 ???????????? ??????, ?????? = min{ ???????????? ??????, ?????? + ???????????? (??????, ??????)} ??????∈??????
  • 35. ランドマークの選択 ? ランドマークの選び方で近似性能が大きく変わる – ベースライン：ランダム ? 実は次数が大きいものから選ぶだけで良くなる！ [Potamias+’09] – 他にも Closeness Centrality や Graph Partitioning を使う方法 – 労力の割に大差ないかも [Potamias+’09, Table2] 34
  • 36. 複雑ネットワークの Core-Fringe 構造 [Lu’00] 複雑ネットワークは 以下の 2 つ (3 つ) に分けられる ? 密な “Core” Core ? 木に近い “Trails” ? (“Middle Layer”) Fringe よりフォーマルには，モデル (恣意的な可視化) の仮定のもとで証明可 35
  • 37. 木分解の活用 [Wei’10], [Akiba+’12] 木分解 ? グラフ → 頂点集合の木 ? どちらかというと理論界の道具 ? グラフが“木っぽい”とオイシイ (よりフォーマルには木幅が小さいと良い) 複雑ネットワーク ? 全体としては木っぽくない ? しかし Fringe 部分は木っぽい！ – 木分解してウマウマ ? Core はやっぱしんどい – 諦めるor頑張る 36
  • 38. 木分解の活用 [Akiba+’12] 数 M 頂点?辺ぐらいまでなら厳密解で爆速クエリ処理 クエリ時間 (μs) それ以上はシンドイので，近似手法と組み合わせる （5 M 頂点，70 M 辺 → 数十 μs，数％エラー） 37
  • 40. 会議と話題 ? HPC 系の会議: SC, ICS, ISCA, … ? 話題 （全て並列or分散） – 連結成分分解 – BFS, SSSP (最短路) – Eigenvector (PageRank, HITS) –… 特に IBM と LLNL 辺りが力いれてる SC? でバイオリンを弾く 平木先生 39
  • 41. 並列?分散環境でのグラフアルゴリズム グラフアルゴリズムの性質 ? ランダムなアクセスパターン ? データの再利用がない → 時間的局所性?空間的局所性の両方が超低い ? 並列化はとても難しい – 簡単には逐次を超えられない 40
  • 42. Graph 500 日本では CREST スパコンのベンチマーク (超デカいグラフ) のチームの方々 ? 現在 BFS のみ でやっています ? 次に SSSP が入るという噂 ? 更にその次は極大独立集合 ? グラフは難しいので，ベンチマークとしては逆に良い – Top 500 の LINPACK は “簡単” ? ? 将来の需要も考慮 ? 現状，アルゴリズム?実装の優劣も大きく影響 – 配られてるリファレンス実装はスケールしない – まだまだアプローチに「決定版」がない – アツい！ （しかしスパコンのベンチマークになっているかは謎） 41
  • 43. 並列 BFS (共有メモリ) 並列 BFS の基本アルゴリズム 1. キューに始点入れる 2. キューが空でない間: ←このループを並列に – キューから頂点 v だす – v に隣接する全頂点で未訪問のものをキューに追加 42
  • 44. 並列 BFS (共有メモリ) の最適化 [Agarwal+’10] 基本 ? 到達したかのフラグをビットセットに – キャッシュミス減 ? ロックする前に値みてからロック ソケット超えの最適化 ? ソケットごとにキューを別に (inter-socket queue) – ソケット内での push とソケット外への push を別に – ソケット外から push されたのは後でまとめて処理 – 良い感じの lock-free queue ? Inter-socket キューの処理の batching – 何個か頂点まとめて push/pop → 通信を整理
  • 45. 実験結果 (性能向上) Nehalem-EX 8 コア × 4 ソケット (= 32 コア) [Agarwal+’10, Figure 5]
  • 46. 分散 BFS (クラスタ) [Buluc+’11]他 繰り返す 1 次元分割 × = 隣接行列 距離 i で到達可能な 距離 i+1 で到達可能な 頂点集合 頂点集合 全体全通信が必要となりスケールしない 45
  • 47. 分散 BFS (クラスタ) [Buluc+’11]他 繰り返す 2 次元分割 ■ ■ ■ ■ ■ ■ × = + ■ ■ ■ ■ ■ ■ 隣接行列 距離 i で到達可能な 距離 i+1 で到達可能な 頂点集合 頂点集合 通信が √n 倍程度減る (n はノード数) （しかし，これをベースに頑張り 40K コア使っても， SMP 32 コアの数十倍程度とかだったりしたりしなかったり…？) 46
  • 48. 終わりです：まとめ ? アルゴリズム界隈の話題： 道路ネットワーク – A*, ALT, Highway Dimension, Hub-Labeling ? DB 界隈の話題：複雑ネットワーク – Landmark, Core-Fringe Tree-Decomposition ? HPC 界隈の話題：並列分散 – ソケット超えの最適化，1D/2D 分割法 ありがとうございました （?__________?）／ 47
  • 49. 宣伝 48
  • 50. 宣伝 第二版が出ます!! ? 4 つの新トピック – 計算幾何 – 枝刈り探索 – 分割統治法 – 文字列アルゴリズム ? 練習問題コーナー ? 発展内容コーナー 49
  • 51. 宣伝 第二版が出ます!! ? 4 つの新トピック – 計算幾何 – 枝刈り探索 – 分割統治法 – 文字列アルゴリズム ? 練習問題コーナー ? 発展内容コーナー よろしくお願いします！ 1/27 発売！ 50