地理信息系統空間數據庫中混合數據的近鄰查詢研究

楊陽

（梅州市測繪與地理信息中心，廣東 梅州 514071）

1 引言

隨著我國路網建設、地理位置服務等相關工作的持續完善與不斷發展，空間數據庫得到逐步推廣和應用。為不斷滿足產業的發展需求，空間數據庫的構建已經與物聯網、機器學習、大數據等現代化技術發生一定程度的融合[1]。隨著地理信息系統的不斷發展，空間數據索引、混合數據檢索成為數據庫工作領域的研究重點[2]。相比常規的索引方式，空間數據查詢具有一定的優勢，能夠有效提高系統對數據的訪問效率與查詢數據使用率。在數據索引工作持續推進過程中，有關部門提出了針對空間數據庫中混合數據的近鄰查詢方法，該方法是數據庫關鍵詞數據檢索與核心數據檢索的基礎[3]。由于終端用戶對檢索數據需求的不斷改變，近鄰檢索被演變為最近鄰檢索、組近鄰檢索、聚類檢索等[4]。但在現有檢索與查詢方法應用效果的深入研究中發現，大部分方法在檢索中都需要將抽象的空間點、空間線段作為研究對象，即查詢的目標數據集合與檢索到的空間數據集合往往存在類型不匹配、格式不統一問題。

因此，為解決這類問題，充分發揮地理信息系統在測繪地理信息生產、空間數據庫構建等方面的價值與效益[5]，研究以某地理信息系統為例，設計一種針對空間數據庫中混合數據的近鄰查詢方法，為數據庫的檢索、查詢等工作提供技術支持。

2 構建空間數據庫中混合數據Voronoi 圖

為滿足空間數據庫中混合數據的近鄰查詢，提取數據庫的混合數據，構建對應的Voronoi圖。Voronoi圖一般指泰森多邊形，是一組由連接兩鄰點線段的垂直平分線組成的連續多邊形。一個泰森多邊形內的任一點到構成該多邊形控制點的距離小于到其他多邊形控制點的距離。

在構建過程中，需要判斷查詢數據集合在空間中的生成對象類型與位置關系，其中，點間距離等分線是兩個連線的縱向等分線，兩個點之間的Voronoi圖邊是兩個連線的豎向平分線[6]。點到線段的距離等分線屬于直線段，直線段直接作用于影響區域，直線段距離相等線是以點為中心、以直線段為準線的拋物線，將其作為依據，確定混合數據Voronoi圖的覆蓋區域。在確定區域內點集后，按照公式（1）計算，定義混合數據Voronoi圖的邊。

公式（1）中：R表示混合數據Voronoi圖的邊；x表示空間數據庫中混合數據子集；X表示混合數據集合；d表示距離；Pk表示以k為半徑的外接圓；Pj表示以j為半徑的內接圓。

在確定混合數據Voronoi圖的所有點集后，生成并連接若干條混合數據Voronoi圖的邊，按照上述方式，完成混合數據Voronoi圖的構建。

3 鄰域點集數據精簡處理

在上述設計內容的基礎上，考慮到Voronoi圖中的混合數據量較大，且存在數據冗余方面不足的情況，會在一定程度上影響數據近鄰查詢結果[7]。因此，要對數據集合進行精簡處理操作。在此過程中，計算一個隨機數據點距離其近鄰直線的距離，計算公式如下：

公式（2）中：D表示隨機一個數據點距離其近鄰直線的距離；a、b、c分別表示數據點在三個方向的矢量。在此基礎上，將計算得到的D作為空間數據精簡鄰域，將隨機選擇的數據點作為中心，將D作為半徑，建立外接圓，從中提取鄰域點集個數，此過程具體計算公式如下：

公式（3）中：p表示鄰域點數據集合；N表示鄰域點集個數；i表示鄰域點集中第i個數據[8]。保留上述集合中的數據，同時刪除空間中的其他數據將其作為冗余數據，以此種方式，完成鄰域點集數據的精簡處理操作。

4 混合數據KNN 查詢

基于上述設計內容，引進KNN 算法。KNN 算法是一種鄰近算法，或者說K 最鄰近（K-NearestNeihbor，KNN）分類算法是數據挖掘分類技術中最簡單的方法之一。所謂K 最近鄰，意為K 個最近的鄰居，說的是每個樣本都可以用它最接近的K 個鄰近值來代表。近鄰算法就是將數據集合中每一個記錄進行分類的方法[9]。設計針對地理信息系統空間數據庫中混合數據的KNN查詢。在此過程中，假定數據庫中混合數據集合表示為Q，則混合數據KNN 查詢的返回數據應為OQ，將OQ作為混合數據KNN 的查詢結果。假定地理信息系統空間數據庫中的混合數據維度為n[10]，則空間中隨機向量的查詢過程如公式（4）所示。

公式（4）中：L(q)表示空間中隨機向量q的查詢過程；n表示地理信息系統空間數據庫中的混合數據維度；q1、q2分別表示隨機向量q的兩個鄰近點。按照上述方式，實現混合數據的KNN 查詢，以此完成近鄰查詢方法的設計。

