TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in ...

TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph

  • James Cheng, Silu Huang, Huanhuan Wu, Ada Fu
  • In SIGMOD 2013

概要

  • reachability の高速化
  • Topological foldingとラベリング

Topological folding

なにそれ

  • DAGをトポロジカル順にlevel付
  • G1, G2, …と行くに従い、偶数レベルの頂点だけを残す
    • 到達可能なエッジ間にはエッジを張っておく
  • エッジが変になっているとめんどい

cross-level エッジ

  1. まず
  • u がcross-levelエッジを持つ
  • uの下にu1を追加
  • u→vは、u→u1→vにとする
  1. 次に
  • 奇数levelのvの親par[v]からvの子にエッジを追加
  • 何か複雑になるけど、畳込めるようになるらいい

ラベリング

  • level_in(v): vとvの親ノード
  • level_out(v): vとvの隣接ノード
    • ただし、グラフGi*はvが存在する最後のにする
  • クエリ判定
    • s→t ⇔ label_out(s)∩label_in(t)≠{}

実験

データセット

  • 数十M辺なのがいくつか

比較対象

  • (´つヮ⊂)ウオオww
    • いっぱいだよお
  • PathTree, GRAIL, PWAH8, ScaPathTree, ScaGRAIL

インデックス時間

  • 割と速い
  • グラフによっては負けている

クエリ時間

  • 圧倒的でござる
    • インデックスで負けていたのには圧勝

ラベルサイズ

  • インデックス時間と同じようなノリ
  • 他にも人工データで色々試している

SIGMOD connectivity reachability

2013-10-19 21:12:16 (Sat)

最終更新:2013年10月19日 21:12