空間數(shù)據(jù)庫分類查詢算法研究與實現(xiàn)

摘要： 空間數(shù)據(jù)庫是指地理信息系統(tǒng)在計算機物理存儲介質(zhì)上存儲的與應(yīng)用相關(guān)的地理空間數(shù)據(jù)的總和。由于傳統(tǒng)的查詢方法效率低，查詢信息單一，如何在龐大的數(shù)據(jù)中快速有效地挖掘出有特定意義的信息是空間數(shù)據(jù)查詢研究的一個重要方面。為了更深入的挖掘空間數(shù)據(jù)庫的信息，進行的空間數(shù)據(jù)查詢使用了范圍查詢，K最近鄰算法查詢，反最近鄰查詢算法的優(yōu)化和實現(xiàn)對大量已分類的空間數(shù)據(jù)進行查詢。使用反最近鄰查詢算法得到的結(jié)果是在所有屬于一類點的集合中，把某一位置作為離其最近的地點的點的集合，并用數(shù)據(jù)實驗對算法進行了驗證，利用算法幫助用戶對大量空間數(shù)據(jù)進行分類查詢，完成了最優(yōu)查詢的可行性。

關(guān)鍵詞：空間數(shù)據(jù)庫; K最近鄰算法;反最近鄰查詢算法

0 引言

計算機技術(shù)和數(shù)據(jù)收集技術(shù)的飛速發(fā)展，使人們可以從更加廣闊的范圍和難以想象的速度收集與存儲信息，希望能夠?qū)ζ溥M行更高層次的分析，以便更好地利用這些數(shù)據(jù)。由于空間數(shù)據(jù)庫的數(shù)據(jù)量龐大，具有高可訪問性、模型復(fù)雜和屬性數(shù)據(jù)與空間數(shù)據(jù)聯(lián)合管理等特點。導(dǎo)致了用戶對豐富數(shù)據(jù)資源不能對其進行有效地利用?？臻g數(shù)據(jù)庫技術(shù)已經(jīng)代替?zhèn)鹘y(tǒng)的文件管理方式，逐步成為空間數(shù)據(jù)管理的主流技術(shù)。如今基于空間數(shù)據(jù)庫的研究已成為計算機科技領(lǐng)域中應(yīng)用研究技術(shù)內(nèi)容最豐富的分支之一。如何在龐大的數(shù)據(jù)中挖掘出有特定意義的信息是空間數(shù)據(jù)研究的一個重要方面。

在Visual C++6.0環(huán)境下分別使用范圍查詢、K最臨近分類算法查詢、反臨近查詢（RNN）算法對處理過的數(shù)據(jù)進行查詢。范圍查詢是在一個已知的點周圍一定范圍內(nèi)找到某類型的點。K最臨近分類算法是找出整個數(shù)據(jù)集中距離已知點最小的幾個數(shù)據(jù)點。反近鄰查詢算法則是找出某個數(shù)據(jù)集中以已知點為最鄰近點的地點。

1 經(jīng)典查詢算法

1.1范圍查詢算法。

指定空間中某一點和一個范圍，在空間特征對象的圖層中以指定點為中心，以設(shè)定的范圍為半徑，而在范圍之內(nèi)的點為結(jié)果。四方形a為指定的點，以該點位中心，一定范圍為半徑，落入該范圍內(nèi)的圖中顯示的圓內(nèi)的點即為該范圍查詢的結(jié)果。

1.2 最近鄰查詢算法。

最近鄰查詢問題是由Kunth在1973年提出來的，即郵局問題。它可以描述為：給定N維空間內(nèi)的n個點所組成的集合S，將這n個點存儲在一種數(shù)據(jù)結(jié)構(gòu)中，使得對于空間內(nèi)的任何查詢點q，都可以有效地找到大的最近鄰，即在S中找到一個點p，是起到q的距離最近。最鄰近的數(shù)目可以是一個，也可以是多個即KNN。K最近鄰算法（KNN）：圓要被決定賦予哪個類，是三角形還是四方形？如果K=3，由于三角形所占比例為2/3，圓a將被賦予三角形那個類，如果K=5，由于四方形比例為3/5，因此圓a被賦予四方形類。

1.3 反最近鄰查詢算法

