Speedup Graph Processing by Graph Ordering - todo314 @ ウィキ

Speedup Graph Processing by Graph Ordering

• Hao Wei, Jeffrey Xu Yu, Can Lu, Xuemin Lin
• SIGMOD 2016

概要

• CPUキャッシュミスを減らす頂点順序を求めたい
• 幅w以内の頂点対間の(共通近傍サイズ)+(辺数)を最大化
• MaxTSPのインスタンスとして1/2w近似アルゴリズム
• ∑(出次数)^2時間
• 沢山実験やって2倍以上の高速化を確認

問題定式化

• 局所性を考慮したスコア関数
• $$ S(u,v) := |\mathcal{N}^-(u) \cap \mathcal{N}^-(v)| + [(u,v) \in E] + [(v,u) \in E] $$
  • 前者: 出近傍を全走査するので、uとvが近いなら同時に出てきて欲しい
  • 後者: 単に辺が張られているなら近いと嬉しい
• 順列φの評価関数 $$ = \sum_{0 < \phi(v)-\phi(u) \leq w} S(u,v) $$
  • 実験では窓幅w=5が良さ気
• 論文中では、「グラフ分割」との違いについてかなり語っているが省略
• 評価関数を最小化する最適解の計算はNP-困難

提案手法

• w=1: maxTSPになる
  • 最良近似算法(3/4近似・O(n^3)時間)は辛さisある
  • 最良近似ヒューリスティクス(1/2近似)を使う
• w>1: やばお
  • maxTSPへの変換を書いているがホントか？
  • どちらにしろこの変換はしない
• 近似算法
  • 戦略: 普通に貪欲するだけ
  • 定理: 1/2w-近似
  • 実際: 評価関数値の下限とか求めて結構良いですよアピール
  • 時間: $$ \mathcal{O}(w \cdot \Delta \cdot n^2) $$でやばお
  • $$ \mathcal{O}( \sum_{v \in V} |\mathcal{N}^+(v)|^2 ) $$: 優先度キュー+各頂点の評価関数を逐次更新(スライド更新的な奴)+細かい頑張り

実験

• データセット: SNAP・KONECTからソーシャル・ウェブ
• 比較手法: linear arrangement, logarithmic arrangementとか色々
• 問題: 近傍クエリ・BFS・DFS・SCC・最短経路・Bellman-Ford・PageRank・支配集合・K-core分解・直径
• 評価関数値: 色々な比較手法よりは流石に良い
• 高速化比: 最大で2倍くらい？
• 実行時間: 2B辺で<2時間

まとめ

• キャッシュとかの辺りをちゃんと書いていてデータベースらしい
• 問題定式化とかアルゴリズムの辺りは結構良さ気
• [Arai-Shiokawa-Yamamuro-Onizuka-Iwamura. IPDPS'16](Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis)との比較は如何に…？

SIGMOD グラフ処理 グラフ順序付け

2016/11/30