2022年面向移动GIS的动态四叉树空间索引算法 .pdf

《2022年面向移动GIS的动态四叉树空间索引算法 .pdf》由会员分享，可在线阅读，更多相关《2022年面向移动GIS的动态四叉树空间索引算法 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、86面向移动 GIS 的动态四叉树空间索引算法赵波1，边馥苓2(1.广州大学经济与管理学院，广州 510006；2.武汉大学空间信息与数字工程研究中心，武汉 430079)摘要：介绍了常用的空间索引算法，对其性能进行了比较，认为这些算法用于需要动态更新空间索引结构的移动GIS 系统中时具有较大的局限性。针对移动GIS 系统中对空间索引的特殊要求，提出了动态四叉树空间索引算法，对算法的计算效率进行了分析，实验表明该算法用于移动GIS 系统时效果良好。关键词：空间索引；动态四叉树；移动GIS Dynamic Quadtree Spatial Index Algorithm for Mobile G

2、IS ZHAO Bo1,BIAN Fu-ling2(1.School of Ecnomics and Management,Guangzhou University,Guangzhou 510006;2.Research Center of Spatial Information and Digital Engineering,Wuhan University,Wuhan 430079)【Abstract】The commonly used spatial index algorithms in GIS are introduced,whose performance used in mobi

3、le are compared.Thelimitationsof these algorithms when used in mobile GIS are analyzed.A new spatial index algorithm,the dynamic quadtree spatial index algorithm,ispresented.Its effectiveness is validated by experiments.【Key words】spatial index;dynamic quadtree;mobile GIS 计算机工程Computer Engineering第

4、33卷第 15 期Vol.33 No.152007 年 8 月August 2007 软件技术与数据库文章编号：10003428(2007)15 008602文献标识码：A 中图分类号：TP3111 概述自从美国提出“数字地球”概念以来，各国政府纷纷把国家的数字化进程看作国家发展战略的重中之重，它是增强国力不可或缺的一个环节。而“数字城市”又是“国家数字化”的重要组成部分。在数字城市中，每一个组织或个人是一个数字节点。数字城市是一个系统工程，它以计算机网络为基础，通过网络将各数字节点连接在一起。网络基础设施的不断完善是城市数字化的必要条件，由此而产生的各类应用则是“数字城市”的重要组成部分之一

5、，移动GIS 系统正是在这一背景下产生并发展起来的。随着移动通信技术的高速发展、无线信息基础设施的功能越来越强大以及移动通信和计算设备性能的不断提高，移动 GIS 正改变着空间信息的服务方式。移动通信在空间信息服务领域将找到新的发展空间和服务模式，而空间信息服务也将在无线通信平台上衍生出新的服务，不再是简单的平台转换。移动 GIS 与传统 GIS 平台相比，具有其自身的特点1：(1)运行平台的延伸与传统 GIS 相比，移动 GIS 平台从传统平台延伸到无线网络，使得移动GIS 系统的实现更为复杂；同时无线定位技术与传统 GIS 的结合也产生了全新的GIS 应用模式，使得空间信息在移动GIS 系

6、统中的核心地位更加突出。(2)分布式数据源GIS 系统向无线平台的转移引发了很多新的GIS 应用，它们要求分布式数据源的支持。因为移动用户的位置是不断变化的，需要的信息也是多种多样，任何一个单一的数据源都无法满足移动用户的需求。(3)终端的多样性移动 GIS 终端一般情况下应该是各类移动计算终端，比如移动电话、PDA、PocketPC等。终端的多样性就意味着移动 GIS 服务需要更加灵活的定制能力和扩展能力，以及开放的体系结构，以适应终端的多样性，并充分利用终端的信息表达能力。(4)有限的带宽和计算能力移动 GIS 终端的通信能力和计算能力与桌面系统相比，是非常弱的，这就要求移动GIS 采取比

7、桌面GIS 更小的数据量和更加优化的算法。特别是当把移动终端当作GIS 前端数据采集系统时，由于其要进行频繁的数据插入、删除与查询，对数据的存储结构、空间索引方式都提出了新的要求。实验表明，常规的数据组织和空间索引方式应用于移动GIS 终端时，有比较大的局限性，满足不了人们对移动设备响应速度的需求2。2 空间索引算法的性能比较在 GIS 中，对于空间数据的组织来说，关键问题是空间数据的索引与检索，空间索引的性能优劣直接影响着空间数据库和地理信息系统的整体性能，它是GIS 的一项关键技术3。对于空间索引，学者们进行了大量的研究，常见的空间索引算法有BSP 树、K-D-B 树、R 树、R+树、CE

