武　菊，潘　浪

（1.內(nèi)江師范學院 數(shù)學與信息科學學院，四川 內(nèi)江　641100；2.成都理工大學 管理科學學院，四川 成都　610051）

?

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

武菊1，潘浪2

（1.內(nèi)江師范學院 數(shù)學與信息科學學院，四川 內(nèi)江641100；2.成都理工大學 管理科學學院，四川 成都610051）

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

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

0　引言

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

1　移動GIS

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

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

2　空間索引編碼設計

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

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

圖1　基于左下角坐標系的DRI編碼

圖2　DRI編碼示例

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

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

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

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

2.2DRI編碼計算方法

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

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

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

（1）左下角點坐標加上右上角點坐標；

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

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

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

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

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

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

3.1R?Tree代價模型

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

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

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

3.2GPI代價模型

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

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

3.3對比

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

4　實驗測試

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

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

開發(fā)了移動應用程序來測試兩種空間數(shù)據(jù)檢索方法的性能[9]。將數(shù)據(jù)存儲在移動設備的“HKEN_s2_en?cripted.spatialite”數(shù)據(jù)庫中，數(shù)據(jù)大小為503 411 712 B。移動設備選用的是兩個基于微軟Windows Mobile的設備：戴爾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ù)密度下地理空間數(shù)據(jù)檢索的檢索性能對比圖如圖3，圖4所示。

圖3　Dell Axim X51v的測試結果

圖4　Acer NeoTouch上的測試結果

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

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

表1　Dell Axim X51v性能比

表2　Acer NeoTouch性能比

5　結論

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

參考文獻

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

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

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

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

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

[6]李紅巖，高陽東，閆曉茹.基于GPS+GPRS的嵌入式校園定位導航系統(tǒng)[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，F(xiàn)ALOUTSOS 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].計算機測量與控制，2011，19（3）：704?706.

中圖分類號：TN911?34；TH873.7

文獻標識碼：A

文章編號：1004?373X（2016）03?0072?04

doi：10.16652/j.issn.1004?373x.2016.03.018

收稿日期：2015?10?22

作者簡介：武菊（1981—），女，四川瀘縣人，碩士，講師。從事應用統(tǒng)計、地質(zhì)統(tǒng)計學研究。潘浪（1986—），男，安徽廬江人，碩士，講師。從事統(tǒng)計學研究。

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 infor?mation 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