ICDE 2016 & WWW 2016 勉強会 Research Session 5A-3: Durable Graph Pattern Queries on Historical Graphs Konstantinos Semertzidis Evaggelia Pitoura 担当 : 楠和馬 ( 同志社大学 )
I. Introduction (1 / 2) } 背景 } 様々なドメインで時間経過につれ変化するグラフがほとんど } グラフの変化を捉えることは様々な分野で求められている } 取り組む問題 } 長期間存在するグラフパタンのクエリの効率化 Ø Durable Graph Pattern } ネットワークに対する理解や諸アプリケーションに必要不可欠 DBLP において共同研究の分析 Facebook における友達関係の分析 } 計算コストが大きい 出現回数が一回だけでも各スナップショットで該当パタンを割り出す 2
I. Introduction (2 / 2) } 提案手法 :DurablePattern Algorithm } グラフスナップショット群をコンパクト表現したグラフを提案 } labeled version graph (LVG) } 各節点, 辺にはグラフ内に存在し続けてきた時間間隔 (lifespan) の注釈付き } Driven by θ-threshold } θ: どのくらいの時間間隔でパタンマッチし続けていたか } 持続性のないサブグラフを考慮しないことでメモリの効率的利用を実現 } 枝切りアルゴリズムにより検索空間の削減 } 無向辺で単一ラベルのグラフにも適用可能 3
II. Problem Definition (1 / 8) } Preliminaries } Σ: ラベル集合 } V: 節点集合 } E: 辺集合 } L:V Σ* ラベリング関数 } G = (V, E, L): 有向ラベル付グラフ } 時間 t : 連続的な時間を意味する離散で連続的な整数値 } G t = (V t, E t, L t ): 時間 t におけるグラフのスナップショット 4
II. Problem Definition (2 / 8) } Preliminaries } lifespan [SLP:2015] : 節点, 辺, ラベルがグラフに存在した期間の集合 Ex) G [0, 4] = {G 0, G 1, G 2, G 3 } (u 7, u 4 ) の辺の lifespan を求める 1. G 0 の時に存在している I = [0, 0] 2. G 2 から G 3 の間で存在している. I = [2, 3] I = {[0, 0], [2, 3]} p 542 Fig. 1 を転載 [SLP:2015] K. Semertzidis, K. Lillis, and E. Pitoura, Timereach: Historical reachability queries on evolving graphs, in EDBT, Brussels, Belgium, March 23-27, 2015, pp. 121 132. 5
II. Problem Definition (3 / 8) } Durable Graph Pattern Query l G = (V, E, L): 静的有向ラベル付グラフ l P = (V P, E P, L P ): ユーザ指定のグラフパタン } Def. Graph Pattern Matching } グラフパタン P にマッチする所与グラフ G のサブグラフ群 m = (V m, E m, L m ) ü 全単射 f = V p V m ü v V P, L P (v) L m (f(v)) ü (u, v) E p, (f(u), f(v)) E m 6
II. Problem Definition (4 / 8) } Durable Graph Pattern Query l P = (V P, E P, L P ): ユーザ指定のグラフパタン l I P : 時間間隔の集合 } Def. Pattern Match Lifespan } 時間間隔の集合 I P から以下のいずれかが最長の lifespan のサブグラフ m collective duration 時間間隔集合の期間の総和 continuous duration 時間間隔集合の中で最長の期間 Ex) I = {[1, 3], [5, 10], [12, 13]} collective duration = 3 + 6 + 2 = 11 continuous duration = max(3, 6, 2) = 6 7
II. Problem Definition (5 / 8) } Durable Graph Pattern Query l G [ti, t j ] : 連続時間 t 6, t 7 中のグラフのスナップショット群 l P = (V P, E P, L P ): ユーザ指定のグラフパタン l I P : 時間間隔の集合 } Def. Durable Graph Pattern Matching n A collective-time durable graph pattern query n collective time が一番大きいパタンを求める n A continuous-time durable graph pattern query n continuous time が一番大きいパタンを求める 8
II. Problem Definition (6 / 8) } Ex) Durable Graph Pattern Matching グラフパタン A continuous-time durable graph pattern query の場合 Match1, Match2 p 542 Fig. 1 を転載 p 543 Fig. 2 を転載 9
II. Problem Definition (7 / 8) } Labeled Version Graph (LVG) l G I : 連続時間 t 6, t 7 } Def. Labeled Version Graph 中のグラフのスナップショット群 } 連続時間 t 6, t 7 中のグラフのスナップショットを単一グラフで表現 VG I = (V I, E I, L I, L u, L e, L l ) V, E, L 全てに lifespan を注釈 メモリ上での注釈の表現 Bit arrary Ex) G [0, 15] } I = 0011100001100111 {[2, 4], [9, 10], [13, 15]} 論理積によりパタンマッチ p 543 Fig. 3 を転載 10
II. Problem Definition (8 / 8) } Labeled Version Graph (LVG) } メモリ上における V, E, L の表現 p 545 Fig. 4(a) を転載 11
III. Durable Graph Pattern Algorithms } Baseline approach } グラフスナップショット群 G I を利用した簡易パタンマッチアルゴリズム G I 全てにおいてグラフパタンを検索する必要がある (Line 3) 計算量が膨大 一つのスナップショットでのみ出現する場合も考慮している (Line 4-8) 多様なパタンの検索や G I が多い場合に候補が膨大 p 544 Algorithm. 1 を転載 グラフのスナップショット間の分析が非効率 12
III. Durable Graph Pattern Algorithms } Durable Graph Pattern Matching } LVG を利用した Durable Graph Pattern Algorithm l 探したいグラフパタンに対して持続性の閾値 θ を設定する 単一のスナップショットでしか出現しないサブグラフをフィルタ可能 l スナップショット群を単一のグラフ (LVG) で表現している Durable Graph Pattern Matching を高速に行うことが可能 p 544 Algorithm. 2 を転載 課題 候補集合 C(p) から節点の効率的な検索 検索空間の削減 C(p1) x x C(p V P ) 耐久性閾値 θ の最適な値の決定方法 13
III. Durable Graph Pattern Algorithms } Time Indexes } TILA, TINLA, TIPLA の三つの Time Index を考案 p 545 Fig. 4 を転載 14
III. Durable Graph Pattern Algorithms } Time Indexes } TILA index 1. 各時間 t に対応したラベル集合 2. ラベル l が付与されている節点リスト 3. 時間 t における LVG を展開 l l 全ての節点の検索が一定な時間で可能 TITA index の記憶領域は V I Σ I T nodes p 545 Fig. 4 (1) を転載 15
III. Durable Graph Pattern Algorithms } Time Indexes } TINLA(r) index } r: ホップ数 } 節点から r 本の辺を辿ることで到達する節点を取得可能 } TINTA(r) index の記憶領域は V I Σ I T bits } CTINLA(r) index } 節点から r 本の辺を辿った時に取得できる各ラベルの lifespan が取得可能 p 545 Fig. 4 (a) を転載 p 545 Fig. 4 (b) を転載 16
III. Durable Graph Pattern Algorithms } Time Indexes } TIPLA index } 時間 t において節点 u からラベル l の組合せごとに到達可能な節点リストを取得可能 } Ex) l 1, l 2, l 3 = l 1 l 2 l 3 } λ path の組合せ総数 N H N = D L! L r! IJK } 経験的に λ = 2 で十分 p 545 Fig. 4 (c) を転載 17
IV. Experimental Eevaluation } DataSet l DBLP *1 l 研究者の共著関係グラフ l 1959 2014 / 年 l YT k [M:2009] l YouTube データセット l 1 37 / 日 } Setting } CPU : Quad-Core Intel Core i7-3820 3.6 GHz } 全ての実験において 1 core のみ利用 } RAM : 64 GB p 548 TABLE I. を転載 *1 dblp, http://dblp.uni-trier.de/ 2016/06/25 閲覧 [M:2009] A. Mislove, Online social networks: Measurement, analysis, and applications to distributed information systems. Rice University, Department of Computer Science, 2009. 18
IV. Experimental Eevaluation } Time Indexes Size and Construction Time p 548 TABLE II. を転載 } Comparison with Baseline p 548 TABLE III. を転載 19
VI. Conclusions And Future Work } まとめ } グラフのスナップショット群を一つのグラフ (LVG) で表現し, 三種の Index を考案することで持続的なサブグラフの高速な検索を実現 } 検索空間を削減する枝切りアルゴリズムを提案 } 今後の展望 } 枝切りアルゴリズムの強力化 } ストリーミンググラフへの対応 20