On k-skip shortest paths

Yufei Tao, Cheng Sheng, and Jian Pei. 2011. On k-skip shortest paths. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data (SIGMOD '11). ACM, New York, NY, USA, 421-432. DOI=10.1145/1989323.1989368 http://doi.acm.org/10.1145/1989323.1989368

• 問題
  • k-skip shortest path
  • shortest path の頂点集合の部分集合
  • 元のパスにおける位置が k 個以上あいちゃわない
• クエリ
  • K-skip graph の上で最短路を求めるだけ
  • 求めたい頂点が含まれてなければ暫定的に K-skip graph につぎ足してやればいいだけ
• 前処理
  • K-skip graph というものを作る
  • 頂点集合 V* = K-skip cover
    • 任意の二点間の shortest path と and とると k-skip shortest path になる
    • サイズ O(n/k log n/k) のものがそこそこ高速に求められる
  • 辺は k-skip neighbor
    • 二点間の最短路が V* の頂点を通らなければ辺を結ぶ
• 実験
  • どでかい USA ロードネットワーク
  • クエリ 3倍とかぐらいはやくなったらしい，やったねｗ
  • bidirectional とか reach しかつかってない？