データグラフ ( 外部記憶 ) 主記憶 S 1 S 2 読み込んだ部分グラフ部分解を格納解と成り得る部分解集合 A さん C さん c 近況 Bさん u 動画 u s D さん E さん s c 写真 u c s (b) 出力完全解集合 (a) Facebook 3: データグラフ ( 外

Size: px

Start display at page:

Download "データグラフ ( 外部記憶 ) 主記憶 S 1 S 2 読み込んだ部分グラフ部分解を格納解と成り得る部分解集合 A さん C さん c 近況 Bさん u 動画 u s D さん E さん s c 写真 u c s (b) 出力完全解集合 (a) Facebook 3: データグラフ ( 外"

ゆみかいざわ
5 years ago
Views:

1 DEIM Foum 2017 E E-mai: RDF 1. Web SNS subgaph isomophism. [1] [2] Umann [3] Umann VF2 [4] QuickSI [5] GaphQL [6] GADDI [7] SPath [8] [9] (extena memoy agoithm) [15] I/O I/O [10] [11] [12] 1 S 1 S 1 S

2 データグラフ ( 外部記憶 ) 主記憶 S 1 S 2 読み込んだ部分グラフ部分解を格納解と成り得る部分解集合 A さん C さん c 近況 Bさん u 動画 u s D さん E さん s c 写真 u c s (b) 出力完全解集合 (a) Facebook 3: データグラフ ( 外部記憶 ) 1: S 1 S 2 読み込んだ部分グラフ主記憶ノードとエッジの情報を追加部分解集合部分解を残す A C B A C B D E D B B u C c D s E s E u 出力削除 4: 2. 1 完全解集合 2: 2 マッチできなかった () G = (V, E) V E () v V v V e E e = v v e = v v e v, v v v e v v v V L in (v)l out (v) G = (V, E) G = (V, E ) V = V E = E G G 3 Facebook P = (V p, E p ) G = (V, E) u u E p f(u) f(u ) E f : V p V P G

3 5 6 v 1 v 1 v 2 v 1 v 3 5: S 1 7 V in = {v 1, v 2, v 6} {(v 2 v 1), (v 2 c v 3), (v 5 v 6), (v 6 s v 1), (v 7 v 6)} b ) S 1 S 1 S 1 V bn 7 V bn = {v 3, v 5, v 7} {(v 2 c v 3), (v 6 s v 1), (v 7 v 6)} c ) S 1 S 1 S 1 v out x v out v 1 v 3 v 1 v 2 7 v 4 v 4 v 5 {(v 5 x v out)} v 2 v 1 v 2 u v 4 v 2 v 3 v 2 v 8 v 3 v 2 v 3 c v 4 v 6 s v 4 v 6 u v 5 v 6 s v 7 v 8 v 2 v 8 v 6 v 3 v 1 v 4 c v 3 v 4 s v 6 v 4 u v 2 v 5 u v 6 v 6 v 8 v 7 s v 6 v 8 c v 7 (a) v 7 c v 8 (b) 7: 6: S 1 S 1 7 S 1 a ) S 1 V in 3. 2 K S 1 M M S Agoithm 1 3 K 5 6

4 GetBNnodes Agoithm 2 u u 1 v M (u 1, v) M SubgaphSeach SubgaphSeach Agoithm 3 Agoithm 1 : P = (V P, K, E P ) G = (V, E) : M M 1: S 2 = 2: whie G do 3: G K S 1 4: V in = V (S 1 ) 5: V bn = GetBNnodes(S 1, P ) 6: fo each v V (S 1 ) do 7: if L out (v) = L out (u 1 ) o L in (v) = L in (u 1 ) then 8: M (u 1, v) M 9: M = 10: SubgaphSeach(P, S 1, M, M ) M v M Agoithm 3 SubgaphSeach : P = (V P, K, E P ) G = (V, E) : M M 1: if M v outm x then 2: M M 3: ese if M v out M x then 4: M M S 2 5: ese 6: u V p 7: fo each v V in do 8: if IsJoinabe_I(P, S 1, M.M, u, v) M tmp then 9: (u, v) M v v M tmp M 10: SubgaphSeach(P, S 1, M, M ) 11: (u, v) M v v M tmp M 12: fo each v V bn do 13: if IsJoinabe_B(P, S 1, M.M, u, v) M tmp then 14: (u, v) M v v M tmp v x v M tmp M Agoithm 2 GetBNnodes : P = (V P, K, E P ) G = (V, E) : V bn 1: fo each v v V (S 1 ) do 2: if v V (S 1 ) but v / V (S 1 ) then 3: v V bn 4: ese if v V (S 1 ) but v / V (S 1 ) then 5: v V bn 15: SubgaphSeach(P, S 1, M, M ) 16: (u, v) M v v M tmp v x v M tmp M 17: if v = v outisjoinabe_o(p, S 1, M.M, u, v) M tmp then 18: (u, v) M v x v M tmp M 19: SubgaphSeach(P, S 1, M, M ) 20: (u, v) M v x v M tmp M 6: etun V bn IsJoinabe_I u v SubgaphSeach 14 M M v out x 12 M M 34 M M S 2 6 u IsJoinabe_I Agoithm IsJoinabe_B Agoithm IsJoinabe_O Agoithm 6 u v u u E p (u, v ) M u v v (v v ) M tmp u u E p (u, v ) M u v v (v v) M tmp IsJoinabe_B u v IsJoinabe_I x x u u E p u v

