不確定圖數(shù)據(jù)查詢處理技術(shù)的研究.pdf

1、圖是一種通用的數(shù)據(jù)結(jié)構(gòu)，已應(yīng)用到科學(xué)與工程的各個領(lǐng)域，如計算化學(xué)、生物信息學(xué)、流體動力學(xué)、社會關(guān)系學(xué)、萬維網(wǎng)等。而現(xiàn)代科學(xué)的研究方法和測量技術(shù)普遍存在誤差和噪聲，使獲取的圖數(shù)據(jù)具有不確定性，例如不確定社會關(guān)系網(wǎng)絡(luò)、不確定道路交通網(wǎng)絡(luò)、不確定蛋白質(zhì)交互網(wǎng)絡(luò)、不確定本體網(wǎng)絡(luò)等。近年來，不確定數(shù)據(jù)管理技術(shù)是數(shù)據(jù)庫領(lǐng)域的研究熱點，它的基本模型—可能世界模型—為建模不確定圖提供了基礎(chǔ)，使不確定圖能充分表達(dá)研究對象的語義。現(xiàn)有的確定圖數(shù)據(jù)和不確定數(shù)

2、據(jù)的管理技術(shù)不能處理不確定圖數(shù)據(jù)，需要開發(fā)出新的技術(shù)。
　　確定圖數(shù)據(jù)之上的查詢處理本身就非常復(fù)雜，甚至是NP-難題，如子圖同構(gòu)測試。另一方面，“可能世界”的規(guī)模呈指數(shù)級的增長。因此，如何高效地管理兩者的結(jié)合體——不確定圖更是難上加難。
　　針對“不確定圖的最短路徑查詢”，本文采用可能世界模型建模不確定圖，基于該模型提出全新的最短路徑查詢定義——概率最短路徑(P-SP)查詢。首先為避免枚舉指數(shù)級的可能世界，給出一個基本算法可

3、精確求解P-SP查詢。其次為進(jìn)一步加速基本算法，用不確定事件界對基本算法中的解決樹進(jìn)行剪枝;用同構(gòu)圖的縮減可以使基本算法只對圖中相同的元素進(jìn)行一次計算，從而降低計算空間;用不相交路徑/割集界、關(guān)聯(lián)界可使計算更快速地收斂。
　　針對“不確定圖的可達(dá)查詢”，本文通過真實的應(yīng)用實例說明此查詢在生物網(wǎng)絡(luò)、本體網(wǎng)絡(luò)和RDF網(wǎng)絡(luò)中有著廣泛的應(yīng)用。使用可能世界語義模型來定義概率可達(dá)查詢(PR)，并證明處理PR查詢是＃P-完全問題。為避免高昂的計

4、算代價，首先給出一個基本隨機(jī)算法可快速地估算出可達(dá)概率，并且該值有很高的精確度。為進(jìn)一步完善基本方法，本文為隨機(jī)算法引入條件分布，稱為條件隨機(jī)算法。在該算法中，采用圖的不相交路徑集/割集、子圖結(jié)果界作為條件概率分布應(yīng)用于條件隨機(jī)算法，因此改進(jìn)的隨機(jī)算法可準(zhǔn)確地在多項式時間內(nèi)處理查詢?；谡鎸嵅淮_定圖的大量實驗驗證了兩種隨機(jī)算法的正確性和高效性。
　　針對“不確定圖的子圖查詢”，本文使用可能世界模型描述不確定圖中節(jié)點和關(guān)聯(lián)邊的概率依

5、賴關(guān)系，進(jìn)而定義了概率子圖查詢。盡管證明處理此查詢是＃P-完全問題，本文使用了一種“過濾-驗證”的框架來有效地處理查詢。在過濾階段，通過最優(yōu)子圖特征選擇方法構(gòu)建概率索引(PIndex)，從而PIndex不僅具有小的尺寸，同時可最大限度的剪枝不確定圖。在驗證階段，給出了“基于迭代閾值”的精確算法可快速利用閾值結(jié)束計算。又給出“基于時間演化”的隨機(jī)算法可高效準(zhǔn)確地求解查詢結(jié)果。大量的基于真實數(shù)據(jù)的實驗驗證了提出方法的有效性。
　　針對