RkNN搜索在空間數(shù)據(jù)庫應(yīng)用中的研究.pdf

1、隨著Internet以及Web的迅速發(fā)展，使得網(wǎng)絡(luò)上的信息量無比豐富，如何從海量的網(wǎng)絡(luò)信息資源中及時、準(zhǔn)確地找到所需的信息成為當(dāng)今的一個研究熱點。而實際上，一方面用戶不得不忍受在海量的信息中搜索自己想要的信息的痛苦，而另一方面，信息發(fā)布者卻希望對自己的信息感興趣的用戶能夠迅速的接收到信息。所以，一個有效的解決方法是信息發(fā)布者只把信息發(fā)布給那些有可能對這些信息有興趣的用戶。 隨著空間信息科學(xué)的發(fā)展，地理信息系統(tǒng)等方面的應(yīng)用越來越廣

2、泛，作為空間科學(xué)的重要分支之一，地理信息系統(tǒng)在很多應(yīng)用中都需要求給定對象的RkNN，它在智能導(dǎo)航、現(xiàn)代通訊、交通控制、氣象預(yù)報等各個領(lǐng)域都有著廣泛的需求。 在現(xiàn)實生活中，大部分?jǐn)?shù)據(jù)都具有空間屬性，例如，地址、客戶統(tǒng)計分布數(shù)據(jù)或者資產(chǎn)分布數(shù)據(jù)等等。利用這些數(shù)據(jù)信息的空間屬性進(jìn)行數(shù)據(jù)分析，可以觀察發(fā)展趨勢，幫助您掌握機遇。總而言之，能夠迅速有效地管理空間數(shù)據(jù)，并根據(jù)其空間屬性進(jìn)行分析，對于當(dāng)今的企業(yè)來說，是勢在必行的。尤其是在郵電通

3、信、城市規(guī)劃、公安交通等領(lǐng)域，空間屬性比普通數(shù)據(jù)扮演著更為重要的角色[15]。 空間數(shù)據(jù)庫自身也有很多特殊性，首先，空間數(shù)據(jù)對象有著復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，因為對于空間對象的描述除了有幾何信息外，還有其它非空間的屬性。因此，空間數(shù)據(jù)庫通常都非常巨大：其次，空間數(shù)據(jù)對象常常是動態(tài)變化的，對于它們的插入、刪除和更新交錯進(jìn)行，而且由于空間數(shù)據(jù)的次序難以有統(tǒng)一的標(biāo)準(zhǔn)，所以對其動態(tài)的管理難度很大。 RkNN搜索在空間數(shù)據(jù)庫中有十分重要的應(yīng)

4、用，如GIs、生物基因研究等領(lǐng)域。然而現(xiàn)有的RkNN算法一般都是近似的解法或則僅僅適用于某種特定的情況，因此在一定程度上存在以下的不足和缺陷：僅適用于二維空間數(shù)據(jù)的求解；對k的值有限制；僅僅支持靜態(tài)數(shù)據(jù)而不支持?jǐn)?shù)據(jù)庫的動態(tài)更新，尤其移動對象數(shù)據(jù)庫；僅能得到近似不能得到精確的結(jié)果。 而相對于RkNN問題，kNN問題不僅研究得較早，而且對于它們的商業(yè)應(yīng)用已經(jīng)相當(dāng)?shù)膹V泛，所以相對于RkNN而言，kNN問題的研究已經(jīng)相當(dāng)成熟，而且存在較

5、理想的算法。但遺憾的是，在一般情況下kNN與RkNN之間并不存在任何直接的轉(zhuǎn)換關(guān)系，即r<'∈>NNS(q)并不意味著r<'∈>RNNS(q)。不過通過研究我們發(fā)現(xiàn)，在一定的條件的情況下，RNN(q) NN(q)和：RkNN(q) kNN(q)。即我們可以把：RkNN求解問題轉(zhuǎn)化為kNN求解問題，通過相對來說成熟的kNN算法，最終達(dá)到求解RkNN的目的。基于此，本文提出了一個利用已有的kNN算法，在三維空間內(nèi)能夠支持?jǐn)?shù)據(jù)更新且適合任意k