基于地球空間網(wǎng)格的基礎(chǔ)地理信息數(shù)據(jù)庫空間索引方法

王乃生 吳 鑫 龐曉峰 勾會杰

(1.自然資源部陜西基礎(chǔ)地理信息中心 陜西西安 710054；2.西安市水利規(guī)劃勘測設(shè)計(jì)院 陜西西安 710054)

基礎(chǔ)地理信息是國家空間數(shù)據(jù)基礎(chǔ)設(shè)施的重要組成部分，是國家信息化的權(quán)威、統(tǒng)一的定位基準(zhǔn)和空間載體，是國家經(jīng)濟(jì)建設(shè)、社會發(fā)展和生態(tài)保護(hù)中不可或缺的基礎(chǔ)性和戰(zhàn)略性信息資源[1]，具有通用性強(qiáng)、共享需求大、行業(yè)應(yīng)用廣泛等特點(diǎn)。隨著社會經(jīng)濟(jì)的加速發(fā)展，一方面基礎(chǔ)地理信息數(shù)據(jù)的動態(tài)更新和全面更新已逐步覆蓋了各級比例尺，另一方面基礎(chǔ)地理信息數(shù)據(jù)的數(shù)據(jù)量呈爆發(fā)式增長。

傳統(tǒng)的基礎(chǔ)地理信息數(shù)據(jù)庫以關(guān)系型數(shù)據(jù)庫為主，數(shù)據(jù)的空間檢索主要借助空間關(guān)系運(yùn)算和數(shù)據(jù)庫索引來實(shí)現(xiàn)，對海量異構(gòu)數(shù)據(jù)的檢索效率低。如何科學(xué)、高效地管理基礎(chǔ)地理信息數(shù)據(jù)庫，提高海量異構(gòu)數(shù)據(jù)的空間檢索效率，進(jìn)而提升地理信息數(shù)據(jù)庫的管理能力，是業(yè)內(nèi)學(xué)者一直關(guān)注的研究方向。

徐道柱等[2]提出了一種適應(yīng)分布式環(huán)境下的分層+分塊的矢量數(shù)據(jù)存儲組織模型，實(shí)現(xiàn)了高并發(fā)條件下的數(shù)據(jù)高效訪問；于亮和宋明明等[3-4]對基于R-樹的空間索引技術(shù)進(jìn)行了探討，提出了一種改進(jìn)型的R-樹索引結(jié)構(gòu)，在一定程度上提升了空間數(shù)據(jù)的檢索效率；余冬梅[5]對空間索引及其發(fā)展分類、空間數(shù)據(jù)查詢及其與傳統(tǒng)關(guān)系數(shù)據(jù)庫的區(qū)別進(jìn)行了研究。這些研究從不同視角研究了空間數(shù)據(jù)索引，但并未提出針對基礎(chǔ)地理信息數(shù)據(jù)庫有效管理的完整解決方案。

地球空間網(wǎng)格[6]編碼規(guī)則的提出為基礎(chǔ)地理信息數(shù)據(jù)庫的空間索引提供了一種新的思路。本文在研究地球空間網(wǎng)格編碼規(guī)則等關(guān)鍵技術(shù)的基礎(chǔ)上，設(shè)計(jì)了基礎(chǔ)地理信息數(shù)據(jù)庫的空間索引算法及對應(yīng)的數(shù)據(jù)空間檢索算法，以解決基礎(chǔ)地理信息數(shù)據(jù)庫的空間檢索問題。

1 數(shù)據(jù)空間索引關(guān)鍵技術(shù)

1.1 地球空間網(wǎng)格編碼規(guī)則

地球空間網(wǎng)格是為了滿足地球空間區(qū)域位置結(jié)構(gòu)化表達(dá)和統(tǒng)一標(biāo)識，將地球空間剖分成不同尺度單元的空間參考系統(tǒng)。地球空間網(wǎng)格按照四叉樹遞歸剖分方案，以地球參考橢球面、本初子午面與赤道面3個面的交點(diǎn)為起始位置，在經(jīng)度(L)、緯度(B)和大地高(H)3個方向逐級遞歸二分，在地球參考橢球面形成地球表面剖分，加大地高方向形成立體剖分。

