這篇應(yīng)用電子技術(shù)論文發(fā)表了面向移動(dòng)GIS的快速檢索方法研究，論文針對(duì)柵格數(shù)據(jù)的快速檢索提出一種新的空間索引編碼方法——降維索引編碼方法(Dimension Reduction Index Encoding，DRI)，以期提供一種更快、更簡單的方法來獲取常規(guī)的具有地理位置參考的地圖基本影像。
 

　　摘 要：向移動(dòng)客戶端提供用戶當(dāng)前位置附近的地理空間信息是移動(dòng)GIS應(yīng)用程序的核心目標(biāo)之一。移動(dòng)GIS應(yīng)用程序的有效性很大程度上取決于所使用空間數(shù)據(jù)傳輸方法的效率以及從地理空間數(shù)據(jù)庫中獲取基礎(chǔ)地圖影像的速度。提出了一種簡單有效的索引方案實(shí)現(xiàn)在標(biāo)準(zhǔn)RDBMS環(huán)境下柵格地理空間數(shù)據(jù)的快速檢索，以傳統(tǒng)的R?Tree索引方法做參照，分析了R?Tree索引與提出的檢索方法的運(yùn)算代價(jià)，并通過記錄不同測試地點(diǎn)、不同數(shù)據(jù)大小情況下兩種方案的檢索時(shí)間，對(duì)兩種檢索方法進(jìn)行了性能對(duì)比。實(shí)驗(yàn)結(jié)果驗(yàn)證了所提出檢索方法的有效性。

　　關(guān)鍵詞：應(yīng)用電子技術(shù)論文,移動(dòng)GIS,空間索引,快速檢索,柵格數(shù)據(jù),DRI

　　0 引 言

　　隨著移動(dòng)通信技術(shù)與地理信息技術(shù)的融合，移動(dòng)地理信息系統(tǒng)的理論與技術(shù)研究成為新的熱點(diǎn)[1]。現(xiàn)階段，移動(dòng)GIS因?yàn)槠浞奖阈浴⒂行�性，逐漸被越來越多的人所接受。在移動(dòng)GIS中，空間數(shù)據(jù)的索引與檢索是數(shù)據(jù)組織當(dāng)中非常重要的一部分。空間索引性能的優(yōu)劣對(duì)空間數(shù)據(jù)庫和移動(dòng)GIS的整體性能有著直接的影響[2]。由于移動(dòng)設(shè)備資源的有限性，為方便用戶的使用，如何設(shè)計(jì)出較好的空間檢索方法，縮短數(shù)據(jù)檢索時(shí)間，成為當(dāng)前移動(dòng)GIS領(lǐng)域的一大熱點(diǎn)問題[3]。

　　1 移動(dòng)GIS

　　移動(dòng)GIS是建立在移動(dòng)計(jì)算環(huán)境、處理能力有限的終端條件下，向用戶提供分布式的、隨偶性的移動(dòng)地理信息服務(wù)的地理信息系統(tǒng)。它是集GIS，GPS和移動(dòng)通信技術(shù)于一體的系統(tǒng)，具有移動(dòng)性、動(dòng)態(tài)(實(shí)時(shí))性、對(duì)位置信息的依賴性、移動(dòng)終端的多樣性等特點(diǎn)[4?5]。

　　一般來講，移動(dòng)GIS不像桌面GIS那樣涉及到大規(guī)模GIS數(shù)據(jù)的分析處理，但卻希望能在有限的帶寬和計(jì)算能力下實(shí)現(xiàn)對(duì)空間數(shù)據(jù)的快速檢索和顯示[6]。通常傳輸?shù)揭苿?dòng)客戶端的地圖內(nèi)容主要包含兩種信息：地理數(shù)據(jù)和屬性。但無論是什么類型的應(yīng)用程序，都需要向移動(dòng)客戶端提供一組包括道路、建筑物、水系特征等要素的基礎(chǔ)地理空間數(shù)據(jù)集，這組地圖數(shù)據(jù)通常被稱為“基礎(chǔ)地圖”。地圖基礎(chǔ)數(shù)據(jù)作為背景顯示基本的地理相關(guān)數(shù)據(jù)，與地圖基礎(chǔ)數(shù)據(jù)相關(guān)聯(lián)的第二類數(shù)據(jù)集合，也就是所謂的“應(yīng)用數(shù)據(jù)”，需要同時(shí)發(fā)送給客戶端。

　　2 空間索引編碼設(shè)計(jì)

