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

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

　　關鍵詞：應用電子技術論文,移動GIS,空間索引,快速檢索,柵格數據,DRI

　　0 引 言

　　隨著移動通信技術與地理信息技術的融合，移動地理信息系統的理論與技術研究成為新的熱點[1]。現階段，移動GIS因為其方便性、有效性，逐漸被越來越多的人所接受。在移動GIS中，空間數據的索引與檢索是數據組織當中非常重要的一部分。空間索引性能的優劣對空間數據庫和移動GIS的整體性能有著直接的影響[2]。由于移動設備資源的有限性，為方便用戶的使用，如何設計出較好的空間檢索方法，縮短數據檢索時間，成為當前移動GIS領域的一大熱點問題[3]。

　　1 移動GIS

　　移動GIS是建立在移動計算環境、處理能力有限的終端條件下，向用戶提供分布式的、隨偶性的移動地理信息服務的地理信息系統。它是集GIS，GPS和移動通信技術于一體的系統，具有移動性、動態(實時)性、對位置信息的依賴性、移動終端的多樣性等特點[4?5]。

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

　　2 空間索引編碼設計

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

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

　　2.1 根據坐標確定DRI編號

　　根據單個瓦片左下角坐標計算瓦片所處的行列編號來確定DRI編號，計算公式如下所示：

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

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

　　例如坐標為(4 550，2 500)的點，計算其所在瓦片的DRI編碼為100120018。

　　2.2 DRI編碼計算方法

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

　　FIND?DRI (P，O)

　　/* O代表原點坐標(0， 0) */

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

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

　　S=比例尺等級編號×100000000+RowN×10000+ColN

　　Return S

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

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

　　(1) 左下角點坐標加上右上角點坐標;

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

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

　　確定MBR的左下角點坐標公式如下：

　　[Xtile=Column N×250] (3)

　　[Ytile=Row N×200] (4)

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

　　3 R?Tree和DRI的代價模型對比

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

　　3.1 R?Tree代價模型

　　Faloutsos等人首先嘗試對R?樹的查詢性能進行估計。隨后，Kamel和Faloutsos[8]給出了下面的公式來評估范圍為[qx×qy]時使用通用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]代表樹節點的數量;[ni]表示R?Tree上第[i]個節點;[qx]表示[x]方向上的查詢長度;[qy]表示[y]方向上的查詢長度。

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

　　3.2 GPI代價模型

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

　　DIRECT?DRI?SEARCH(T，g)

　　Return T[g]

　　顯然，對于單個記錄來說，此搜索操作只需要花費O(1)的時間。這與從傳統的索引表中進行簡單的記錄檢索一樣。

　　3.3 對比

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

　　4 實驗測試

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

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

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

　　確定查詢位置和數據尺寸

　　If (method=1) then

　　{

　　計時

　　確定讀取范圍

　　執行SQL操作

　　檢索數據并存儲到本地內存

　　計時結束

　　}

　　If (method=2) then

　　{

　　計時

　　計算所需瓦片的索引編碼

　　計算所需編碼查詢并存儲數據

　　計時結束

　　}

　　返回計時結果

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

　　推薦期刊：《計算機光盤軟件與應用》雜志是國內外公開發行的綜合性國家級學術期刊。本刊致力于創辦以創新、準確、實用為特色，突出綜述性、科學性、實用性，及時報道國內外計算機技術在科研、教學、應用方面的研究成果和發展動態，為國內計算機同行提供學術交流的平臺。