地球空間網(wǎng)格編碼是為地球空間上的任意網(wǎng)格賦予唯一可識別的編碼。地球空間網(wǎng)格編碼采用四進(jìn)制1位變長編碼，編碼順序采用Z序進(jìn)行，即每一級網(wǎng)格編碼在上一級網(wǎng)格編碼基礎(chǔ)上采用Z序繼續(xù)編碼，將地球表面空間區(qū)域劃分為32級的網(wǎng)格。

1.2 基礎(chǔ)地理數(shù)據(jù)存儲管理

基礎(chǔ)地理信息數(shù)據(jù)庫中的數(shù)據(jù)主要包括矢量數(shù)據(jù)、柵格數(shù)據(jù)、文檔數(shù)據(jù)及元數(shù)據(jù)。矢量數(shù)據(jù)以空間數(shù)據(jù)集進(jìn)行存儲管理，地理要素都有相應(yīng)的空間信息和屬性信息；柵格數(shù)據(jù)以鑲嵌數(shù)據(jù)集或文件形式進(jìn)行存儲，空間信息和屬性信息管理主要通過對應(yīng)的元數(shù)據(jù)來實(shí)現(xiàn)；文檔數(shù)據(jù)以文件形式進(jìn)行存儲，空間信息和屬性信息管理也是通過對應(yīng)的元數(shù)據(jù)來關(guān)聯(lián)實(shí)現(xiàn)。

1.3 空間關(guān)系

根據(jù)空間對象間的拓?fù)潢P(guān)系，多邊形與網(wǎng)格的空間關(guān)系可歸納為以下3種：

1)相離關(guān)系，網(wǎng)格完全不在多邊形內(nèi)部；

2)相交關(guān)系，網(wǎng)格部分在多邊形內(nèi)部或多邊形完全在網(wǎng)格內(nèi)部；

3)包含關(guān)系，網(wǎng)格完全在多邊形內(nèi)部。

1.4 完全容納數(shù)據(jù)的最小網(wǎng)格

空間索引是一種依據(jù)基礎(chǔ)地理信息數(shù)據(jù)的位置、形狀或空間實(shí)體之間的某種空間關(guān)系，按一定順序排列的數(shù)據(jù)結(jié)構(gòu)?；诘厍蚩臻g網(wǎng)格實(shí)現(xiàn)基礎(chǔ)地理信息數(shù)據(jù)的空間索引，就是以地球空間網(wǎng)格的方式重新組織基礎(chǔ)地理信息數(shù)據(jù)的位置，建立數(shù)據(jù)和網(wǎng)格的關(guān)系，為數(shù)據(jù)庫的高效檢索提供支撐。

能夠完全容納數(shù)據(jù)的最小網(wǎng)格，是建立數(shù)據(jù)和網(wǎng)格關(guān)系的一種直觀有效的方式。對于矢量數(shù)據(jù)，其數(shù)據(jù)內(nèi)容由一個個地理要素構(gòu)成，當(dāng)?shù)乩硪氐淖钚⊥饨泳匦闻c第m級網(wǎng)格的相交個數(shù)為1、與第m+1級網(wǎng)格的相交個數(shù)大于1時，則認(rèn)為第m級網(wǎng)格是能夠完全容納當(dāng)前要素?cái)?shù)據(jù)的最小網(wǎng)格。對于通過元數(shù)據(jù)進(jìn)行管理的柵格數(shù)據(jù)和文檔數(shù)據(jù)，可將元數(shù)據(jù)的范圍看作是一個面要素，按矢量數(shù)據(jù)中的面要素計(jì)算最小網(wǎng)格。

2 數(shù)據(jù)空間索引算法

基于地球空間網(wǎng)格實(shí)現(xiàn)基礎(chǔ)地理信息數(shù)據(jù)的空間索引，實(shí)際上就是計(jì)算數(shù)據(jù)對應(yīng)的最小網(wǎng)格并進(jìn)行編碼的過程。計(jì)算完全容納數(shù)據(jù)的最小網(wǎng)格算法流程為：

