A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs

Ruoming Jin, Ning Ruan, Yang Xiang, and Victor Lee. 2012. A highway-centric labeling approach for answering distance queries on large sparse graphs. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12). ACM, New York, NY, USA, 445-456. DOI=10.1145/2213836.2213887 http://doi.acm.org/10.1145/2213836.2213887

  • 問題
    • 厳密・近似最短路クエリ
    • 複雑ネットワーク系
  • 手法概要
    • 1 つツリー T を作ります
    • 2-hop みたいに基本的には各頂点に L_in, L_out = {(頂点, 距離), ...} を計算（ラベル）
    • ただし，2-hop とちがって，d_G(x, l1) + d_T(l1, l2) + d_G(l2, y) ってやるらしい
      • d_G はグラフ中の距離で，ラベルに含まれるもの．d_T はツリー内の距離．
  • 前処理
    • ツリーの作り方
      • 最短路木 with Maximal Cover
      • 有向全域木 on Edge-Betweenness
    • ラベルの計算しかた
      • N^2 通りのペアが全てカバーされるようにラベルを選ぶ
      • どのペアを選んだ時に満たされるか，みたいなので厳密にしたり近似値保証付きの近似にしたりできる
      • 適当に
  • クエリ
    • 普通にやると O(|L_out^v| * |L_in^w|) になりそうだが，O(|L_out^v| + |L_in^w|) にできる
    • まぁできるだろうなぁ
  • 実験
    • WIkiVote 7115/103689
    • label size 323444
    • query time 2817 / 100000 ms (BFS の ３倍速ｗ）
    • label time 1003 seconds,
    • ワロス