Hub-Labeling

経路探索に速さを求めて行き着いた先

潤沢なメモリが利用できるなら、どんなノード間でも数nsで最短距離を算出可能

• Hub Labeling Algorithms(pdf)
• 2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化(pdf)

事前計算とクエリに分かれる。「Hubノード」という概念を利用する。

• 事前計算
  • 「Hubノード」を適切に選ぶ
  • 全ノードに対し、いくつかの「Hubノード」までの最短距離を持たせる
• クエリ
  • $s$ から $t$ までの最短経路の距離を求めるとする
  • $s$ と $t$ で共通して持っている「Hubノード」を探し、距離を合算
  • その中で最小のものが最短距離

• そのため「Hubノード」は以下の条件を満たすように選ぶ
  • 全ての2ノードの組で必ず1つは共通Hubノードがある
  • その合計が最短距離となる

(s) s が持つHubノードID  15  23  25  41  ...
    Hubノードまでの距離  10  11   9   6  ...

(t) t が持つHubノードID  11  23  26  41  ...
    Hubノードまでの距離   8  19  11  19  ...
                             ~~      ~~  共通ノードは23,41
                             ↓      ↓  距離を合算
    最短距離は25             30      25

（Hub Labeling Algorithmsより引用）

西ヨーロッパのネットワーク、1800万ノード・2400万リンクで、

• 事前計算に時間のかからない簡単な実装で
  • ノード1つ当たりに持たせる平均Hubノード数: 98
  • メモリ: 22.5GB
  • 計算時間: 700ns
• 頑張ってHubノードを厳選すれば、
  • ノード1つ当たりに持たせる平均Hubノード数: 69
  • メモリ: 17.7GB
  • 計算時間: 508ns

多少重いが、今どき用意できないスペックなんてことは全然無い