面向移動GIS的快速檢索方法研究

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

關(guān)鍵詞： 移動GIS； 空間索引； 快速檢索； 柵格數(shù)據(jù)； DRI

中圖分類號： TN911?34； TH873.7 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2016）03?0072?04

Research on fast retrieval method for mobile GIS

WU Ju1， PAN Lang2

（1. College of Mathematics and Information Science， Neijiang Normal University， Neijiang 641100， China；

2. College of Management Science， Chengdu University of Technology， Chengdu 610051， China）

Abstract： One of the core objectives of mobile GIS application program is to provide the nearby geographical spatial information of current user location to the mobile client， and its effectiveness largely depends on the efficient of the used spatial data transmission method and speed of acquiring the basic map image from geographic space database. A simple and effective index scheme is proposed to implement the fast retrieval of the raster geographical spatial data under standard RDBMS environment. The computing cost of the R?Tree index and the proposed retrieval method is analyzed by taking the traditional R?Tree index method as the reference， and the performance of the two methods are compared by recording the index time of the two schemes in the condition of different test location and different data size. The effectiveness of the proposed retrieval method was verified by experimental results.

Keywords： mobile GIS； spatial index； fast retrieval； raster data； DRI

0 引 言

隨著移動通信技術(shù)與地理信息技術(shù)的融合，移動地理信息系統(tǒng)的理論與技術(shù)研究成為新的熱點[1]。現(xiàn)階段，移動GIS因為其方便性、有效性，逐漸被越來越多的人所接受。在移動GIS中，空間數(shù)據(jù)的索引與檢索是數(shù)據(jù)組織當(dāng)中非常重要的一部分。空間索引性能的優(yōu)劣對空間數(shù)據(jù)庫和移動GIS的整體性能有著直接的影響[2]。由于移動設(shè)備資源的有限性，為方便用戶的使用，如何設(shè)計出較好的空間檢索方法，縮短數(shù)據(jù)檢索時間，成為當(dāng)前移動GIS領(lǐng)域的一大熱點問題[3]。本文針對柵格數(shù)據(jù)的快速檢索提出一種新的空間索引編碼方法——降維索引編碼方法（Dimension Reduction Index Encoding，DRI），以期提供一種更快、更簡單的方法來獲取常規(guī)的具有地理位置參考的地圖基本影像。

1 移動GIS

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

一般來講，移動GIS不像桌面GIS那樣涉及到大規(guī)模GIS數(shù)據(jù)的分析處理，但卻希望能在有限的帶寬和計算能力下實現(xiàn)對空間數(shù)據(jù)的快速檢索和顯示[6]。通常傳輸?shù)揭苿涌蛻舳说牡貓D內(nèi)容主要包含兩種信息：地理數(shù)據(jù)和屬性。但無論是什么類型的應(yī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ù)”，需要同時發(fā)送給客戶端。

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

以香港地區(qū)為例介紹降維索引編碼方法，首先根據(jù)一系列的1[∶]5 000的地圖創(chuàng)建覆蓋整個香港地區(qū)的無縫底圖圖像。每個基礎(chǔ)圖像設(shè)定的覆蓋范圍大小為[x]方向3 750 m，在[y]方向上3 000 m，相應(yīng)的圖像尺寸是4 800×3 840像素。把每一個基礎(chǔ)圖像平均切分成15行15列，一共有225個瓦片。按照這個分區(qū)的概念，整個香港是由240行240列的網(wǎng)，共57 600個（16×16×225）瓦片覆蓋。

無縫底圖瓦片的DRI編號需要基于瓦片左下角坐標(biāo)來計算。本文把每一個瓦片的DRI編號設(shè)計為9位數(shù)字，定義了瓦片在240行×240列的格網(wǎng)中位置的行號和列號以及比例尺大小。第一位數(shù)字表示瓦片的比例尺大小，不同的系統(tǒng)可以按照不同的顯示需求進(jìn)行相應(yīng)標(biāo)記，本文將其記為1。中間4位數(shù)字表示行號，后4位數(shù)字為列號。瓦片的編號從左下角在行列上的0值開始，行號往北依次增加，列數(shù)往東依次增加，如圖1所示，也就是說左下角瓦片的空間索引編號定義為100000000，與之相對應(yīng)的，右上角瓦片的編號為102390239。示例如圖2所示。

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

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

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

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

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

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

2.2 DRI編碼計算方法

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

FIND?DRI （P，O）

/* O代表原點坐標(biāo)（0， 0） */

RowN=（P.y?O.y）/200

ColN=（P.x?O.x）/250

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

Return S

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

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

（1） 左下角點坐標(biāo)加上右上角點坐標(biāo)；

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

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

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

[Xtile=Column N×250] （3）

[Ytile=Row N×200] （4）

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

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

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

3.1 R?Tree代價模型

