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

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

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

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

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

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