5 對比實驗

上文分別從三個方面，以某地理信息系統為例，設計了一種針對空間數據庫中混合數據的近鄰查詢方法。但目前該方法的研究仍局限在理論階段，還沒有進行到實際操作階段。本文結合研究成果，采用設計對比實驗的方式，針對空間數據庫中混合數據的近鄰查詢方法展開測試，以便將設計查詢方法在測繪地理信息生產領域進行推廣應用。

為滿足實驗需求，為地理信息系統空間數據庫提供一個相對適宜的運行環境，按照表1 所示的內容，設計對比實驗環境的技術參數。

表1 對比實驗環境技術參數

按照表1 內容完成實驗環境的布置后，選用由某地區地質測繪工程單位提供的測繪地理信息數據作為此次對比實驗的測試集合，實驗相關數據均存儲在地理信息系統空間數據庫中。實驗數據為某地區地質測繪工程現場反饋數據，數據集合中包含1957027 個節點數據，共涉及2654792 條路段。為確保實驗結果的真實性與可靠性，實驗前要對地理信息系統空間數據庫中的數據進行適當調整，可在數據集合中添加空間坐標、方向數據等信息，并在不同的測繪路段隨機生成數據節點與路段。將隨機生成的節點以混合數據的方式錄入數據庫，插入的節點與路段之間存在交叉關系，且所有線段之間均不發生交互。

完成上述準備工作后，使用本文設計的空間數據庫混合數據近鄰查詢方法，進行混合數據近鄰查詢。查詢過程中，先構建空間數據庫中混合數據Voronoi圖，對空間數據庫中的混合數據進行精簡處理，在此基礎上，引進KNN 算法，通過對混合數據的KNN 查詢，完成本文方法在實驗中的應用。

為滿足實驗結果的對比性需求，檢驗本文方法與傳統方法的優勢與不足，引進基于數據空間自適應規則的近鄰查詢方法、基于本地化差分隱私算法的近鄰查詢方法，將上述兩種方法分別設定為傳統方法1 與傳統方法2。實驗分別按照對應方法的規范化操作步驟，進行地理信息系統空間數據庫中混合數據的近鄰查詢。確保實驗中相關參數條件不變后，將近鄰查詢過程中目標數據集合周圍數據對象密度對CPU 運行時間的影響，作為評價本文查詢方法應用效果的關鍵指標，由技術人員統計實驗結果，具體如圖1 所示。

圖1 近鄰查詢過程中CPU運行時間對比結果

從圖1 所示的實驗結果可以看出，在三種方法中，本文設計的方法應用后，目標數據集合周圍數據對象密度對CPU 運行時間的影響最小，即在查詢過程中CPU 的運行時間最短。

在完成上述設計后，按照相同步驟再次開展實驗，將查詢時空間數據庫中的混合數據量對I/O 代價的影響作為評價指標。I/O 代價越高，說明查詢所占用的CPU 越高，出現異常查詢或查詢中出現卡頓的次數越多；反之，I/O 代價越低，說明查詢所占用的CPU 越低，出現異常查詢或查詢中出現卡頓的次數越少。以此為依據，統計對比實驗結果，如表2 所示。

表2 混合數據近鄰查詢中數據量對I/O代價的影響

從表2 所示的實驗結果可以看出，在混合數據近鄰查詢中數據量不變的前提下，應用本文設計的近鄰查詢方法進行混合數據近鄰查詢，數據量對I/O 代價的影響最小，而使用傳統方法進行混合數據近鄰查詢，數據量對I/O 代價的影響較大。

綜合實驗結果，得到如下結論：相比傳統方法，本文設計的空間數據庫中混合數據的近鄰查詢方法在實際應用中效果良好，可以縮短查詢過程中的CPU 運行時間，并降低數據量對I/O 代價的影響，提高地理信息系統近鄰查詢工作的可靠性。

6 結束語

經市場調研發現，空間數據庫在信息決策系統、道路交通系統、地理信息系統中應用廣泛，可將此類數據庫作為開發地理信息系統的核心。在構建數據庫時發現，空間數據庫不僅具備傳統數據庫使用中的所有功能，還具備對空間信息與數據的描述、管理、檢索、存儲等功能。為發揮空間數據庫在測繪地理信息生產領域的應用價值，提高對數據庫中混合數據的利用率，本文以某地理信息系統為例，通過構建空間數據庫混合數據Voronoi圖、數據精簡處理、混合數據KNN 查詢，設計一種空間數據庫中混合數據的近鄰查詢方法。為測試該方法的應用效果，引進兩種傳統方法作為參照，設計了對比實驗，結果證明本文設計的方法可縮短查詢過程中的CPU 運行時間，降低數據量對I/O 代價的影響。為進一步實現對本文方法近鄰查詢效果的優化，在現有工作基礎上，加大對實驗的投入，深化本文方法的綜合性能，為地理信息系統在更多領域推廣應用提供技術指導。