Shortest Path Computation on Air Indexes - todo314 @ ウィキ

Shortest Path Computation on Air Indexes

• Georgios Kellaris, Kyriakos Mouratidis
• VLDB 2010

• 某所スライドより

概要（だけ）

• 無線環境における最短経路
• グラフ：road network
• 2手法提案

1. EB法（楕円境界法）

• ノード群を領域に分割（kd木
• 領域間の距離のminとmaxをもっておく（事前計算
• s-t間の最短経路は？？？
• R(s),R(t)をs,tが含まれる領域とすると
  • min(d(R(s), R)) + min(d(R, R(t))) ≦ max(d(R(s), R(t)))なRを通るかも！

1. NR法

• 最短経路で通る領域をもっておく？謎
• EB法よりも高性能らしい