第1步：根據(jù)要素實(shí)體的左、右、上、下經(jīng)緯度坐標(biāo)和所在空間區(qū)域，計(jì)算上下緯度和左右經(jīng)度坐標(biāo)差dL、dW，若dL大于dW，則將dL作為長邊、dW作為短邊，得到要素實(shí)體的最小外接矩形。

第2步：若dL的邊長小于某一級網(wǎng)格邊長Dm且大于下一級網(wǎng)格邊長Dm+1，則可確定描述該要素實(shí)體對應(yīng)的網(wǎng)格層級為m。

第3步：若數(shù)據(jù)所在空間范圍的最小外接矩形與第m級網(wǎng)格的相交個數(shù)為1，與第m+1級網(wǎng)格的相交個數(shù)大于1時，則認(rèn)為第m級網(wǎng)格是能夠完全容納當(dāng)前數(shù)據(jù)的最小網(wǎng)格。

第4步：若最小外接矩形與第m級網(wǎng)格的相交個數(shù)大于1，則m=m- 1，繼續(xù)第3步。

第5步：若最小外接矩形與第m級網(wǎng)格的相交個數(shù)等于1，則m=m+ 1，繼續(xù)第3步。

在計(jì)算最小網(wǎng)格時會存在一些同時跨越多個網(wǎng)格的數(shù)據(jù)，如果跨網(wǎng)格數(shù)據(jù)采用最小網(wǎng)格作為其所在的空間網(wǎng)格，則這些數(shù)據(jù)最小網(wǎng)格的層級過高，不利于后續(xù)數(shù)據(jù)檢索。因此，需要對這些跨網(wǎng)格數(shù)據(jù)進(jìn)行特殊處理，選擇與跨網(wǎng)格數(shù)據(jù)相交的指定層級的網(wǎng)格作為這些數(shù)據(jù)所在的空間網(wǎng)格。為了判斷數(shù)據(jù)是否為跨網(wǎng)格數(shù)據(jù)并確定其所在空間網(wǎng)格的層級，設(shè)計(jì)算法流程為：

1)獲取數(shù)據(jù)外接矩形的左下角點(diǎn)PLB和右上角點(diǎn)PRT。

2)獲取PLB和PRT坐標(biāo)(X，Y)的整數(shù)值(XLB，YLB)和(XRT，YRT)。

3)若XRT-XLB>0或者YRT-YLB>0，則認(rèn)定該數(shù)據(jù)是跨網(wǎng)格數(shù)據(jù)；反之，則進(jìn)行下一步判斷。

4)根據(jù)外接矩形的長邊計(jì)算跨網(wǎng)格數(shù)據(jù)所在的層級m。

5)根據(jù)最小網(wǎng)格算法計(jì)算跨網(wǎng)格數(shù)據(jù)最小網(wǎng)格所在的層級n。

6)若m-n≥4，則認(rèn)定該數(shù)據(jù)是跨網(wǎng)格數(shù)據(jù)；反之，則不是跨網(wǎng)格數(shù)據(jù)。

7)m為該數(shù)據(jù)所在空間網(wǎng)格的指定層級。

計(jì)算數(shù)據(jù)所在地球空間網(wǎng)格后，按照地球空間網(wǎng)格編碼規(guī)則計(jì)算空間網(wǎng)格的編碼，如果數(shù)據(jù)所在的空間網(wǎng)格有多個，則以“，”作為分隔符，以“編碼1，編碼2，…，編碼n”的格式進(jìn)行編碼。

3 數(shù)據(jù)空間檢索算法實(shí)現(xiàn)

基于地球空間網(wǎng)格建立的空間索引進(jìn)行數(shù)據(jù)空間檢索時，需要自頂向下逐級判斷多邊形檢索范圍以及與不同級別網(wǎng)格的空間關(guān)系，最后計(jì)算多邊形范圍內(nèi)相應(yīng)的地球空間網(wǎng)格，算法實(shí)現(xiàn)如圖1所示。

圖1 空間檢索流程

