面向不確定圖的kNN查詢研究.pdf

1、作為一種重要的且具有代表性的數(shù)據(jù)結(jié)構(gòu)，圖通?？梢杂脕砻枋霾煌I(lǐng)域的事物之間的繁雜關(guān)系。在信息化時代，快速增長的數(shù)據(jù)中的不確定性越來越普遍。如何對具有不確定性的圖數(shù)據(jù)進行有效的處理，是一項巨大的工程。對于不確定圖的研究，有很多想法都來源于確定圖，因為確定圖可以看作是邊的存在概率為1的特殊不確定圖。關(guān)于圖的研究，在很多情況下都無法避開距離問題，但是由于不確定圖自身的特性，使得其距離的計算變得更加復(fù)雜。
　　本文首先對現(xiàn)有的關(guān)于距離的研

2、究進行分析，指出在不確定圖上進行相關(guān)研究所遇到的主要問題，其一是精確計算是NP難問題，其二是最短距離相同的路徑之間在很多情況下都是不獨立的。其次，在結(jié)合已有的關(guān)于距離的相關(guān)計算方法的基礎(chǔ)上，提出了不確定圖上可達距離的一種計算方法。當(dāng)不確定圖中給定的兩點之間可達的概率超過0.5的時候，就用期望最短距離來度量它們之間的可達距離；相反，雖然它們之間不可達的概率比較大，但是只要最短距離不是無窮，說明他們之間是存在可達路徑的，這時就用最大可能路徑

3、的長度來度量它們之間的可達距離。在現(xiàn)有的關(guān)于不確定圖的距離的研究中，大都使用采樣法作為核心處理方法，但是取樣次數(shù)對結(jié)果的影響很大，而且結(jié)果也不一定固定。為了避開采樣，提出了兩種近似方法，分別是基于算術(shù)平均的近似方法與基于加權(quán)平均的近似方法。在算法復(fù)雜度方面，通過理論與實驗相結(jié)合的方式驗證了在可能世界中尋找可達的最短距離的時候，與最受歡迎的Dijsktra方法相比較而言，BFS方法的優(yōu)勢更加突出。最后，在將可達距離應(yīng)用于 kNN查詢處理的