不確定圖上基于標(biāo)簽限制的可達(dá)性查詢(xún)技術(shù)的研究.pdf

1、近年來(lái)，圖模型得到越來(lái)越多的重視，它不僅可以應(yīng)用到路網(wǎng)及社交網(wǎng)絡(luò)中，還可以應(yīng)用到各種生物網(wǎng)絡(luò)中。作為圖上的基本查詢(xún)之一，可達(dá)性查詢(xún)得到了廣泛的研究?？蛇_(dá)性查詢(xún)也是子圖同構(gòu)的圖形查詢(xún)的一個(gè)基本構(gòu)成部分，因此可能會(huì)被頻繁調(diào)用以處理大量數(shù)據(jù)和復(fù)雜查詢(xún)，對(duì)它的有效支持就顯得尤為重要。然而，由于統(tǒng)計(jì)誤差等原因，圖數(shù)據(jù)往往具有不確定性，且隨著圖中包含的信息越來(lái)越豐富，各式各樣的標(biāo)簽圖應(yīng)需產(chǎn)生。在這些圖上的一個(gè)基礎(chǔ)研究問(wèn)題是基于標(biāo)簽限制的可達(dá)性查詢(xún)(

2、LCR)，即查詢(xún)?nèi)我鈨牲c(diǎn)間路徑滿(mǎn)足標(biāo)簽集限制的可達(dá)概率。針對(duì)不確定標(biāo)簽圖，傳統(tǒng)的可達(dá)性查詢(xún)技術(shù)不再適用。
　　針對(duì)上面提出的問(wèn)題，本文對(duì)不確定圖上基于標(biāo)簽限制的可達(dá)性查詢(xún)技術(shù)進(jìn)行了研究。首先，針對(duì)概率圖的不確定性，本文形式化定義了不確定圖上基于標(biāo)簽和距離限制的可達(dá)性問(wèn)題，接著提出了一種基于子路徑的高效的剪枝方法，根據(jù)子路徑和距離閾值的特性，通過(guò)分支路徑過(guò)濾的剪枝方法，大幅度減少了子路徑處理個(gè)數(shù)。最后給出了抽樣方法包括Random

3、Walk、不等概率抽樣和DC樹(shù)抽樣方法。其次，針對(duì)標(biāo)簽集為有序限制的情況下，對(duì)上面的問(wèn)題進(jìn)行改進(jìn)，定義了不確定圖上有序標(biāo)簽限制的可達(dá)性查詢(xún)問(wèn)題，由此提出了一個(gè)迭代算法，即使用路徑索引及有效的剪枝方法定位含有有序標(biāo)簽的邊，接著用這些邊構(gòu)造新的子路徑，連接成完整路徑并記錄，再使用蒙特卡羅采樣方法對(duì)所有路徑的概率和進(jìn)行估計(jì)，并給出了Bonferroni和Chung-Erdos不等式界和路徑/割界。最后，實(shí)驗(yàn)通過(guò)比其他方法驗(yàn)證了本文所提出的算法

4、在高效性和準(zhǔn)確性上的優(yōu)越性，同時(shí)檢驗(yàn)了各種剪枝優(yōu)化方法的效率。
　　總之，本文從越來(lái)越接近實(shí)際應(yīng)用的不確定圖上基于標(biāo)簽限制的可達(dá)性查詢(xún)的典型特征和挑戰(zhàn)出發(fā)，針對(duì)不確定圖上的路徑標(biāo)簽的關(guān)鍵技術(shù)展開(kāi)研究，如基于子路徑、路徑索引的數(shù)據(jù)結(jié)構(gòu)的標(biāo)簽查詢(xún)技術(shù)，預(yù)處理技術(shù)、分支路徑過(guò)濾技術(shù)和拓?fù)漤樞蚣糁夹g(shù)等，從而提供高效健壯的不確定圖上基于標(biāo)簽限制的查詢(xún)處理方法。本文的研究工作所采用的算法思想和剪枝更新策略將為相關(guān)課題的開(kāi)展打下了堅(jiān)實(shí)的基礎(chǔ)。