Querying shortest path distance with bounded errors in large graphs

Miao Qiao, Hong Cheng, and Jeffrey Xu Yu. 2011. Querying shortest path distance with bounded errors in large graphs. In Proceedings of the 23rd international conference on Scientific and statistical database management (SSDBM'11), Judith Bayard Cushing, James French, and Shawn Bowers (Eds.). Springer-Verlag, Berlin, Heidelberg, 255-273.

  • 問題
    • 最短路クエリ．2 点間．
    • ただし， bounded error にしたい！ したくね？
      • error は additive, ユーザからεを受け取ったらd±ε以下にするっぽい
  • 手法
    • 基本は landmark-based SPQ
    • 頂点 v が landmark l から距離 ε/2 以下だったら，v が l に cover されてるという
    • 全頂点が cover されるように landmark を選べれば bounded error
      • 三角不等式よりすぐわかる
    • でも全部 cover するのは無理ゲーなので割合 CR (cover ratio) までカバー出来れば満足!!!
      • お，おう （bounded とはなんだったのか!!）
      • それでも 1 - (1 - CR)^2 の確率で二点間の距離はエラー ε で収まるらしい…ってまぁそうですな
    • Sec. 4: Graph Partitioning-Based Heuristics
      • 前処理とかはやくするために graph partition 使って局所的にやる．
      • 実験みると精度落ちとる．
  • 実験結果
    • Road Network は…
      • Road Network 用の手法があるのに，そういうのじゃなくて Complex Network 向けの別手法と比べてるのだろう
  • Social Network
    • データ: DBLP (600K / 4.8M)
    • average error は centrality よりちょっと良い…んだけれど，landmark の数が 1000 から 4000
      • centrality (Potamias+) はそんなランドマークの数で使う手法じゃなくて，せいぜい数百
      • そういう凄い数使うのだと，centrality 使って真ん中ばっかよりもっと散りばめた方が有利なので，提案手法の精度が高そうなのはわかる
    • 他は普通

感想

  • bounded error であるならあったほうがいい
  • でも，それは実験部分で全く言及してないのが少し気になる
  • 例えば:
    • centrality ではこれだけ bound を超えちゃうことがありました!!
    • でも，我々の手法では指定した全然 bound を超えない!!　素敵!!
  • 実は centrality でも bound 全然超えなかったのではないかと予想