8、LL 树、四叉树等4。除此之外，简单的网格型的空间索引也有着广泛的应用，如 ESRI 的软件 ArcSDE 就使用了一种改进的网格索引。网格索引是一种多对多的索引，即一个空间对象可能跨越/穿越多个网格，而一个网格往往包含多个空间对象。这种多对多的关系会导致冗余，因为一个对象的ID 号可能被多个网格重复记录。这种冗余不仅是存储上的，而且在搜索算作者简介：赵波(1965)，男，副教授、博士，主研方向：地理信息系统应用研究；边馥苓，教授、博士生导师收稿日期：2006-08-25 E-mail：名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 3 页 -87法上也要进行额外的排重处理，并且

9、网格划分得越细，搜索的精度就越高，当然冗余也越大，耗费的磁盘空间和搜索时间也越长。网格划分的精细程度取决于几何对象的大小和数量。当被索引的对象大小差别很悬殊时，网格索引会遇到另外一个难题：网格划分小到什么程度合适？网络划分得过于精细，会导致冗余太大，索引数据的存储量也可能成倍增加，甚至索引的存储量会超过数据本身，此时如果进行大范围查询，也会影响速度；网格划分得过于粗略，小对象不能精确定位，过多的几何对象落在同一个网格上，降低了搜索的准确度。为此有些软件采用多重网格索引来避免这一问题，这在一定程度上能够提高搜索速度，但也会导致更多的数据冗余。网格法由于必须预先定义好网格大小，因此它不是一种动态的

10、数据结构5。四叉树（quadtree）6和 K-D 树7对分布不均匀的空间数据对象来说，是一种非重力平衡的树结构，很难设计高效的搜索算法，不利于各种GIS 搜索算法的优化；K-D-B 树8仅仅适用于点数据；而对于R 树9来说，它像 B-Tree 一样，索引记录的叶子结点包含指向数据对象的指针，是一种重力平衡的树结构；R*树10也是一种很好的结构，它更适用于点状数据。R-树是一种重力平衡树，其设计满足空间搜索访问尽量少的结点的要求，是一种动态结构，应该是适合移动GIS 空间索引结构要求的空间数据索引结构。但通过实验表明，基于 R-树空间索引结构的更新计算量对于目前的移动设备来说还是太大。四叉树结

11、构的更新计算量与R-树相比要小得多，但由于其非平衡的特点，使其搜索效率并不高。为了在搜索效率和更新代价之间取得一个平衡，本文提出了一种基于四叉树空间索引结构的动态四叉树算法，可以较好地解决上述问题。3 四叉树空间索引算法由于四叉树结构的生成和维护相对比较简单，且当空间数据对象分布比较均匀时，基于四叉树的空间索引可以获得比较高的空间数据插入和查询效率，因此四叉树是空间数据库中常用的索引之一。在生成常规空间四叉树索引结构时，首先要确定工作区域的范围，即图1 中工作区域边框的坐标，也就是空间四叉树的根节点。空间对象插入空间数据库时，如果某一节点中的空间对象数达到某一阈值，则需要将当前节点分解成2d个

12、子节点（其中 d 为空间的维数），以使每个节点中包含的空间对象数小于给定阈值。图2 所示为在已有的四叉树中插入空间对象 15以后的四叉树结构，其插入算法可以描述如下：(1)计算空间对象的MBR(minimum bounding rectangle)；(2)通过根节点R，搜索出所有包含该对象的叶子节点；(3)判断这些叶子节点所包含的空间对象数是否超出阈值；(4)如果节点中的对象数超出阈值，则把当前节点分解成2d；(5)对新生成的节点，重新计算落入其中的空间对象；(6)重复(1)(5)。当移动 GIS 系统终端用于数据采集时，由于事先并不知道具体作业范围的坐标，因此作业范围通常需要用户输入或事先设

