空间索引并行批量加载算法研究

摘要：空间索引是提高空间数据库查询性能的关键技术。空间数据具有海量、空间目标不规则、结构和关系复杂等特征，要动态地维护空间索引结构，传统R树的构建方法插入代价非常高。在深入分析空间索引批量加载算法基础上，面向多核处理器的新型硬件架构，基于OpenMP并行编程模型，实现Hilbert R树索引的并行批量加载算法。实验结果表明，相对于串行经典算法，该算法的并行效率接近50%，通过查询实验验证，并行加载算法保持了串行算法生成索引的优良查询性能。

关键词：空间索引； 批量加载； 多核； 并行加载算法

中图分类号：TN91934文献标识码：A文章编号：1004373X(2011)22009005

Research on Parallel Bulkloading Algorithm for Spatial Index

LIU Wenhong, XIONG Wei, WU Ye, CHEN Hongsheng

(College of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China)

Abstract： Spatial index is a key technology for improving the inquiry performance of spatial database. As the spatial data has the characteristics of massive amount of data in the database space, irregular space target, complex structure and relationship, the inserting cost of the traditional R tree loading algorithm is very high to dynamically maintain the spatial index structure. Based on indepth analysis of spatial index bulkloading algorithm, the Hilbert Rtree index parallel bulkloading algorithm based on multicore hardware architecture was realized by the aid of OpenMP parallel programming model. Experimental data shows that, compared with the classic serial algorithm, the parallel efficiency of this algorithm is close to 50%. The results of inquiry experiment certify that the parallel bulkloading algorithm maintains the good query performance of the serial algorithm.

Keywords： spatial index; bulkloading; multiprocessor; parallel loading algorithm

收稿日期：20110631

基金项目：国家自然科学基金资助项目（61070035，60902036，40801160）；高等学校博士学科点专项科研基金（20104307110017）；国家高技术研究发展计划（“863”计划）课题资助（2011AA120306）0引言

随着国家空间基础设施建设的迅猛发展和各种地学相关信息的爆炸性增长，利用空间数据库来存储和管理海量空间数据大势所趋［1］。空间索引作为空间数据库的关键技术，是估计空间实体表达形式多样，数据量庞大，空间操作计算复杂等特点，按一定顺序排列的一种数据结构，主要用于提高系统对空间数据获取的效率。

R树是B树在k维空间上的自然扩展［2］，传统R树的构建是从空树开始，利用传统的插入算法逐个插入记录，直至生成整个R树，称为OBO（One by one）方法。由于要动态地维护空间索引结构，该方法的插入代价非常高，特别对于海量空间数据而言，索引的创建过程将耗时巨大。因此，面向海量空间数据处理的应用需求，需要寻求高效的R树静态批量操作技术，在维持和提高查询性能的前提下，尽可能提高R树的静态加载速度［3］。

本文综述了空间索引批量加载算法，并结合相关研究对这些算法进行了分析与评述，基于Kamel和Faloutsos提出的Hilbert R 树压缩算法，对该算法的并行性进行分析，最终实现基于多核硬件架构的Hilbert R 树并行算法。通过实验，将设计的索引并行批量加载算法与传统的串行算法做性能比较，并提出修改意见和今后的研究方向。

1相关研究

1.1基于R树的静态批量加载技术

R树批量加载技术又称压缩技术。在数据为已知且相对静态的情况下，对已知数据进行有效的预处理，提高数据加载速度，建立结构优化的R树，改善空间存储利用率，从而获得优良的检索性能，是压缩技术的初衷。采用静态加载技术的R树称为静态R树。

第一个基于R树的压缩算法由Rousopoulos等提出，用以建立能够达到100％空间利用率的压缩R树。其基本思想是根据空间对象最小边界矩形的一个角点的x坐标或y坐标对空间对象进行排序，然后用这些有序的空间对象逐个压满树的叶结点，自下而上，一次一层，递归生成最终的压缩R树。由算法可知，在压缩R树的每一层中，除了最后一个结点可能不满外，其他所有结点都是满的，因此，可以获得几乎100％的空间利用率。但是，该算法仅在点数据的点查询方面优于线性分裂或平方分裂的R树和R*树，而对于域查询和空间扩展数据（如矩形等）性能较差。