　　以香港地區(qū)為例介紹降維索引編碼方法，首先根據(jù)一系列的1[∶]5 000的地圖創(chuàng)建覆蓋整個(gè)香港地區(qū)的無縫底圖圖像。每個(gè)基礎(chǔ)圖像設(shè)定的覆蓋范圍大小為[x]方向3 750 m，在[y]方向上3 000 m，相應(yīng)的圖像尺寸是4 800×3 840像素。把每一個(gè)基礎(chǔ)圖像平均切分成15行15列，一共有225個(gè)瓦片。按照這個(gè)分區(qū)的概念，整個(gè)香港是由240行240列的網(wǎng)，共57 600個(gè)(16×16×225)瓦片覆蓋。　無縫底圖瓦片的DRI編號(hào)需要基于瓦片左下角坐標(biāo)來計(jì)算。本文把每一個(gè)瓦片的DRI編號(hào)設(shè)計(jì)為9位數(shù)字，定義了瓦片在240行×240列的格網(wǎng)中位置的行號(hào)和列號(hào)以及比例尺大小。第一位數(shù)字表示瓦片的比例尺大小，不同的系統(tǒng)可以按照不同的顯示需求進(jìn)行相應(yīng)標(biāo)記，本文將其記為1。中間4位數(shù)字表示行號(hào)，后4位數(shù)字為列號(hào)。瓦片的編號(hào)從左下角在行列上的0值開始，行號(hào)往北依次增加，列數(shù)往東依次增加，如圖1所示，也就是說左下角瓦片的空間索引編號(hào)定義為100000000，與之相對(duì)應(yīng)的，右上角瓦片的編號(hào)為102390239。示例如圖2所示。

　　因此，左下角瓦片空間索引編號(hào)為100000000，而右上角瓦片的空間索引編號(hào)為102390239。圖2為示例說明。

　　2.1 根據(jù)坐標(biāo)確定DRI編號(hào)

　　根據(jù)單個(gè)瓦片左下角坐標(biāo)計(jì)算瓦片所處的行列編號(hào)來確定DRI編號(hào)，計(jì)算公式如下所示：

　　[Column N=f(x，250的倍數(shù))] (1)

　　[Row N=f(y，200的倍數(shù))] (2)

　　例如坐標(biāo)為(4 550，2 500)的點(diǎn)，計(jì)算其所在瓦片的DRI編碼為100120018。

　　2.2 DRI編碼計(jì)算方法

　　基于式(1)，式(2)，計(jì)算DRI編碼的算法如下：

　　FIND?DRI (P，O)

　　/* O代表原點(diǎn)坐標(biāo)(0， 0) */

　　RowN=(P.y?O.y)/200

　　ColN=(P.x?O.x)/250

　　S=比例尺等級(jí)編號(hào)×100000000+RowN×10000+ColN

　　Return S

　　2.3 根據(jù)DRI編碼確定瓦片最小外接矩形范圍

　　有兩種表達(dá)最小邊界矩形(MBR)的方法：

　　(1) 左下角點(diǎn)坐標(biāo)加上右上角點(diǎn)坐標(biāo);

　　(2) 左下角的坐標(biāo)加上邊界矩形的高度及寬度。

　　通常用第二種方法來表示瓦片的最小邊界矩形信息。

　　確定MBR的左下角點(diǎn)坐標(biāo)公式如下：

　　[Xtile=Column N×250] (3)

　　[Ytile=Row N×200] (4)

　　例如，GPI編號(hào)為100120018的MBR左下角坐標(biāo)為(4 500，2 400)。

　　3 R?Tree和DRI的代價(jià)模型對(duì)比

　　R?Tree是格特曼于1984年提出來的[7]，主要目的是為了處理高維空間的幾何數(shù)據(jù)。

　　3.1 R?Tree代價(jià)模型

　　Faloutsos等人首先嘗試對(duì)R?樹的查詢性能進(jìn)行估計(jì)。隨后，Kamel和Faloutsos[8]給出了下面的公式來評(píng)估范圍為[qx×qy]時(shí)使用通用R?Tree查詢[P(qx，qy)]的磁盤訪問的期望值：

　　[P(qx，qy)=i=1Nni，x?ni，y+qy×i=1Nni，x+qx?i=1Nni，y+N?qx?qy]

　　式中：[N]代表樹節(jié)點(diǎn)的數(shù)量;[ni]表示R?Tree上第[i]個(gè)節(jié)點(diǎn);[qx]表示[x]方向上的查詢長度;[qy]表示[y]方向上的查詢長度。

　　以“點(diǎn)查詢平均分布在地址空間，地址空間為規(guī)則矩形”為前提，上述公式能夠估計(jì)一個(gè)查詢窗口[q]的磁盤訪問的數(shù)量。很顯然，使用R樹記錄的檢索會(huì)產(chǎn)生一定的磁盤訪問次數(shù)。

