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 エッジ
-
まず
-
u がcross-levelエッジを持つ
-
uの下にu1を追加
-
u→vは、u→u1→vにとする
-
次に
-
奇数levelのvの親par[v]からvの子にエッジを追加
ラベリング
-
level_in(v): vとvの親ノード
-
level_out(v): vとvの隣接ノード
-
クエリ判定
-
s→t ⇔ label_out(s)∩label_in(t)≠{}
実験
データセット
比較対象
-
(´つヮ⊂)ウオオww
-
PathTree, GRAIL, PWAH8, ScaPathTree, ScaGRAIL
インデックス時間
クエリ時間
ラベルサイズ
-
インデックス時間と同じようなノリ
-
他にも人工データで色々試している
SIGMOD connectivity reachability
2013-10-19 21:12:16 (Sat)
最終更新:2013年10月19日 21:12