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

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

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

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

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