5 v (v x v ) M tmp u u E p u v v (v x v) M tmp Agoithm 4 IsJoinabe_I : P = (V P, K, E P ) G = (V, E) u V p y V (S 1 ) : M tmp 1: M tmp = 2: fo each u u E p (u, v ) M do 3: if v V in V bn v v E(S 1 ) then 4: v v M tmp 5: continue 6: ese 7: etun 8: fo each u u E p (u, v ) M do 9: if v V in V bn v v E(S 1 ) then 10: v v M tmp 11: continue 12: ese 13: etun 14: etun M tmp Agoithm 5 IsJoinabe_B : P = (V P, K, E P ) G = (V, E) u V p y V (S 1 ) : M tmp 1: M tmp = 2: fo each u u E p (u, v ) M do 3: if v V in v v E(S 1 ) then 4: v v M tmp 5: continue 6: ese if v V bn {v out} then 7: v x v M tmp 8: continue 9: ese 10: etun 11: fo each u u E p(u, v ) M do 12: if v V in v v E(S 1 ) then 13: v v M tmp 14: continue 15: ese if v V bn {v out} then 16: v x v M tmp 17: continue 18: ese 19: etun 20: etun M tmp IsJoinabe_O u x u u E p u v v (v x v ) M tmp u u E p u v v (v x v) M tmp Agoithm 6 IsJoinabe_O : P = (V P, K, E P ) G = (V, E) u V p y V (S 1 ) : M tmp 1: M tmp = 2: fo each u u E p(u, v ) M do 3: if v V bn {v out} v v E(S 1 ) then 4: v x v M tmp 5: continue 6: ese 7: etun 8: fo each u u E p(u, v ) M do 9: if v V bn {v out } v v E(S 1 ) then 10: v x v M tmp 11: continue 12: ese 13: etun 14: etun M tmp P G P u 1, S 1 v 4 v 6 u 1 M M 1 = {(u 1, v 4)} M 2 = {(u 1, v 6)} M SubgaphSeach M S 1 V in V bn V in = {v 1, v 3, v 4, v 5, v 6 } V bn = {v 2, v 7, v 10 } S 1 {v 1 v 4, v 1 s v 10, v 2 c v 3, v 2 v 4, v 5 v 6, v 5 u v 7, v 7 v 6 } M 1 S 1 M 1 M 2 v 5 v 6 v 7 v 6 x v out M 2 S 2 (M 1, M 1) (M 2, M 2)

6 8: M 1 ={(u 1, v 4 )(u 2, v 1 )(u 3, v 2 )(u 4, v 3 )} M 1={(v 1 v 4 )(v 2 v 4 )(v 2 c v 3 )} M 2 ={(u 1, v 6 )(u 2, v 5 )(u 3, v 7 )(u 4, v out )} M 2={(v 5 v 6 )(v 7 v 6 )(v 7 x v out )} Agoithm Agoithm 7 2 : P = (V P, K, E P ) G = (V, E) S 2 M M : M M 1: 215 2: whie G do 3: G K S 1 4: fo each (M, M ) S 2 do 5: if M v out M x then 6: M M 7: ese 8: fo each u u E p do 9: if (u, v) Mv = v out (u, v ) Mv = v out v v E(S 1 ) then 10: (u, v) M (u, v ) 11: v x v M v v 12: ese if (u, v) Mv = v out (u, v ) Mv = v out v v E(S 1 ) then 13: (u, v ) M (u, v ) 14: v x v M v v 15: S 2 M M M M v out x S 2 M M v out x v 911 M u v v out v v v out S 1 v out v v v v v v v x v 1214 M u v v out v v v out v v (u v ) (u v ) v v v x v M M (M 2, M 2) G S 1 S 1 {v 2 c v 3v 2 v 4v 5 u v 7v 7 v 6v 7 c v 8v 9 s v 8} v 7 x v out Agoithm u 3 c u 4 (u 3 v 7) M M x v out 1214 v 7 v 7 c v 8 (u 4v out) (u 4v 8) v 7 c v 8 v 7 x v out (M 2M 2) (M 2M 2) (M 2M 2) 9: K 56 M 2 ={(u 1 v 6 )(u 2 v 5 )(u 3 v 7 )(u 4 v out )}

