武　菊，潘　浪

（1.内江师范学院 数学与信息科学学院，四川 内江　641100；2.成都理工大学 管理科学学院，四川 成都　610051）



面向移动GIS的快速检索方法研究

武菊1，潘浪2

（1.内江师范学院 数学与信息科学学院，四川 内江641100；2.成都理工大学 管理科学学院，四川 成都610051）

摘要：向移动客户端提供用户当前位置附近的地理空间信息是移动GIS应用程序的核心目标之一。移动GIS应用程序的有效性很大程度上取决于所使用空间数据传输方法的效率以及从地理空间数据库中获取基础地图影像的速度。提出了一种简单有效的索引方案实现在标准RDBMS环境下栅格地理空间数据的快速检索，以传统的R⁃Tree索引方法做参照，分析了R⁃Tree索引与提出的检索方法的运算代价，并通过记录不同测试地点、不同数据大小情况下两种方案的检索时间，对两种检索方法进行了性能对比。实验结果验证了所提出检索方法的有效性。

关键词：移动GIS；空间索引；快速检索；栅格数据；DRI

0　引言

随着移动通信技术与地理信息技术的融合，移动地理信息系统的理论与技术研究成为新的热点[1]。现阶段，移动GIS因为其方便性、有效性，逐渐被越来越多的人所接受。在移动GIS中，空间数据的索引与检索是数据组织当中非常重要的一部分。空间索引性能的优劣对空间数据库和移动GIS的整体性能有着直接的影响[2]。由于移动设备资源的有限性，为方便用户的使用，如何设计出较好的空间检索方法，缩短数据检索时间，成为当前移动GIS领域的一大热点问题[3]。本文针对栅格数据的快速检索提出一种新的空间索引编码方法——降维索引编码方法（Dimension Reduction Index Encoding， DRI），以期提供一种更快、更简单的方法来获取常规的具有地理位置参考的地图基本影像。

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所示。

图1　基于左下角坐标系的DRI编码

图2　DRI编码示例

因此，左下角瓦片空间索引编号为100000000，而右上角瓦片的空间索引编号为102390239。图2为示例说明。

2.1根据坐标确定DRI编号

根据单个瓦片左下角坐标计算瓦片所处的行列编号来确定DRI编号，计算公式如下所示：

例如坐标为（4 550，2 500）的点，计算其所在瓦片的DRI编码为100120018。

2.2DRI编码计算方法

基于式（1），式（2），计算DRI编码的算法如下：

2.3根据DRI编码确定瓦片最小外接矩形范围

有两种表达最小边界矩形（MBR）的方法：

（1）左下角点坐标加上右上角点坐标；

（2）左下角的坐标加上边界矩形的高度及宽度。

通常用第二种方法来表示瓦片的最小边界矩形信息。

确定MBR的左下角点坐标公式如下：

例如，GPI编号为100120018的MBR左下角坐标为（4 500，2 400）。

3　R⁃Tree和DRI的代价模型对比

R⁃Tree是格特曼于1984年提出来的[7]，主要目的是为了处理高维空间的几何数据。

3.1R⁃Tree代价模型

Faloutsos等人首先尝试对R⁃树的查询性能进行估计。随后，Kamel和Faloutsos[8]给出了下面的公式来评估范围为qx×qy时使用通用R⁃Tree查询P(qx,qy)的磁盘访问的期望值：

式中：N代表树节点的数量；ni表示R⁃Tree上第i个节点；qx表示x方向上的查询长度；qy表示y方向上的查询长度。

以“点查询平均分布在地址空间，地址空间为规则矩形”为前提，上述公式能够估计一个查询窗口q的磁盘访问的数量。很显然，使用R树记录的检索会产生一定的磁盘访问次数。

3.2GPI代价模型

从地理空间数据库中检索一个以DRI为编码的影像BLOB，从技术角度上讲非常简单，它的原理类似于从以DRI为记录编号的数据库中选择记录。用T[0..M]表示动态记录集，其中的每一个位置或记录都对应总体U={0,1,2,…,m}中的一个Key值。假定两条记录不会有相同的DRI值。影像记录g指向表中Key值为g的元素。在SQL环境中执行这种查询操作非常简单。

