Shortest paths in less than a millisecond

Rachit Agarwal, Matthew Caesar, Philip Brighten Godfrey, and Ben Y. Zhao. 2012. Shortest paths in less than a millisecond. In Proceedings of the 2012 ACM workshop on Workshop on online social networks (WOSN '12). ACM, New York, NY, USA, 37-42. DOI=10.1145/2342549.2342559 http://doi.acm.org/10.1145/2342549.2342559

Orkut (2 億 edges) で exact SPQ，ただしごく一部の点対には答えられない

• 問題
  • exact SPQ, 対象のグラフは複雑ネットワーク系
  • ただし彼らは全ての点対に対して答えられなくても良いルール
• アプローチ
  • ほぼ labeling (= 2-hop)
  • 各頂点について，距離を覚える頂点集合のことを vicinity とよんでいる
  • それが ball になるようにしていれば，2 頂点のそれが intersect した時は必ず最短路が求まるので，ball にする
  • 2 頂点のそれが intersect しなかったら，こたえられなかったってことであきらめるｗ
• vicinity の選び方
  • 全部の頂点から等距離にすると微妙らしい
  • そこで，次数に比例した確率で O(m/√n) 個ぐらいの頂点集合 L をランダムに選ぶ
  • 各頂点から，L に至るまでの距離を半径にする
  • そうするとラベルの合計は O(n √n) 個ぐらいになるらしい
  • O(n √n) ぐらいの感じで，ちょうど大半の点対がカバーされるようになるところらしい
    • これは empirically らしい．実験結果はたしかに綺麗にそうなっている．おもれーな．
    • 理論的になにか言えるのかなぁ．
• クエリ
  • ほげほげ
• 実験結果
  • 前処理時間の報告なし…
  • クエリは 0.3 ms ぐらいで，BFS の 2000 倍
  • 99.9% がカバー

特に，多分答えられないのは遠すぎる点対だが，そういうのの正確な距離は実用上あまり意味がないんじゃ．あるいは，遠いほうが得意なやつらがあるから……