一種基于拓?fù)湫蛄衅ヅ涞挠邢驁D

1、一種基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法的設(shè)計與實(shí)現(xiàn)指導(dǎo)老師：呂建華學(xué)生： 羅丹學(xué)號： 71107304大綱 背景意義 問題描述 基本思路 關(guān)鍵算法 實(shí)驗(yàn)結(jié)果 總結(jié) 致謝2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法2背景意義 與其它數(shù)據(jù)結(jié)構(gòu)相比，圖能夠表達(dá)更加豐富的語義，它能夠很好的建模存在多種關(guān)聯(lián)的數(shù)據(jù)，以及表示內(nèi)部具有拓?fù)浣Y(jié)構(gòu)的數(shù)據(jù)。 豐富的語義和復(fù)雜的內(nèi)部結(jié)構(gòu)增加了各種查詢算法的難度，使得傳統(tǒng)的數(shù)據(jù)查詢和處理算法無法繼續(xù)適用或高效處理。2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法3背景意義 目前，大多數(shù)的圖查詢算法的思路： 優(yōu)缺點(diǎn) 本文提出了一種基于拓?fù)湫?/p>

2、列匹配的有向圖子圖同構(gòu)的過濾算法，使得每個圖都對應(yīng)于一個獨(dú)立的序列。2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法4圖形數(shù)據(jù)庫圖形數(shù)據(jù)庫G G候選結(jié)果集候選結(jié)果集CLCL結(jié)果集結(jié)果集RSRS過濾規(guī)則過濾規(guī)則子圖同構(gòu)檢測子圖同構(gòu)檢測過過 濾濾驗(yàn)驗(yàn) 證證問題描述 給定有向圖數(shù)據(jù)庫D=g1,g2,gn和查詢圖q，找出D中所有以q為子圖的gi。2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法5基本思路2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法6關(guān)鍵算法 分層拓?fù)渌惴?序列匹配算法頂點(diǎn)標(biāo)簽唯一DAG頂點(diǎn)標(biāo)簽可重復(fù)DAG 環(huán)路處理算法2022-3-22基于拓?fù)湫蛄衅ヅ?/p>

3、的有向圖子圖同構(gòu)過濾算法7分層拓?fù)渌惴ǚ謱油負(fù)渌惴P(guān)鍵算法2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法8分層拓?fù)渌惴?定義定義 DAGDAG上的嚴(yán)格偏序關(guān)系上的嚴(yán)格偏序關(guān)系對于頂點(diǎn)集V，對E中的每一條邊，定義偏序關(guān)系ab，則“”是頂點(diǎn)集V上的嚴(yán)格偏序，滿足反自反，非對稱和傳遞性。2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法9分層拓?fù)渌惴?022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法10拓?fù)湫蛄校?,2 / 3,5,8 / 4,9 / 6,7138497265138497265序列匹配算法序列匹配算法頂點(diǎn)標(biāo)簽唯一頂點(diǎn)標(biāo)簽唯一DAGDAG關(guān)鍵算法2022-3

4、-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法11序列匹配算法 - 頂點(diǎn)標(biāo)簽唯一DAG2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法12gi.str: 1,3/2,5/4/6,7/q.str: 2,3/4/6,7/ q.str的第一層：的第一層： 2,3/ Gi.str: 1,3/ 2,5/ 4/ 6,7/ q.str第二層：第二層： 4 / Gi.str: 1,3/ 2,5/ 4/ 6,7/ q.str第三層：第三層： 6,7 Gi.str: 1,3/ 2,5/ 4/ 6,7/ s=1s=1s=1序列匹配算法 - 頂點(diǎn)標(biāo)簽唯一DAG 命題命題 若Gi和q為標(biāo)簽不重復(fù)的有向無環(huán)圖且

5、Gi包含q，則Gi.str必匹配q.str。證明略。 命題也證明了以上算法不丟解。2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法13序列匹配算法序列匹配算法頂點(diǎn)標(biāo)簽可重復(fù)頂點(diǎn)標(biāo)簽可重復(fù)DAGDAG關(guān)鍵算法2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法14序列匹配算法 - 頂點(diǎn)標(biāo)簽可重復(fù)DAG2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法15gi.str: a,d/b,c2/c1/eq.str: c1,d/c2/e序列匹配算法 - 頂點(diǎn)標(biāo)簽可重復(fù)DAG 命題命題 若Gi和q為DAG且Gi包含q，則Gi.str必匹配q.str。證明略。 以上命題的證明也就是，算

6、法2推廣到頂點(diǎn)標(biāo)簽可重復(fù)DAG不丟解的證明。2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法16環(huán)路處理算法環(huán)路處理算法關(guān)鍵算法2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法17環(huán)路處理算法 定義定義 環(huán)路中頂點(diǎn)等序關(guān)系環(huán)路中頂點(diǎn)等序關(guān)系有向圖環(huán)路中的邊首尾相連，定義環(huán)路中頂點(diǎn)是等序關(guān)系。2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法18環(huán)路處理算法2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法191235412,35412,3,4,5算法的正確性算法的正確性實(shí)驗(yàn)測試2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法20算法的正確性2022

7、-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法21性能分析性能分析實(shí)驗(yàn)測試2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法22性能分析 - 候選結(jié)果集平均大小2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法23性能分析 - 索引構(gòu)造時間算法索引構(gòu)造時間(sec.)gIndex 255.42FG-Index11.05TopologicalOrder5.99Tree+5.742022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法24性能分析 查詢時間2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法25性能分析 查詢時間2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D

8、子圖同構(gòu)過濾算法26性能分析 在線查詢時間2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法27性能分析 在線查詢時間2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法28性能分析 TopologicalOrder使得每個圖都對應(yīng)于一個獨(dú)立的序列，無需構(gòu)造復(fù)雜的索引。 數(shù)據(jù)庫動態(tài)更新時，只需要進(jìn)行個別序列處理，便于數(shù)據(jù)庫的動態(tài)維護(hù)。并且，相對于圖的匹配，序列的匹配是簡單的，算法在線查詢表現(xiàn)出色。2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法29總結(jié) 首先，根據(jù)定義有向圖環(huán)路中頂點(diǎn)之間的等序關(guān)系，可以將有向圖轉(zhuǎn)化為DAG；然后根據(jù)定義在DAG上的嚴(yán)格偏序關(guān)系，將DAG拓?fù)涑尚蛄?；再利用序列匹配算法過濾出候選結(jié)果集；最后通過同構(gòu)檢測驗(yàn)證，獲得真正的結(jié)果集。 本文提出的算法無需構(gòu)建復(fù)雜索引結(jié)構(gòu)，便于數(shù)據(jù)庫的動態(tài)維護(hù)，可用于在線查詢。2022-3-22基于拓?fù)湫蛄衅ヅ涞挠邢驁D子圖同構(gòu)過濾算法30致謝 感謝在座的老師耐