Approximate Shortest Distance Computing: A Query-Dependent Local Landmark Scheme

Miao Qiao, Hong Cheng, Lijun Chang and Jeffrey Xu Yu, "Approximate Shortest Distance Computing: A Query-Dependent Local Landmark Scheme", Accepted by the 2012 IEEE International Conference on Data Engineering (ICDE 12). 2012.


Miao Qiao, Hong Cheng, and Jeffrey Xu Yu はここ 2 年で DB 系会議に最短路系の論文 2 本だがウーンどちらもそこまでお気に入りではない

  • 問題
    • 最短路クエリ．
    • オンメモリ．
    • 実験は一応，複雑ネットワークと road network 両方
  • アプローチ
    • landmark-based SPT
    • local landmark scheme!!!!!! って言っているものは SPT の LCA のこと
      • そういうのは他の人たちも既にやっている． 少なくとも path-sketch の人達とその後の fully dynamic の人達．
      • LCA に RMQ を使えばいいよ!!! って言ってる．road network はたしかにそれ効果ありそうだけど，直径小さいネットワークは意味ないと思うが．
      • というか，local search scheme に発展させたとき結局クエリ時パスを作るので，そっちに至ってはもはや高速に LCA を計算する意味は…
    • optimization techniques
      1. graph compression
        • 完全にツリーになってるところをつぶすのと，パスになってるとこをつぶす
        • 最近みんなまえ処理に graph compression いれてるね
      2. local search
        • ランドマークからの SPT 使って最短路候補いっぱいもとまる（１SPTにつき１こ）
        • それらのパスをくっつけまくって，それを幅 1 ふくらませ，その上で最短路を求める感じ
  • 実験結果
    • 最大の複雑ネットワークは Flickr で 1.8M / 23M (僕も使ったやつだ)
    • もっとスケールするだろうになんで LiveJournal とか Twitter とかやらないのかな
    • Local Search して，数ms，エラー 0.004 とか 0.0005 とか．
      • Fully Dynamic の人達より，早くて，エラー小さい!! ぱねえ
      • 彼らも Local Search と似たようなことをしている気がするがちょっと違う？ Graph Compression がすごい？
        • graph compression は枝数はあまりかわらなくて，頂点数は 1/3 になったりしてるかんじっぽい…
      • ただ Fully Dynamic の人達のほうが実験が大きいのでそれは関係するか？