13、定一个足够大的范围2。随着数据采集作业的进行，构成空间索引的四叉树也会不断增大，最后往往会生成一个严重不平衡的四叉树。由于基于四叉树的空间查询效率随着四叉树的深度增加会急剧下降，从而降低了检索空间对象的效率，这一点对于计算能力相对较弱的移动GIS 设备来说更为严重。12345678910111213abcdxyzt1,2,5,6 5,6,14 2,3,6 6a148,11,12,133,4,79,10,13bcdxyzt图 1 四叉树间索引结构12345678910111213abcdxyzt1,2,5,65,6,142,3,66a143,4,79,10,13bcdxyzt15mnqqmnpq

14、8,1111,158,1212,13,15R图 2 插入空间对象15 后的四叉树4 动态四叉树空间索引算法为了克服常规四叉树空间索引结构中的问题，本文提出一种对常规四叉树的改进算法，其算法要点为：在开始建立四叉树时，不需要事先确定工作区域的范围，只须把要插入空间数据库的第1 个对象的MBR 中心作为四叉树的顶点，随着数据采集工作的进行，对作业空间进行分解。具体算法如下：(1)根据第1 个插入的空间对象，确定四叉树空间的中心点，此四叉树的4 个叶子节点的某一个方向是开放的，如图3 所示；(2)计算空间对象的MBR；(3)通过图 3 搜索出所有包含该空间对象的叶子节点；(4)判断这些叶子节点所包含

15、的空间对象数是否超出阈值，如果节点中的对象数超出阈值，则分2种情况进行处理：1)如果是开放边界的节点，如图3 中的节点(d)，则要首先计算该节点内的包含所有空间对象的MBR，然后把该节点分解成4 个新的叶子节点；2)否则，如果该节点是非开放节点，如节点(e)，则直接把该节点分成 4 个新的叶子节点；(5)重新计算新生成节点中所包含的空间对象；(6)重复(1)(5)。12 345678 910111213 1415abcdabcdef h i m n p q1 1,5,11,15 1,2,3,4 efhi m n pq 6,5,14 8,11,156 8,9,12,13图 3 动态四叉树空间索引

16、从上面的算法可以看出，该算法无须用户在开始作业前人工确定作业区域的大小或事先预设一个非常大的作业区域，因此，该算法生成的四叉树的平衡性明显优于常规四叉树，而其计算量比R-树小得多。为了验证上述算法的可行性，笔者在PalmSurveying 系统2中，分别采用格网索引，R-树、四叉树和本文提出的动态 四叉 树 进行 了实 验，实 验 环境 为 运行WinCE 2.11的（下转第 93页）名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 3 页 -93user session中每个被记录的请求被转化成可以发送到Web服务器的 HTTP 请求。一个测试用例就是一个集合，包括与 user

17、session关联的 HTTP 请求，描述了用户通过与系统对话执行的事件序列。不同的策略被用来为收集的user session构造测试用例。有试验表明user session 数据能够比上述基于路径覆盖的方法更加有效地产生测试集，但由于这两大类技术所检测出来的错误是不同的，因此它们互为补充。3.3正向建模的同时生成测试用例除了上述首先建立WA 的测试模型，根据测试模型生成测试用例，还可以在开发早期正向建模的同时生成测试用例。在开发过程中，根据系统模型创建测试装具模块，作为针对特定领域的测试用例的环境，处理测试设置、清除等事务，同时编写实现真实测试逻辑的测试用例。实践证明，在该过程中，生成测试装

18、具模块和测试用例所需要的工作量只是全部工作量的一小部分，但带来显著的益处。4 Web应用测试存在的问题与发展方向综上所述，可以创建各种WA 模型，贯穿开发全过程、覆盖 WA 各方面特点，作为WA 测试的基础。测试人员可以针对被测 WA 的特点和测试需要选择合适的测试模型及其描述方法。但是总的来说，模型驱动的Web应用测试的相关研究呈现虎头蛇尾、衔接不畅的现状。建立被测系统模型只是MDT方法的一部分，模型驱动的WA 测试的各个阶段都应通过相应的测试模型描述并驱动执行，并且这些模型应在元模型层次定义，以实现模型之间的一致性转换与检测。但目前关于被测 WA 建模方法以及测试用例生成技术的研究相当广泛