Faloutsos等人首先嘗試對R?樹的查詢性能進(jìn)行估計。隨后，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]代表樹節(jié)點的數(shù)量；[ni]表示R?Tree上第[i]個節(jié)點；[qx]表示[x]方向上的查詢長度；[qy]表示[y]方向上的查詢長度。

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

3.2 GPI代價模型

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

DIRECT?DRI?SEARCH（T，g）

Return T[g]

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

3.3 對比

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

4 實驗測試

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

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

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

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

If （method=1） then

{

計時

確定讀取范圍

執(zhí)行SQL操作

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

計時結(jié)束

}

If （method=2） then

{

計時

計算所需瓦片的索引編碼

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

計時結(jié)束

}

返回計時結(jié)果

開發(fā)了移動應(yīng)用程序來測試兩種空間數(shù)據(jù)檢索方法的性能[9]。將數(shù)據(jù)存儲在移動設(shè)備的“HKEN_s2_encripted.spatialite”數(shù)據(jù)庫中，數(shù)據(jù)大小為503 411 712 B。移動設(shè)備選用的是兩個基于微軟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è)版。為了獲得每個地理空間數(shù)據(jù)訪問方法更為可靠的檢索時間，對每個位置測量10次取平均值。

根據(jù)不同檢索策略下對兩個移動設(shè)備進(jìn)行測試得到的測試結(jié)果繪制了兩種方法，對不同數(shù)據(jù)密度下地理空間數(shù)據(jù)檢索的檢索性能對比圖如圖3，圖4所示。

基于圖3和圖4得到的趨勢線，不同地理空間數(shù)據(jù)密度（1 MB，2.5 MB和4 MB分別被用來代表低、中、高數(shù)據(jù)密度）的性能比（使用R?Tree方法的檢索時間與DRI方法的檢索時間的比值）的計算結(jié)果如表1，表2所示。

從兩個性能比集合中可以得出：處理不同的地理空間數(shù)據(jù)密度時，不論在何種設(shè)備平臺上，DRI方法優(yōu)于R?樹訪問方法。在兩個設(shè)備測量的R?Tree方法趨勢線的傾斜度都為0.3，并且有較高的[y]軸截距值。[y]軸截距值為執(zhí)行R?Tree算法的總開銷。這意味著大多數(shù)時間都花費在R?Tree算法處理上，檢索時間與被檢索數(shù)據(jù)容量大小的關(guān)系不大。與此相反，用DRI方法檢索地理空間數(shù)據(jù)所需要的時間更依賴于所需要的數(shù)據(jù)大小，這與需要檢索的瓦片總數(shù)有關(guān)。

5 結(jié) 論

本文針對移動索引的設(shè)計問題，提出了一種可以在標(biāo)準(zhǔn)的RDBMS環(huán)境下進(jìn)行柵格地理空間數(shù)據(jù)快速檢索的有效索引方法——降維索引編碼方法（DRI），并將其與R?Tree索引方法進(jìn)行對比，實踐結(jié)果證明了該方法的可行性。但本文的這種降維編碼的思想提供了一種新的思路，僅適用于柵格數(shù)據(jù)的快速檢索顯示，如何能將其與矢量數(shù)據(jù)的分析應(yīng)用結(jié)合到一起，綜合應(yīng)對移動GIS的各項功能需求，還需要進(jìn)一步的研究。

參考文獻(xiàn)

[1] 李德仁，李清泉，謝智穎，等.論空間信息與移動通信的集成應(yīng)用[J].武漢大學(xué)學(xué)報，2002（1）：1?7.

[2] 趙波，邊馥苓.面向移動GIS的動態(tài)四叉樹空間索引算法[J].計算機(jī)工程，2007，33（15）：86?87.

[3] 謝忠，鳳鳴，馬常杰.嵌入式空間索引策略[J].地球科學(xué)：中國地質(zhì)大學(xué)學(xué)報，2006，31（5）：653?658.

[4] 葉霜霜，申閆春.移動GIS引擎的設(shè)計與實現(xiàn)[J].計算機(jī)工程，2012，38（20）：256?259.

[5] 李成名，王繼周，劉勇.移動GIS的原理、方法與實踐[J].武漢大學(xué)學(xué)報（信息科學(xué)版），2004，29（11）：990?993.

[6] 李紅巖，高陽東，閆曉茹.基于GPS+GPRS的嵌入式校園定位導(dǎo)航系統(tǒng)[J].計算機(jī)測量與控制，2013，21（12）：3377?3379.

[7] GUTTMAN A. R?trees： a dynamic index structure for spatial searching [C]// Proceedings of 1984 ACM SIGMOD Conference on Management of Data. San Francisco： ACM， 1985： 47?57.

[8] KAMEL I， FALOUTSOS C. On packing R?trees [C]// Procee?dings of the 2nd International Conference on Information and Knowledge Management. [S.l.]： ACM， 1993： 490?499.

[9] 雷韻鴻，周劍奇.裝備嵌入式信息中心系統(tǒng)研究與實現(xiàn)[J].計算機(jī)測量與控制，2011，19（3）：704?706.