Kamel和Faloutsos提出了一种基于分形曲线构建静态R树的压缩算法，利用分形Hilbert曲线对已知空间数据对象进行更好的一维排序［4］，以获得优良的压缩效果。他们设计了不同的变体进行了大量的实验，最终“2DC”（利用空间对象MBR中心点的Hilbert码进行排序）变体性能最优［5］。该变体在查询性能上不仅优于Rousopoulos等的packed R树，而且优于当时R树的所有动态版本，如R+树、R*树等，且特别适合现实的、不规则分布的数据。

与基于排序的批量加载方法不同，Bercken等提出的批量加载方法是一种基于缓冲的技术，也可以认为是基于种子树方法的推广，它并不局限于R树，而是适用于所有基于树的空间索引结构［6］。该方法借鉴了buffer树的思想，通过Lazy buffer技术，利用一个有效的临时数据结构，一次一层地建立整个索引结构，避免了数据排序预处理过程。

Bercken等通过性能分析得出该算法的R树插入代价达到了外排序的下界，但是并没有进行具体的实验证明和性能比较。

最后根据测得的数据计算time_total的并行加速比和并行效率，分析该并行算法的优化效能。

定义 1： 并行加速比=串行执行时间÷并行执行时间；

定义 2： 并行效率=加速比÷处理器个数。

统计Step 2的时间开销，如图3所示。

图3Step 2索引构建初始化时间统计Step 3的时间开销，如图4所示。

图4Step 3排序时间统计Step 4的时间开销，如图5所示。

图5Step 4构建R树时间统计索引生成总的时间开销，如图6所示。

图6索引构建总时间从图4~图6中可以看出，对Hilbert R树算法中的Step 2初始化、Step 3排序、Step 4构树部分所做的并行优化从时间上看都有不同程度的提高，随着实验数据的增大，发现在开启4或8个线程时效果最好。通过对串行算法和并行算法的实验对比，在分别计算在开启不同线程数情况下的并行加速比和并行效率，进一步分析该并行优化算法的加速效率，如图7和图8所示。

图7总时间的并行加速比图8总时间的并行效率通过上述试验结果分析可知，本文设计的并行算法在多核硬件环境下对索引构建的效率有了较大提升，在调用线程数为4时并行效果最明显，并行加速比达到1.9左右，并行效率在0.48附近。由此得出结论，采用OpenMP对Hilbert packed R树算法进行并行优化效果明显，可以较大地提高索引的批量加载效率。

3.3索引性能测试

为了验证Hilbert packed R树算法经过并行优化后能否维持原经典串行算法构建索引的优良性能，对2种算法构建的索引分别进行查询测试。由于点查询可以看作是域查询的特殊情况，因此本文采用域查询方式进行实验。

以第1幅图（包含2 092 079个对象）作为实验对象，设定选择率分别为1%，2%，3%，4%，5%，统计磁盘I/O数和查询时间，结果如图9，图10所示。

图9磁盘I/O对比图10查询时间对比

通过上述的试验结果分析可知，Hilbert R树并行算法和串行算法生成的索引查询性能基本一致，验证了Hilbert R树算法的并行化设计并没有降低索引的优良性能。

4结语

在空间索引的创建过程中，许多专家学者正在致力于提高索引批量加载效率的研究，提出了很多经典算法或是在前人的基础上进行了改进。本文结合当今高速发展的多核CPU技术，在深入学习Hilbert R树经典算法的基础上，通过调用OpenMP接口实现基于多核的并行化设计，在保证索引性能的前提下使得并行加速比达到1.9，并行效率在0.48左右。相关的研究内容和研究方法有待进一步的探讨，仍需要经过更加详细的测试，以期在空间数据处理领域得到实际应用。

