On k-skip Shortest Paths

On k-skip Shortest Paths

  • Yufei Tao, Cheng Sheng, Jian Pei
  • SIGMOD 2011

概要

  • k-skip coverを考えた
    • 要はk-shortest pathのhitting set
  • 色々使えそう
  • 理論的な解析とそこそこ速そうなアルゴリズム

問題定義とか

k-skip Shortest Paths

  • SP(s,t)をs-t間の最短経路とし,その順番をv_1,v_2,…,v_lとする
  • P*が以下を満たすならs-t間のk-skip shortest path
  • ∀i P*∩{v_i,…,v_{i+k-1}}≠∅
  • つまり,どの連続するk頂点を選んでも,どれかひとつ以上はP*に含まれている

k-skip Cover

  • V*がk-skip coverであるとは,
  • 任意のs,tに対し,V*∩SP(s,t)がk-skip SPである
  • どの最短路もV*でk-skip cover

k-skip Graph

  • 元のグラフを上手いこと反映するk-skip coverを頂点とするグラフを作りたい
  • 単に辺を取り除くだけでは駄目
  • s,t∈V*の(G上の)最短経路がV*以外の頂点を(端点を除いて)含まない場合
  • s-t間に新しいsuper-edgeを張る
    • 感覚的には,これで良さそう.V*上の任意の2頂点間の距離はGでの距離に一致する
  • G*=(V*,E*)がk-skip graphであるとは,
    • V*がGのk-skip cover
    • u∈V*についてE*はvのk-skip neighbor uについて辺(u,v)を持つ

k-skip Graphについて

  • 色々と理論的に解析できる
  • k-skip coverのサイズはO(n/k log n/k)
  • 証明のための道具
  • VC-dimension
    • 学習理論のために使ったり
    • 問題がいかに分解できるか
    • 今回のケースだとこの値が2
  • ε-net
    • hitting setなんだけどヒットするサイズがεn以上,みたいな
    • ε=k/nとすれば今回のケース
  • VC-dimension dならO(d/ε log 1/ε)サイズのε-netがある
    • 適当に書いた
  • しかもこのサイズの頂点集合をランダムに選べば高確率で所望の頂点集合が得られるらしい
    • 確認が大変か?
  • n/kが下界
    • logだけ違うさね

k-skip coverの計算

  • adaptive sampling
  • 適当な順番で各頂点をチェック,必要ならV*に追加
  • 難しいのでここは飛ばす
  • ヒューリスティクスとして高次数順に見る
  • O(n*(k-hop)*log(k-hop))くらいの計算時間
  • k-skip graphの構築
    • がんばれ♡がんばれ♡

適用

  • 最短路クエリ
  • Zoom-in
    • k-skip上で省略された部分を見るよ

実験

  • データセット
    • USA(23M, 58M)が最大
  • 最短路クエリ
    • 3倍くらい速くなった
  • 前処理
    • k-skip cover自体は短そう
    • super-edgeの方が長い
    • kに対して線形よりちょっと速い増加

まとめ

  • 大まかな可視化に使えるねえ
  • kが相当大きい時なんかに使えるかなもっと速くしたいなら

SIGMOD k-skip 最短路クエリ 道路ネットワーク

2013-10-03

最終更新:2014年10月04日 04:43