显然，对于单个记录来说，此搜索操作只需要花费O（1）的时间。这与从传统的索引表中进行简单的记录检索一样。

3.3对比

由于简单索引机制DRI（检索的对象实际上是一维对象）并不受维数的制约，这种通过常规关键字索引的形式进行检索明显优于R⁃Tree方法。因此，认为使用基于DRI的空间访问方法可以有效地组织和查询地理空间数据库。

4　实验测试

根据不同位置和检索策略测试了相应的检索时间。为了评估使用DRI方法从本体数据库中检索地理空间信息的真实性能，选定了包含三种不同数据密度的11个测试位置来进行测试。为了便于以后分析，在移动设备上的本地地理空间数据库中记录了使用R⁃树的空间访问方法和DRI方法的检索时间。

记录使用R⁃树和DRI方法检索次数的检测算法伪代码如下：

开发了移动应用程序来测试两种空间数据检索方法的性能[9]。将数据存储在移动设备的“HKEN_s2_en⁃cripted.spatialite”数据库中，数据大小为503 411 712 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次取平均值。

根据不同检索策略下对两个移动设备进行测试得到的测试结果绘制了两种方法，对不同数据密度下地理空间数据检索的检索性能对比图如图3，图4所示。

图3　Dell Axim X51v的测试结果

图4　Acer NeoTouch上的测试结果

基于图3和图4得到的趋势线，不同地理空间数据密度（1 MB，2.5 MB和4 MB分别被用来代表低、中、高数据密度）的性能比（使用R⁃Tree方法的检索时间与DRI方法的检索时间的比值）的计算结果如表1，表2所示。

从两个性能比集合中可以得出：处理不同的地理空间数据密度时，不论在何种设备平台上，DRI方法优于R⁃树访问方法。在两个设备测量的R⁃Tree方法趋势线的倾斜度都为0.3，并且有较高的y轴截距值。y轴截距值为执行R⁃Tree算法的总开销。这意味着大多数时间都花费在R⁃Tree算法处理上，检索时间与被检索数据容量大小的关系不大。与此相反，用DRI方法检索地理空间数据所需要的时间更依赖于所需要的数据大小，这与需要检索的瓦片总数有关。

表1　Dell Axim X51v性能比

表2　Acer NeoTouch性能比

5　结论

本文针对移动索引的设计问题，提出了一种可以在标准的RDBMS环境下进行栅格地理空间数据快速检索的有效索引方法——降维索引编码方法（DRI），并将其与R⁃Tree索引方法进行对比，实践结果证明了该方法的可行性。但本文的这种降维编码的思想提供了一种新的思路，仅适用于栅格数据的快速检索显示，如何能将其与矢量数据的分析应用结合到一起，综合应对移动GIS的各项功能需求，还需要进一步的研究。

参考文献

[1]李德仁，李清泉，谢智颖，等.论空间信息与移动通信的集成应用[J].武汉大学学报，2002（1）：1⁃7.

[2]赵波，边馥苓.面向移动GIS的动态四叉树空间索引算法[J].计算机工程，2007，33（15）：86⁃87.

[3]谢忠，凤鸣，马常杰.嵌入式空间索引策略[J].地球科学：中国地质大学学报，2006，31（5）：653⁃658.

[4]叶霜霜，申闫春.移动GIS引擎的设计与实现[J].计算机工程，2012，38（20）：256⁃259.

[5]李成名，王继周，刘勇.移动GIS的原理、方法与实践[J].武汉大学学报（信息科学版），2004，29（11）：990⁃993.

[6]李红岩，高阳东，闫晓茹.基于GPS+GPRS的嵌入式校园定位导航系统[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]雷韵鸿，周剑奇.装备嵌入式信息中心系统研究与实现[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—），女，四川泸县人，硕士，讲师。从事应用统计、地质统计学研究。潘浪（1986—），男，安徽庐江人，硕士，讲师。从事统计学研究。

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