空間數據庫分類查詢算法研究與實現

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

關鍵詞：空間數據庫; K最近鄰算法;反最近鄰查詢算法

0 引言

計算機技術和數據收集技術的飛速發展，使人們可以從更加廣闊的范圍和難以想象的速度收集與存儲信息，希望能夠對其進行更高層次的分析，以便更好地利用這些數據。由于空間數據庫的數據量龐大，具有高可訪問性、模型復雜和屬性數據與空間數據聯合管理等特點。導致了用戶對豐富數據資源不能對其進行有效地利用。空間數據庫技術已經代替傳統的文件管理方式，逐步成為空間數據管理的主流技術。如今基于空間數據庫的研究已成為計算機科技領域中應用研究技術內容最豐富的分支之一。如何在龐大的數據中挖掘出有特定意義的信息是空間數據研究的一個重要方面。

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

1 經典查詢算法

1.1范圍查詢算法。

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

1.2 最近鄰查詢算法。

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

1.3 反最近鄰查詢算法

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

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

2.算法的設計與實現

2.1范圍查詢。

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

2.2最近鄰查詢算法實現。

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

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

2.3反最鄰近查詢算法實現。

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

3 結語

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

參考文獻

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

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