一種基于拓撲序列匹配的有向圖

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

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

3、的有向圖子圖同構(gòu)過濾算法7分層拓撲算法分層拓撲算法關(guān)鍵算法2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法8分層拓撲算法 定義定義 DAGDAG上的嚴格偏序關(guān)系上的嚴格偏序關(guān)系對于頂點集V，對E中的每一條邊，定義偏序關(guān)系ab，則“”是頂點集V上的嚴格偏序，滿足反自反，非對稱和傳遞性。2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法9分層拓撲算法2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法10拓撲序列：1,2 / 3,5,8 / 4,9 / 6,7138497265138497265序列匹配算法序列匹配算法頂點標簽唯一頂點標簽唯一DAGDAG關(guān)鍵算法2022-6

4、-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法11序列匹配算法 - 頂點標簽唯一DAG2022-6-12基于拓撲序列匹配的有向圖子圖同構(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序列匹配算法 - 頂點標簽唯一DAG 命題命題 若Gi和q為標簽不重復(fù)的有向無環(huán)圖且

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

6、法2推廣到頂點標簽可重復(fù)DAG不丟解的證明。2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法16環(huán)路處理算法環(huán)路處理算法關(guān)鍵算法2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法17環(huán)路處理算法 定義定義 環(huán)路中頂點等序關(guān)系環(huán)路中頂點等序關(guān)系有向圖環(huán)路中的邊首尾相連，定義環(huán)路中頂點是等序關(guān)系。2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法18環(huán)路處理算法2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法191235412,35412,3,4,5算法的正確性算法的正確性實驗測試2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法20算法的正確性2022

7、-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法21性能分析性能分析實驗測試2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法22性能分析 - 候選結(jié)果集平均大小2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法23性能分析 - 索引構(gòu)造時間算法索引構(gòu)造時間(sec.)gIndex 255.42FG-Index11.05TopologicalOrder5.99Tree+5.742022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法24性能分析 查詢時間2022-6-12基于拓撲序列匹配的有向圖子圖同構(gòu)過濾算法25性能分析 查詢時間2022-6-12基于拓撲序列匹配的有向圖

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