楊陽

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

1 引言

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

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

2 構(gòu)建空間數(shù)據(jù)庫中混合數(shù)據(jù)Voronoi 圖

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

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

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

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

3 鄰域點集數(shù)據(jù)精簡處理

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

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

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

4 混合數(shù)據(jù)KNN 查詢

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

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

5 對比實驗

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

為滿足實驗需求，為地理信息系統(tǒng)空間數(shù)據(jù)庫提供一個相對適宜的運行環(huán)境，按照表1 所示的內(nèi)容，設(shè)計對比實驗環(huán)境的技術(shù)參數(shù)。

表1 對比實驗環(huán)境技術(shù)參數(shù)

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

完成上述準(zhǔn)備工作后，使用本文設(shè)計的空間數(shù)據(jù)庫混合數(shù)據(jù)近鄰查詢方法，進行混合數(shù)據(jù)近鄰查詢。查詢過程中，先構(gòu)建空間數(shù)據(jù)庫中混合數(shù)據(jù)Voronoi圖，對空間數(shù)據(jù)庫中的混合數(shù)據(jù)進行精簡處理，在此基礎(chǔ)上，引進KNN 算法，通過對混合數(shù)據(jù)的KNN 查詢，完成本文方法在實驗中的應(yīng)用。

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

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

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

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

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

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

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

6 結(jié)束語

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