参考文献

［1］吴炳方,张明金.地理信息系统的发展[J].地理学报,1994,49(z1):633640.

［2］GUTTMAN A. Rtrees: a dynamic index structure for spatial searching [C]// Proceedings of ACM SIGMOD. Boston, MA: ACM, 1984: 4757.

［3］顾军,吴长彬.常用空间索引技术的分析[J].微型电脑应用,2001,17(12):4042.

［4］KAMEL I., FALOUTSOS C. On packing Rtrees [C]// Proceedings of CIKM. Washington DC, USA: CIKM, 1993: 490499.

［5］KAMEL I, FALOUTSOS C. Hilbert Rtree: an improved Rtree using fractals [C]// Proceedings of 20th VLDB. Santiago, Chile: VLDB, 1994: 500509.

［6］张明波,陆锋,申排伟,等.R树家族的演变和发展[J].计算机学报,2005,28(3):289300.

［7］赵园春，李成名，赵春宇.基于R树的分布式并行空间索引机制研究[J].地理与地理信息科学,2007(11)：3841.

［8］何小苑，闵华清.基于聚类的Hilbert R:数空间索引算法[J].计算机工程，2009(9)：4042.

［9］陆锋，周成虎.一种基于Hilbert排列码的GIS空间索引方法[J].计算机辅助设计与图形学学报,2001,13(5)：424429.

［10］陈国良，孙广中，徐云，等.并行计算的一体化研究现状与发展趋势[J].科学通报，2009，54(8):10431049.

［11］FALOUTSOS C, KAMEL I. Beyond uniformity and independence: analysis of Rtrees using the concept of fractal dimension [C]// Proceedings of PODS. Minneapolis, Minnesota: PODS, 1994: 413.

［12］张明波，陆锋，申排伟，等.空间索引R树研究：批量操作技术[C]//中国地理信息协会第8届年会论文集，北京：科学出版社，2004:2832.

［13］赵晓燕.数字常规调幅解调器的DSP算法及实现[J].电子科技，2010（3)：9092.

［14］刁树民.数据库应用系统中索引重建技术和维护[J].现代电子技术，2006,29（21)：7879.

［15］王珂敏，汤晓安，陈敏，等.基于金字塔模型的地形网格数据研究[J].现代电子技术，2008,31（21)：3942.

(上接第89页)

4结语

基于J2EE且以MVC模式设计出来的教学管理信息系统层次清晰、功能强大、易于管理，在教学管理过程中发挥着巨大的作用，必将得到广泛的应用。

参考文献

［1］张勇.基于J2EE的高校信息管理系统的研究与设计［J］.电脑知识与技术,2009(7):1013.

［2］闫振福,张晓诺.基于J2EE平台的教学管理系统设计实现［J］.中国教育信息化,2008(15):103105.

［3］徐小娟,黄新.基于J2EE技术的远程教学管理系统的设计［J］.科技风,2008(9):9095.

［4］张宏森.四层B/S结构及解决方案［J］.计算机应用研究，2002(9):2122.

［5］杨鹏.基于J2EE和工作流技术架构的教务管理系统的设计与实现［D］.长沙：湖南师范大学,2003.

［6］倪晓秋.J2EE 开发案例［M］.北京：中国水利水电出版社，2005.

［7］徐进明.JSP 网站开发技术［M］.北京:清华大学出版社,2001.

［8］MARTY Hall. Servlet与JSP 核心技术［M］.北京:人民邮电出版社,2001.

［9］欧阳翠萍.基于J2EE的高职院校教学管理信息系统［J］.当代教育论坛,2008(3):6567.

［10］李迟颖.基于MVC设计模式的Java应用程序研究与开发［J］.电脑知识与技术,2006(8):102104.

作者简介: 王萍利女，1972年出生，陕西渭南人，硕士研究生，讲师。主要研究方向为计算机科学技术。