基于不確定平面圖的模式匹配查詢的研究與實現(xiàn).pdf

1、由于互聯(lián)網(wǎng)技術以及新的科學/工程技術的進步，以圖作為存儲模式的應用數(shù)量不斷地增加，如在生物信息學、社會關系學、萬維網(wǎng)等。而由于測量方法的不準確性以及對數(shù)據(jù)測量時引入的噪聲導致不確定性在圖數(shù)據(jù)中普遍存在。近年來，不確定數(shù)據(jù)管理成為了數(shù)據(jù)庫領域的研究熱點，由于圖的廣泛應用，不確定圖數(shù)據(jù)管理技術的研究也逐漸被重視。但是現(xiàn)有的圖數(shù)據(jù)技術和不確定數(shù)據(jù)管理技術不能直接應用在不確定圖數(shù)據(jù)上。所以如何高效處理這兩者的結合體面臨很大的挑戰(zhàn)。這就要求開發(fā)新

2、的技術以處理不確定圖這種復雜的數(shù)據(jù)結構。
　　不確定圖的模式匹配查詢是不確定圖數(shù)據(jù)查詢處理的重要組成部分，本文主要研究不確定平面圖的模式匹配查詢技術。
　　首先，本文使用可能世界語義建模不確定平面圖數(shù)據(jù)，在該模型的基礎上定義了不確定平面圖的模式匹配查詢。本文首先根據(jù)可能世界語義得出計算匹配概率的直接算法，即枚舉所有可能世界圖（確定圖），所有與查詢圖相匹配（確定圖匹配）的可能世界圖的概率之和即為不確定平面圖的模式匹配概率。但可

3、能世界圖的規(guī)模是呈指數(shù)級增長的，這導致直接算法效率低下。因此提出一種“基于事件解決樹”的精確算法，使查詢可以避免枚舉所有的可能世界圖。在此方法中，本文定義成功、失敗及不確定事件，建立解決樹來逐層分解不確定事件以最終得到所有的成功事件，并對成功事件的概率求和來計算匹配概率。為了進一步優(yōu)化算法效率，本文提出了四種優(yōu)化算法，(1)基于不相交匹配/割集界算法:此方法通過不相交匹配圖集和割集界計算匹配概率的緊湊邊界，并通過與概率閾值的比較得出結果