19、，而关于如何采用模型驱动的方法执行测试、如何有效进行结果分析的研究则略显不足。虽然支持WA 自动化测试的工具有很多，但绝大部分都不是模型驱动的。为解决整个测试过程描述的完整性这一问题，OMG 组织推荐使用U2TP 为测试建模。在研究过程中，发现针对不同的测试目的，被测WA 系统的不同层次需要采用不同模型描述，应当允许用户自定义测试元模型，MDT 框架根据定义创建测试模型。此外，图1仅表示了测试的各个阶段所对应的测试模型，以及模型之间的转化。为了更好地将测试与开发同步进行，应当与MDA结合，将MDA 中的计算无关、平台无关和平台相关模型同步转化为对应的测试模型，驱动开发过程中各个阶段的测试。参考

20、文献1 Liu C H,Kung D C,Hsia P,et al.An Object-based Data Flow Testing Approach for Web ApplicationsJ.International Journal of Software Engineering and Knowledge Engineering,2001,11(2):157-179.2 Tonella P,Ricca F.Statistical Testing of Web ApplicationsJ.Journal of Software Maintenance and Evolution,200

21、4,16(1/2):103-127.3 Li Z,Tian J.Testing the Suitability of Markov Chains as Web Usage ModelsC/Proceedings of the 27th Annual International Computer Software and Applications Conference.2003:356-361.4 Offutt J,Liu S Y,Abdurazik A,et al.Generating Test Data from State Based SpecificationsJ.The Journal

22、 of Software Testing,Verification and Reliability,2003,13(1):25-53.5 Lucca G A D,Fasolino A R,Faralli F,et al.Testing Web ApplicationsC/Proceedings of the 18th International Conference on Software Maintenance,Maintaining Distributed Heterogeneous Systems.2002:310-319.6 Conallen J.Building Web Applic

23、ations with UMLM.Boston:Addison-Wesley Professional,2002.（上接第 87 页）PalmSizePC和运行 WinCE3.0 的 Pocket PC 两款掌上电脑。实验表明，采用R-树索引结构时，无论是WinCE3.0 还是WinCE2.11，当需要更新索引结构时，响应时间都是无法忍受的。当数据分布均匀时，格网算法或常规四叉树空间索引也可以获得较理想的数据插入和数据检索效率。而基于动态空间索引结构的系统在各种条件下，均可获得较理想的数据插入和数据检索效率。5 结论本文提出的动态四叉树空间索引结构算法有如下优点：在四叉树初始化时，不需要事先确

24、定作业区域的大小，并且在四叉树的分解过程中，可以根据空间对象的实际分布，自动确定叶子节点的大小，因此其平衡性优于常规四叉树算法；该算法生成的索引结构是一个可变分辨率的索引结构，当作业区域的数据分布不均匀时也有较强的适应能力；该算法的计算量与普通四叉树相当，明显小于R-树所需的计算量。实验表明，该算法用于移动GIS 设备时，其效果完全可以满足用户对数据插入和数据检索响应时间的要求。参考文献1 虞盛超.XML技术在面向数字城市的移动GIS 系统中的应用研究D.北京:北京大学,2002.2 赵波.掌上野外数据采集系统的实现及其关键技术J.测绘工程,2001,10(2).3 陈述彭,周成虎.地理信系统

25、导论M.北京:科学出版社,2000.4 宋关福.组件式地理信息技术研究R.北京:中国科学院遥感应用研究所,2000.5 Guttman A.R-trees:A Dynamic Index Structure for Spatial Searching C/Proceedings of the Conference of Association for Computing Machinery,Boston.1984.6 Finkel R A,Bently J L.Quad Trees a Data Structure for Retrieval on Composite KeysJ.Acta I

26、nformatica,1974,4(1):1-9.7 Bently J L.Multidimensional Binary Search Trees Used for Asso-ciative SearchingJ.Communications of the ACM,1975,18(9):509-517.8 Robinson J T.The K-D-B Tree:A Search Structure for Large Multidimensional Dynamic IndexesC/Proc.of ACM-SIGMOD81,1981.9 Hjaltason G R.Ranking in Spatial DatabaseC/Proceedings of the 4th Symposium on Spatial Database.1995.10 Beckmann N,Kriegel H P.The R*-tree:An Efficient and Robust Access Method for Points and Rectangles+C/Proc.of ACM SIGMOD 90.1990.名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 3 页 -