On k-Path Covers and their Applications - todo314 @ ウィキ

On k-Path Covers and their Applications

• Stefan Funke, André Nusser, Sabine Storandt
• VLDB 2014
  • best paper award

• スライド見てね

概要

Minimum k-All Path Cover (k-APC)

• 入力
  • 有向グラフ G=(V,E)
  • 整数k
• 出力
  • C⊆V であって，任意の長さkの単純経路πについて，C∩π≠∅
  • minimize |C|

Minimum k-Shortest-Path Cover (k-SPC) [Tao, Sheng, Pei. SIGMOD'11]

• 入力
  • 有向グラフ G=(V,E,c)
  • 整数k
• 出力
  • C⊆V であって，長さkの単純最短経路πについて，C∩π≠∅
  • minimize |C|

応用

• Point of Interest Retrieval
  • 適当なパスがあったとして，そこから例えばk個毎の頂点について，
  • ショッピングモールとかガソリンスタンドとかがあるか知りたい
  • 任意の経路についてうまくいくようにデータ構造を構築すると結局全頂点について計算しないとダメ
  • k-APCについてだけ構築すれば効率的
• Map Simplification
  • 経路をズームアウトとして可視化したいとして，k頂点ごとに直線で結ぶとダサい
  • k-APC上の頂点だけとってくればOK
• Personalized Route Planning
  • 入力がコスト関数（複数）で，クエリにコスト関数の重みがもらえる
  • [Funke, Storandt. ALENEX'13] の手法は3種類以上で既に爆遅
  • k-APCを使って速く出来る

理論的結果

• APX-hard
  • 2より良い定数近似は無理そう
• O(log|OPT|)-近似ができるアルゴリズムがある
  • Vapnik-Chervonenkis (VC) dimension dについて
  • O(d|OPT|log(d|OPT|))-近似アルゴリズムがある
  • k-APC, k-SPCでのVC-dimensionは高々3

k-APCの構築法

• C←V として，適当な順番で各頂点が必要かを調べていく
• vが必要かを調べるために，
  • vからC\{v}を含まない高々長さkの経路を探索
    • 長さkの経路があったらvは必要（v以外の頂点はCに属さないから）
  • ↑で探索した各経路について，今度は後ろに経路を伸ばす
    • vを中間に含む長さkの経路があるかを探索している
  • 2つのフェーズでvが必要と判断されればvは必要ない，Cから削除
• 直感的には…
  • 最初の内はCは大体Vなので，探索が一瞬で終わる
  • 低い次数はあんまり沢山の経路をカバーしないので先に枝刈りしちゃうとよさそう

下限

• 上のはヒューリスティクスだけど，得られた解から頑張ってdisjoint k-pathを探索すればその個数がOPTの下限

Overlay Graph

• G_O(C, E_O)
  • vからwへの経路にCの頂点が含まれていなければ，(v,w)∈E_O
  • E_Oはあんまり無い方がよいので
• 各頂点からBFSしてごにょごにょすればOK

k-SPC

• さっきの方法をそのまま適用すると極小性が保たれない
• vから最短路木を逆に伸ばし，さらにそこから最短路木を伸ばす
  • 爆遅

実験

• kの値を変える
  • kが40とかになると超やばそう
• Personalized Route Planning
  • Cにぶつかるまでs,tからG上でDijkstra，ぶつかった頂点集合それぞれをA(s),A(t)とする
  • A(s)からA(t)はOverlay graph上でDijkstra
  • 10倍速くなった，やったね

まとめ

• best paperになったのは応用の評価に起因するのかしら
• 手法と理論的解析が特に関係ないのが謎い
• Overlay graphはスターがクリークになるので超でかくなるなあ
  • 個人的には|C|+|E_O|を小さくしたい
• 他に応用があるだろうか？
  • 実際に応用して，速くなる，とかの結果が出るタイプだとうれしい
• 可視化したい
• 長さkの経路のサンプリングができれば，hitting setみたいにできるかな？