由圖1可知，當(dāng)多邊形與網(wǎng)格為相離關(guān)系時，該網(wǎng)格及其子網(wǎng)格均被過濾掉。當(dāng)多邊形與網(wǎng)格為相交關(guān)系時，該網(wǎng)格則需要遞歸判斷其子級網(wǎng)格與多邊形的關(guān)系，直至其子級網(wǎng)格被多邊形包含或網(wǎng)格級別達(dá)到空間索引時計(jì)算的網(wǎng)格最深層級。當(dāng)多邊形與網(wǎng)格為包含關(guān)系時，多邊形與該網(wǎng)格及其下級網(wǎng)格中的數(shù)據(jù)均為包含關(guān)系。

計(jì)算多邊形檢索范圍對應(yīng)的地球空間網(wǎng)格后，需要根據(jù)不同的空間關(guān)系進(jìn)行相應(yīng)的屬性查詢。

首先，當(dāng)多邊形與網(wǎng)格為包含關(guān)系時，由于網(wǎng)格編碼之間存在上下級關(guān)系，即網(wǎng)格第n+1級網(wǎng)格編碼的前n位是上一級網(wǎng)格的編碼，因此在定位具體數(shù)據(jù)時，通過屬性查詢只需查找到前n位編碼相同，即可查找到該網(wǎng)格及其所有下級網(wǎng)格中的數(shù)據(jù)。

其次，當(dāng)多邊形與網(wǎng)格為相交關(guān)系時，只需要定位網(wǎng)格對應(yīng)的每個數(shù)據(jù)。如查找交疊的m級，其網(wǎng)格編碼為s的網(wǎng)格a中的數(shù)據(jù)，將查詢條件設(shè)為“位置編碼=s”，通過屬性查詢查出的數(shù)據(jù)即為m級網(wǎng)格a中的數(shù)據(jù)。為驗(yàn)證上述算法，選取陜西省某區(qū)域的1∶10 000 基礎(chǔ)地理信息要素和地理國情要素?cái)?shù)據(jù)進(jìn)行了數(shù)據(jù)試驗(yàn)，同時，基于地球空間網(wǎng)格的空間索引編碼，對比測試了基于地球空間網(wǎng)格空間索引后的空間檢索與傳統(tǒng)空間檢索的效率，試驗(yàn)數(shù)據(jù)統(tǒng)計(jì)信息見表1。

表1 空間檢索統(tǒng)計(jì)信息Tab.1 Statistics Data in Spatial Retrieval圖層名稱要素/個檢索結(jié)果/個傳統(tǒng)空間檢索時間/s基于網(wǎng)格的檢索時間/s 效率比/%CPTP2 2659700.130.121.04HFCL35 34812 6460.490.421.17LFCL385 945124 4984.972.641.88RESP397 22876 2103.142.051.53LRDL705 18514 5400.780.810.96VEGA831 041358 23637.148.644.30LRDA7 5872 2210.340.331.04UV_SFCP22 7422 4810.260.261.00UV_HYDL122 4415 2950.690.421.64UV_HYDA32 8183 5250.640.401.61UV_LCRA7 190 715387 57340.6314.922.72

從表 1可知，基于地球空間網(wǎng)格空間索引的空間檢索時間與傳統(tǒng)空間檢索時間相比，在所有圖層其效率均高于傳統(tǒng)空間檢索，檢索效率平均提升1.5倍，部分圖層可提升4倍以上。

4 結(jié) 語

本文提出的基于地球空間網(wǎng)格的基礎(chǔ)地理信息數(shù)據(jù)庫空間索引方法，可以在不改變已有數(shù)據(jù)模型和存儲模式的基礎(chǔ)上，快速為已有的基礎(chǔ)地理信息數(shù)據(jù)庫構(gòu)建擴(kuò)展索引，大幅提升了空間數(shù)據(jù)的檢索效率。

本文的研究成果已在陜西省基礎(chǔ)地理信息數(shù)據(jù)庫中得到應(yīng)用，與傳統(tǒng)的空間檢索方法相比，檢索效率平均提升1.5倍，部分圖層可提升4倍以上。