對于數(shù)據(jù)及S和查詢點q，預(yù)先計算出數(shù)據(jù)集S中每個點p的最近鄰，而后，使每個點與一個鄰接圓（vicinity circle）相對應(yīng)，再進一步建立這些圓的R-樹索引結(jié)構(gòu)，稱其為RNN-樹，應(yīng)用這種索引結(jié)構(gòu)，可以很容易求得q的最近鄰。但由于RNN-樹的建立目的在于反最近鄰查詢，而非最近鄰查詢，因此，F(xiàn)lip Korn和S.Muthukrishnan不得不建立另外的R-樹來進行最近鄰查詢和其他空間查詢[1]。

反最近鄰算法（Reverse Nearest Neighbor，RNN），要判斷哪些圓形和三角形將中間四方形認為是距離自己最近的四方形。先在所有圓形，三角形中求出距離自己最近的四方形，對于那些將中間四方形認為是距離自己最近的四方形的圖形即為該反最近鄰算法的結(jié)果。

2.算法的設(shè)計與實現(xiàn)

2.1范圍查詢。

范圍查詢算法實現(xiàn)首先獲得用戶所選擇的空間特征對象所在的圖層，并使用了MapX中CMapXLayer類的SearchWithinDistance函數(shù)。該函數(shù)專門用來對已知地點為中心，已知距離為半徑，確定圖層進行范圍查詢。將查詢到的圖元集合在新建的MapX圖層中進行顯示。

2.2最近鄰查詢算法實現(xiàn)。

首先新建立的數(shù)據(jù)結(jié)構(gòu)CMFeature類的數(shù)組對象。將特征對象即圖元集合分離出來。計算此圖元集合中每一個圖元與已知點的距離，將這個距離按插入排序到CMFeature類的數(shù)組中。如果這個圖元按距離計算可以插入到上述數(shù)組中，那么將這個圖元和它距離已知點的距離插入到數(shù)組中。

當所有圖元集合都完成上述操作后，將CMFeature類的數(shù)組中的圖元顯示到地圖中。

2.3反最鄰近查詢算法實現(xiàn)。

首先將特征對象即圖元集合分離出來。根據(jù)定理以“我的位置”點為其所在平面的原點，以該點的水平線為線L1，依次將地圖劃分S1，S2，…S6六個區(qū)域。分別計算落入每個區(qū)域圖元集合中距離已知點最近的那個圖元并將該圖元存入新建立的數(shù)據(jù)結(jié)構(gòu)CMRnnFeature類的對象數(shù)組中。該數(shù)組中最多有6個對象。再分別以這6個對象的圖元為中心點，在滿足“位置點性質(zhì)”特征的圖元集合中找到它的KNN，如果它的KNN剛好是“我的位置”這個圖元，那么把它加入到新的圖層中并顯示到地圖上。

3 結(jié)語

空間數(shù)據(jù)庫技術(shù)是地理信息系統(tǒng)數(shù)據(jù)組織的核心技術(shù)，也是地理科學(xué)、測繪科學(xué)、計算機科學(xué)和信息科學(xué)相結(jié)合的產(chǎn)物?？臻g數(shù)據(jù)庫技術(shù)已經(jīng)代替?zhèn)鹘y(tǒng)的文件管理方式，逐步成為空間數(shù)據(jù)管理的主流技術(shù)。但是由于空間數(shù)據(jù)庫數(shù)據(jù)量大，導(dǎo)致了用戶擁有豐富數(shù)據(jù)資源卻不能對其進行有效地利用。實現(xiàn)了傳統(tǒng)的輸入地點名稱在地圖上進行查詢，而且對所有地圖數(shù)據(jù)按其性質(zhì)對其分類。用戶在分好類的地圖中可以輸入范圍進行查詢，可以查詢地圖中離我最近的某類的地點，還可以使用本系統(tǒng)對選址進行決策。

參考文獻

[1]Liao Haojun，Han Jizhong，F(xiàn)ang Jinyun.All-Nearest-Neighbor Queries Processing in Spatial Databases.Journal of computer research and development，2011，48（1）：17～22.

作者簡介：許崇 女，1982年出生，實驗師，就職于沈陽建筑大學(xué)