A hub-based labeling algorithm for shortest paths in road networks
Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011. A hub-based labeling algorithm for shortest paths in road networks. In Proceedings of the 10th international conference on Experimental algorithms (SEA'11), Panos M. Pardalos and Steffen Rebennack (Eds.). Springer-Verlag, Berlin, Heidelberg, 230-241.
数千万頂点の道路ネットワークの二点間の距離を 5 ランダムアクセスの時間で答える神論文．
- 問題
- road networks
- 最短路クエリ
- ベースアルゴリズム
- labeling algorithm (= 2-HOP)
- 各頂点，そこからの最短路が経由し得る頂点集合というのを覚えておき，二頂点間のそれの積集合を経由するパスの距離の最小値として最短路を計算
- label をどうやって計算するか
- 基本的には，Contraction Hierarchies で自分から登って到達できる頂点集合
- これだと，Europe のデータセットで各頂点平均 500 ぐらいになった，154GB ちょっとでかいね
- これを枝刈りして頑張る
- まず，実は contraction hierarchies で足される shortcut edge は実は最短距離じゃないかも，そういうのいらん
- これで平均 133 ぐらい
- 後ろのテクニックつかってもっとがんばると 85 ぐらいになる
- label pruning (stall-on-demand, bootstrapping), label ordering, shortest path covers, label compression, partition oracle, index-free labels...
- テクニック一杯
- まず，実は contraction hierarchies で足される shortcut edge は実は最短距離じゃないかも，そういうのいらん
- クエリ処理を高速にするには (数ランダムアクセスの世界なので大事)
- (頂点, 距離) は別配列にして2つの配列にしたほうが良いらしい
- 頂点が一致しなければ距離はアクセスしないので実はそのほうがキャッシュミスが少ない
- cache line に align
- sentinel
- prefetch to L1
- 配列インデックスでなくポインタ
- (頂点, 距離) は別配列にして2つの配列にしたほうが良いらしい
- 実験結果
- 爆速（前処理はちょっとかかるね，データもちょっとでかいね）
