Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach

Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach, James Cheng, Nanyang Technological University; Yiping Ke, The Chinese University of Hong Kong; Shumo Chu, Nanyang Technological University; Carter Cheng, Nanyang Technological University. SIGMOD'12.

• http://www.se.cuhk.edu.hk/~ypke/VC-index_sigmod12.pdf

SIGMOD 2012

最短路クエリ．on-disk．billion edges で exact query を数 sec なので結構凄い．

基本アイディアは，VertexCover覚えといて，その間の最短距離が簡単にわかると，全頂点間の最短距離も簡単に分かる．

でもそれだけだとうまくいかん（だってVertexCoverとか普通にでかいじゃん）

なので，階層にする．VertexCoverについて縮約したグラフをVertexCover．

階層にするだけじゃなくて，ある階層のグラフに対する子を何個かつくる．各頂点，どれか少なくとも１つのVCには含まれるようにする．メモリに載るまで小さくする．

らしいです．実験結果のとこ階層の数とかそういうデータ少なくともパッと見で表がないので感覚がつかめん!!（憤怒）

とにかく時間は割と良いと思う，凄いね． 速くなったとか新しいトレードオフというだけじゃなくて，そこそこ複雑そうなフレームワークながらon-disk でも効率的に動くアルゴリズムを作ってスケールをどーんと伸ばしてるのもすごい．見習いたい．

on-disk になると数秒とかのクエリが許されるからずいぶんと計算でできることかわってくるな

追記

exact query じゃなかった．一頂点から全頂点への距離を求めるというクエリだった．

これ on-disk 数秒はすごいとおもうが，でも一方で数秒だとインタラクティブなシチュエーションだったりなんかのビルディングブロックだったりするときは耐えられないので，やることは尽きない．