　　3.2 GPI代價(jià)模型

　　從地理空間數(shù)據(jù)庫中檢索一個(gè)以DRI為編碼的影像BLOB，從技術(shù)角度上講非常簡單，它的原理類似于從以DRI為記錄編號(hào)的數(shù)據(jù)庫中選擇記錄。用T[0..M]表示動(dòng)態(tài)記錄集，其中的每一個(gè)位置或記錄都對(duì)應(yīng)總體[U={0，1，2，…，m}]中的一個(gè)Key值。假定兩條記錄不會(huì)有相同的DRI值。影像記錄[g]指向表中Key值為[g]的元素。在SQL環(huán)境中執(zhí)行這種查詢操作非常簡單。

　　DIRECT?DRI?SEARCH(T，g)

　　Return T[g]

　　顯然，對(duì)于單個(gè)記錄來說，此搜索操作只需要花費(fèi)O(1)的時(shí)間。這與從傳統(tǒng)的索引表中進(jìn)行簡單的記錄檢索一樣。

　　3.3 對(duì)比

　　由于簡單索引機(jī)制DRI(檢索的對(duì)象實(shí)際上是一維對(duì)象)并不受維數(shù)的制約，這種通過常規(guī)關(guān)鍵字索引的形式進(jìn)行檢索明顯優(yōu)于R?Tree方法。因此，認(rèn)為使用基于DRI的空間訪問方法可以有效地組織和查詢地理空間數(shù)據(jù)庫。

　　4 實(shí)驗(yàn)測試

　　根據(jù)不同位置和檢索策略測試了相應(yīng)的檢索時(shí)間。為了評(píng)估使用DRI方法從本體數(shù)據(jù)庫中檢索地理空間信息的真實(shí)性能，選定了包含三種不同數(shù)據(jù)密度的11個(gè)測試位置來進(jìn)行測試。為了便于以后分析，在移動(dòng)設(shè)備上的本地地理空間數(shù)據(jù)庫中記錄了使用R?樹的空間訪問方法和DRI方法的檢索時(shí)間。

　　記錄使用R?樹和DRI方法檢索次數(shù)的檢測算法偽代碼如下：

　　選擇采用的索引方法 (1： R?Tree/2： GPI)

　　確定查詢位置和數(shù)據(jù)尺寸

　　If (method=1) then

　　{

　　計(jì)時(shí)

　　確定讀取范圍

　　執(zhí)行SQL操作

　　檢索數(shù)據(jù)并存儲(chǔ)到本地內(nèi)存

　　計(jì)時(shí)結(jié)束

　　}

　　If (method=2) then

　　{

　　計(jì)時(shí)

　　計(jì)算所需瓦片的索引編碼

　　計(jì)算所需編碼查詢并存儲(chǔ)數(shù)據(jù)

　　計(jì)時(shí)結(jié)束

　　}

　　返回計(jì)時(shí)結(jié)果

　　開發(fā)了移動(dòng)應(yīng)用程序來測試兩種空間數(shù)據(jù)檢索方法的性能[9]。將數(shù)據(jù)存儲(chǔ)在移動(dòng)設(shè)備的“HKEN_s2_encripted.spatialite”數(shù)據(jù)庫中，數(shù)據(jù)大小為503 411 7 [本文由WWw. dYlW.nEt提供，第 一論文網(wǎng)專業(yè)電子技術(shù)類論文，歡迎光臨dYLW.neT]12 B。移動(dòng)設(shè)備選用的是兩個(gè)基于微軟Windows Mobile的設(shè)備：戴爾Axim X51V? Intel PXA270，CPU @624 MHz，64 MB RAM，Windows Mobile 5.0專業(yè)版;宏碁的[neoTouch?]Qualcomm 8250， CPU@1 GHz，256 MB SDRAM，Windows Mobile 6.5專業(yè)版。為了獲得每個(gè)地理空間數(shù)據(jù)訪問方法更為可靠的檢索時(shí)間，對(duì)每個(gè)位置測量10次取平均值。

　　推薦期刊：《計(jì)算機(jī)光盤軟件與應(yīng)用》雜志是國內(nèi)外公開發(fā)行的綜合性國家級(jí)學(xué)術(shù)期刊。本刊致力于創(chuàng)辦以創(chuàng)新、準(zhǔn)確、實(shí)用為特色，突出綜述性、科學(xué)性、實(shí)用性，及時(shí)報(bào)道國內(nèi)外計(jì)算機(jī)技術(shù)在科研、教學(xué)、應(yīng)用方面的研究成果和發(fā)展動(dòng)態(tài)，為國內(nèi)計(jì)算機(jī)同行提供學(xué)術(shù)交流的平臺(tái)。