应用电子技术论文面向移动GIS的快速检索方法研究

　　这篇应用电子技术论文发表了面向移动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次取平均值。

　　推荐期刊：《计算机光盘软件与应用》杂志是国内外公开发行的综合性国家级学术期刊。本刊致力于创办以创新、准确、实用为特色，突出综述性、科学性、实用性，及时报道国内外计算机技术在科研、教学、应用方面的研究成果和发展动态，为国内计算机同行提供学术交流的平台。