不確定圖上Top-k子圖相似性查詢技術(shù)研究.pdf

1、近年來，隨著圖結(jié)構(gòu)在生物信息網(wǎng)絡(luò)和社交網(wǎng)絡(luò)等領(lǐng)域的廣泛應(yīng)用以及各種外界因素對數(shù)據(jù)獲取的干擾，不確定圖模型越來越受到研究者的關(guān)注。同時，子圖的相似性查詢作為圖上的基本查詢之一廣泛應(yīng)用于各種問題中，研究者們設(shè)計并實現(xiàn)了大量的算法來處理查詢圖為給定的確定圖的子圖相似性查詢，然而對于查詢圖是不確定圖和查詢結(jié)果為Top-k的情況并沒有給予足夠的重視且遇到了很大的挑戰(zhàn)。
　　針對上述問題，本文對不確定圖上的Top-k子圖相似性查詢問題進行研究

2、。
　　首先，本文考慮邊之間的存在概率相互獨立的不確定圖為數(shù)據(jù)圖的情況，由于查詢圖為數(shù)據(jù)圖中的一個導出子圖，故查詢圖也為邊之間的存在概率相互獨立的不確定圖，然后本文形式化定義了面向不確定圖上的Top-k子圖相似性查詢問題，并針對此問題提出了基于可能世界模型的算法。本文中提出了一些優(yōu)化算法以進一步提高算法的執(zhí)行效率，例如根據(jù)邊之間概率的關(guān)系及所求匹配結(jié)果的結(jié)構(gòu)特征實現(xiàn)索引優(yōu)化以減小索引集大小;基于聚簇分塊技術(shù)對數(shù)據(jù)圖進行預處理以盡量

3、縮小子圖匹配范圍;根據(jù)各個匹配邊的概率與編輯距離之間的關(guān)系改進計算模型從而避免枚舉所有可能世界圖來計算概率;根據(jù)Top-k的要求提出了基于閾值和Bound剪枝的匹配處理過程等。最后通過大量實驗驗證所提及的算法及優(yōu)化算法的有效性。
　　此外，本文考慮邊之間的存在概率具有相關(guān)性的不確定圖為數(shù)據(jù)圖，查詢圖同數(shù)據(jù)圖類型相同且為其導出子圖的情況。該問題是上述問題的改進，定義了帶有相關(guān)性的不確定圖上Top-k子圖相似性查詢問題。并在上一節(jié)的基

4、礎(chǔ)之上，結(jié)合本節(jié)中邊之間的關(guān)系提出了新的索引建立方法，采用動態(tài)獲得子結(jié)構(gòu)的算法過程并結(jié)合概率上界實現(xiàn)優(yōu)化剪枝。文中通過實驗驗證了所提到的算法和優(yōu)化方法的有效性。
　　總之，本文從越來越接近實際應(yīng)用的不確定圖模型的Top-k子圖相似性查詢的典型特征和挑戰(zhàn)出發(fā)，針對不確定圖和帶有相關(guān)性的不確定圖上子圖相似性查詢的關(guān)鍵技術(shù)展開研究，如基于動態(tài)匹配方式等，并提供了有效的基于不確定圖上的Top-k子圖查詢問題的處理方法。本文的研究工作所采取