7 M 2={(v 5 v 6 )(v 7 v 6 )(v 7 x v out )} M 2 ={(u 1 v 6 )(u 2 v 5 )(u 3 v 7 )(u 4 v 8 )} M 2={(v 5 v 6 )(v 7 v 6 )(v 7 c v 8 )} 3. 4 I/O I/O B [13] I/O I/O O(sot( E )) I/O Agoihtm 1 3 K S < = S 1 K I/O O(S/B) I/O O ( S B E ) S = O ( ) E B I/O Agoithm 8 3 I/O I/O ( S O B E ) ( ) E = O S B Agoithm 7 1 E p 1 I/O ( ) E Ep O B I/O 4. ( ) E Ep O B (1) (2) (3) SP 2 Bench [14] SP 2 Bench Notation3 SP 2 Bench n DBLP SP 2 Bench 559MBn=5,000,000 5,644MBn=50,000, : SP 2 Bench n (MB) 5,000, ,000,632 10,000,000 1,105 10,000,457 20,000,000 2,259 20,000,629 30,000,000 3,386 30,025,978 50,000,000 5,644 50,042, Edito edito edito Jouna Poceeding pubishe Pubishe 10: 4. 2 CPU: Inte Xeon E v3 3.0GHz : 16GB RAM OS: Linux CentOS 7 (64bit) : C++ uimit 4G K=200,000 CPU $sudo sh -c "echo 3 > /poc/sys/vm/dop_caches" Sab 11

8 最大主記憶使用量 (MB) 実行時間 (s) 解の数 ( 個 ) ,000 2,000 3,000 4,000 5,000 6,000 7,000 8,000 9,000 10,000 11,000 12,000 入力ファイルのサイズ (MB) 部分解完全解 11: time ,000 2,000 3,000 4,000 5,000 6,000 7,000 8,000 9,000 10,000 11,000 12,000 入力ファイルのサイズ (MB) 12: 3,000 2,500 2,000 1,500 1, ,000 2,000 3,000 4,000 5,000 6,000 7,000 8,000 9,000 10,000 11,000 12,000 入力ファイルのサイズ (MB) 13: /us/bin/time -f "%M KB" 13 4G 11G 5. [1],,,,, 104(669), PRMU , pp , [2],,,, J.Comput. Chem. Jpn., 2(4), pp , [3] J.R. Umann, An agoithm fo subgaph isomophism, J. ACM, 23(1), pp.31 42, [4] L.P. Codea, P. Foggia, C. Sansone, and M. Vento, A (sub) gaph isomophism agoithm fo matching age gaphs, IEEE Tans. PAMI, 26(10), pp , [5] H. He and A. K. Singh, Cosue-tee: An index stuctue fo gaph queies, Poc. ICDE, pp.38 49, [6] Huahai He, Ambuj K. Singh. Gaphs-at-a-time: quey anguage and access methods fo gaph databases, Poc. SIG- MOD, pp , [7] Shijie Zhang, Shiong Li, Jiong Yang, GADDI: distance index based subgaph matching in, bioogica netwoks, Poc. EDBT, pp , [8] Peixiang Zhao, Jiawei Han, On gaph quey optimization in age netwoks, PVLDB, 3(1), pp , [9] Lee, Jinsoo, et a. An in-depth compaison of subgaph isomophism agoithms in gaph databases, PVLDB, 6(2), [10] Zhiwei Zhang, Jeffey Xu Yu, Lu Qin, Lijun Chang, and Xuemin Lin. I/O efficient: Computing sccs in massive gaphs, VLDB Jouna, 24(2), pp , [11] Zhiwei Zhang, Jeffey Xu Yu, Lu Qin, Qing Zhu, and Xiaofang Zhou. I/O cost minimization: eachabiity queies pocessing ove massive gaphs, Poc. EDBT, pp , [12] Xiaocheng Hu, Yufei Tao, and Chin-Wan Chung. Massive gaph tianguation, Poc. SIGMOD, pp [13] Jeffey Scott Vitte. Agoithms and Data Stuctues fo Extena Memoy, Foundations and Ts in Technoogy, Now Pubishes, [14] Michae Schmidt, Thomas Honung, Geog Lausen, and Chistoph Pinke. SP2Bench: a SPARQL pefomance benchmak, Poc. ICDE, pp , [15] Fancesco Sivesti. Subgaph enumeation in massive gaphs, CoRR, abs/ ,

2

2 485 1300 1 6 17 18 3 18 18 3 17 () 6 1 2 3 4 1 18 11 27 10001200 705 2 18 12 27 10001230 705 3 19 2 5 10001140 302 5 () 6 280 2 7 ACCESS WEB 8 9 10 11 12 13 14 3 A B C D E 1 Data 13 12 Data 15 9 18 2

データグラフ ( 外部記憶 ) 主記憶 S 1 S 2 読み込んだ部分グラフ 部分解を格納 解と成り得る 部分解 集合 A さん C さん c 近況 Bさん u 動画 u s D さん E さん s c 写真 u c s (b) 出力 完全解集合 (a) Facebook 3: データグラフ ( 外

データグラフ ( 外部記憶 ) 主記憶 S 1 S 2 読み込んだ部分グラフ部分解を格納解と成り得る部分解集合 A さん C さん c 近況 Bさん u 動画 u s D さん E さん s c 写真 u c s (b) 出力完全解集合 (a) Facebook 3: データグラフ ( 外