云计算环境下空间索引构建研究_李振举

《云计算环境下空间索引构建研究_李振举》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

第38卷第10期测绘与空间地理信息Vol．38，No．102015年10月GEOMATICS＆SPATIALINFOＲMATIONTECHNOLOGYOct．，2015云计算环境下空间索引构建研究李振举，李学军，杨晟，刘涛(装备学院信息装备系，北京101416)摘要:空间数据索引对于空间数据管理和分析具有重要作用，与数据处理速度和效率密切相关。随着人类社会进入大数据时代，遥感矢量数据具备了大数据的特点，传统的空间索引构建方法无法有效满足矢量大数据处理的需求，为此引入云计算环境来进行空间索引构建，目的是提高空间索引构建速度。首先，对常见的空间索引及现阶段云计算环境下基于MapＲeduce模型的空间数据管理进行了综述;然后以云计算环境下Ｒ树索引构建为例，对云计算环境下空间索引的构建进行了研究;最后，通过实验验证，证明了云计算环境下空间索引构建的速度与单机索引构建相比，加速比为28～40倍;在相同云环境下，网格索引构建速度最快，Ｒ+索引构建速度相对较慢。关键词:云计算;空间索引构建;遥感矢量数据;Ｒ树;Ｒ+树;网格索引中图分类号:P208文献标识码:A文章编号:1672－5867(2015)10－0013－05SpatialIndexBuiltinCloudComputingEnvironmentLIZhen－ju，LIXue－jun，YANGSheng，LIUTao(DeptofInformationEquipment，AcademyEquipmentofPLA，Beijing101416，China)Abstract:Spatialdataindexissignificantlyimportantforspatialdatamanagementandanalysis，whichisrelatedwithdataprocessspeedandefficiency．Withthehumansocietyenteringintothebigdataera，remotesensingvectordataisakindofbigdata．Thetra-ditionalspatialindexconstructionmethodisinsufficientforthevectordataprocessing．Thispaperleveragedthecloudcomputingenvi-ronmentforspatialindexconstructionwiththeaimtoimprovetheconstructingspeed．ThepaperatthebeginninggaveareviewonthenormalspatialindexandspatialdatamanagementbasedonMapＲeducecloudingcomputingmodel，thenanalyzedthespatialindexconstructionincloudcomputingtakingtheＲtreeindexconstructionasanexample．AtlastanexperimentresultsillustratedthatthespatialindexconstructingspeedissignificantlyimprovedincloudcomputingcomparedwithsinglePCenvironment，andinthesamecloudenvironment，gridfileconstructionspeedishigherthanＲtreeandＲ+treeindex．Keywords:cloudcomputing;spatialindexbuilt;remotesensingvectordata;Ｒtree;Ｒ+tree;gridfile［1－3］在最短路径分析和叠加分析等。0引言为了有效地管理不断增长的遥感矢量数据，学术界遥感数据在气象、航空航天、国土资源调查和环境监进行了许多相关的研究，其中，空间数据索引是空间数据［4］测等领域具有非常重要的作用。常见的遥感数据分为栅管理的关键技术之一，在地图数据库和地理信息系统格数据和矢量数据两种。考虑到空间数据量的海量性和(GIS)中应用广泛，索引构建性能会对整体空间查询的性地理数据模型的复杂性，提前在这些数据上建立索引有能产生影响，可以直接影响空间数据库的数据定位时间利于加速后期的处理和计算。矢量数据包括点、线和多和数据响应时间。空间数据索引保存空间数据和空间对边形等类型。随着遥感技术的发展，当前遥感矢量数据象的空间关系，按照一定的顺序进行排列，其包含空间对的数量、种类和增长速度都达到了大数据的要求，成为遥象的概要信息，对象的标识、外接矩形及指向空间对象实感大数据的一个组成部分。目前GIS领域栅格数据的相体的指针。关研究比较充分，而矢量数据的研究相对较少，主要集中收稿日期:2015－06－05基金项目:部委级项目(513150701)资助作者简介:李振举(1987－)，男，河南林州人，助理工程师，通信与信息系统专业博士研究生，主要研究方向为云计算、遥感大数据管理。 14测绘与空间地理信息2015年从图1可以看出，单就两个矢量数据集而言，其包括1研究现状的矢量数据类型就有14种，数据总量接近500G。在进行云计算环境下空间数据索引构建相关研究之随着遥感矢量数据的增加，与之相应的元数据的数前，首先对遥感矢量大数据的相关概念和云计算环境下量和空间数据对象的数量也在不断增加，图2显示了Ti-基于MapＲeduce编程模型的空间数据处理相关研究进行ger和OpenStreetMap一些典型的矢量遥感数据的数据记综述。录的数量。1．1遥感矢量大数据遥感矢量数据作为遥感数据的一个重要类型，近年来随着遥感和信息技术的发展，其数据的量级、数据的类型和数据的增长速度发生了较大的变化，已不断呈现出大数据的趋势。遥感矢量数据的一个特点是数据的数量级不断增加。随着智慧城市等概念的提出，基于位置服务的概念不断发展，与之相关的空间矢量数据不断地增加，从MB的级别增长至GB级别。以Tiger数据集和OpenStreetMap数据集为例，Tiger数据集来自美国人口普查局的Tiger文件，包括区域地标数据(全称Arealandmark，简称arealm，图2遥感矢量数据数据记录的数量下同)、区域水文数据(AreaHydrography，areawater)、边界Fig．2Numberofremotesensingvectordata数据(AllEdgesCombined，edges)、线性水文数据(Linear从图2可以看出，随着遥感矢量数据的数据量级的增Hydrography，linearwater)、道路网数据(PrimaryＲoads，加，其响应的数据记录的数量也呈现不断增加的趋势。primaryroads)和5位邮编的地区数据(5－DigitZIPCode1．2空间数据索引相关研究TabulationArea，zcta510)等。OpenStreetMap作为开源在空间数据索引是典型的空间矢量数据管理的方式之线地图，其包括的数据种类和数据量更多，即地球所有的一，核心思想是对空间数据进行组织抽取，得到相关的索点数据(AllPointsontheplanet，AllNodes)、所有地图对引信息，通过管理较小的数据实现对较大的数据的管理，象的提取数据(Allextractedmapobject，AllObjects)、所有进而提高空间数据管理的效率。常见的空间数据索引包建筑的边界数据(Boundariesofallbuilding，Buildings)、所［5］括网格索引、Ｒ树索引和Ｒ+索引等。有墓地的数据(Boundariesofcemetery，Cemetery)、湖边界网格索引的原理是将空间实体所在的空间范围划分数据(Boundariesofparksorgreenareas，Parks)、公园和绿成一系列大小相同的网格，对空间位置进行网格分化。色区域边界数据(Boundariesofparksorgreenareas，Ｒ树索引的效率相对较高，是B树在多维空间上的Parks)、有邮编的区域边界数据(Boundariesofpostalcode扩展。Ｒ树的结构类似于B+树的平衡树。Ｒ树包括三areas，Postalcodes，Ｒoadnetwork)、运动区域的边界种节点类型，即根节点、中间节点和叶子节点，其中，中间(Boundariesofsportingareas，Sports)，以及地球上所有道节点存储所有叶子节点的最小外包范围，叶子节点存储路网和街道的边界数据(Ｒoadnetworkrepresentedasindi-的是空间对象对应的最小外包范围。Ｒ树索引采用空间vidualroadsegements，Ｒoads)等。图1显示了2012年Ti-聚集的方式将相邻空间实体分到一起，组成更高级的节ger数据集和OpenStreetMap数据中一些典型的矢量数据点。在更高级根节点的最小外包矩形进行聚集，形成更的数据量的大小。［6］高一级的节点，直至所有的实体组成一个根节点。Ｒ+树是为了解决Ｒ树存在的不足而产生的，其同一个节点下的兄弟节点对应的区域没有重叠，这样做的优点是可以消除Ｒ树因为节点之间重叠产生的“死区域”，可以减少无效的查询树，提高索引构建效率;缺点是为了确保空间区域无重叠，在插入和删除操作时会降低索引效率，而且Ｒ+树对于跨区域的空间对象的存储还会产生冗余，并且数据量越大，冗余越多。这种空间划分方式可以提高空间检索的效率，如图3所示。1．3基于MapＲeduce的空间数据处理MapＲeduce编程模型是目前云计算环境下事实上的图1遥感矢量数据数据量［7］标准。经过长时间的发展，该模型在数据挖掘、信息处Fig．1Ｒemotesensingvectordata理和机器学习等多个领域等到了应用。MapＲeduce可以划分为Map、Ｒeduce、Shuffle、Merge等多个阶段。如图4 第10期李振举等:云计算环境下空间索引构建研究15数据的服务，其数据显示的方式和MNTG类似，其支撑的数据库使用GoogleKML格式和ESＲI形状数据。其所有的数据都是通过MapＲeduce从OpenStreetMap上获取。使用Pigeon脚本来创建点和连接线，进而形成空间数据的形状。在产生数据集之后，为每一个数据集创建Ｒ+树索引。［14］图3空间数据分布不均匀示意图SHAHED是一个分析NASA卫星数据的工具，可Fig．3Spatialdatadistributionisnotuniform．以用来分析和探索NASA提供的公开的遥感数据。SHA-所示，其中最重要的阶段为Map阶段和Ｒeduce阶段。HED提供了一个网络接口，可以用来浏览地图和展示选定区域的卫星数据，也可以显示选定区域特定时间段内的温度变化情况。用户只需选定区域就可以执行相关的操作，包括特定区域的植被不规则变化模式等。这个系统对可用的数据集进行预处理产生特点地图，而后通过对外服务使其可以被访问。2云计算环境下的空间索引构建图4MapＲeduce阶段划分在云计算环境下设计时空索引的优点是可以允许用Fig．4MapＲeducestagedivision户使用已有的空间数据索引来减轻工作量，提供了针对在Map阶段，输入文件复制到MapＲeduce的文件系不同数据集的时空划分机制，可以使数据逐渐地添加到统，按照用户设定的逻辑划分为小文件;Ｒeduce阶段通过索引中，过程更简单。网络密集型的作业对Map阶段产生的中间值进行处理。2．1Ｒ树索引构建Map阶段相同的key值将会在相同的Ｒeducer上进行工Ｒ树索引在云空间数据库中的作用是管理非均匀分作，输出结果同时写入到文件系统中。布的数据。Ｒ树索引构建过程中，空间数据记录不采用备Map:(keyi，valuei)→list(keym，valuem)份的方式，目的是减少分割时产生的区域重叠，这样有利Ｒeduce:list(keym，valuem)→(keyo，valueo)于范围查询。分割产生的数据可以直接输出到Hadoop文MapＲeduce编程模型非常简洁，且具有时序性的特件系统，而不需要另外的步骤。云计算环境下使用Ma-点，使用该模型处理一般问题时，需要按照MapＲeduce的pＲeduce构建Ｒ树索引经3个步骤完成。运算逻辑将已有的算法转换为独立的Map函数和Ｒeduce1)数据划分。使用定制的空间数据划分引擎将数据函数。该模型初始目的是计算大数据，对于数量较小的分布到整个集群上，使用Ｒ树索引对非均匀数据进行划数据处理效率不高，有可能会出现调度、效率和资源利用分。在Map阶段设定一个采样概率，对空间对象进行采［15］率下降等问题。样，如果待处理的空间对象满足采样条件，则对数据进［8］在现阶段的研究中，刘义等研究了云计算环境下行采样，否则不执行操作;在Ｒeduce阶段对所有Map阶基于MapＲeduce的Ｒ－树索引的k－近邻连接查询处理段的输出结果进行处理，并按照一定的顺序对结果进行［9］过程，证明了该算法的效率和可扩展性能。CG_Hadoop排序，由Ｒ－1个空间划分点，将空间对象划分成Ｒ个相是一个基于MapＲeduce的几何对象处理库，其支持的操等的空间区域，如图5所示。［16］作包括多边形连接、边界线求解、凸集、最远和最近距离2)本地索引构建。根据串行算法构建Ｒ树，将第求解。HydroCloud是一个基于云的水文数据集成和分析一步分割产生的数据以Ｒ树索引的结构独立进行存储。系统。该步骤也是一个MapＲeduce过程，输入数据和步骤1一［10］SpatialHadoop是一个开源的空间数据获取系统。样，区别在于Map函数的作用是根据函数f()x对空间对通过扩展Hadoop可以支持高等语言、空间索引、空间Ma-象进行分割，Ｒeduce的作用是根据输入对象构建Ｒ树，进［11］pＲeduce部件和一系列的空间操作。HadoopGIS是构建而得到最终的输出数据。结果以键值对格式文件进行存在Hadoop环境上的空间数据查询系统。储，并将子树索引地址和最小外包框MBＲ写入根目录。［12］3)全局索引构建。将步骤2产生的所有单独的Ｒ树MNTG是一个用来产生交通数据的网络服务，其面临的主要挑战是在发送到数据产生引擎时提取选定区域文件通过单线程处理合并成一个文件，同时每个分区产的道路网络。所有的道路网络数据集约100GB，如果在生一个独立索引，最终结果保存在Hadoop集群的分布式所有数据集上执行查询操作非常耗时。解决这个问题的文件系统中，如图6所示。方法是建立Ｒ+空间索引，并且使用该索引来加速指定区2．2网格索引构建和Ｒ+树索引构建域的查询。网格索引在空间数据管理中的作用是管理均匀分布的［13］TAＲEEG是一个基于网络的从OpenStreetMap抽取数据。使用MapＲeduce构建网格索引也是按照Ｒ树构建的 16测绘与空间地理信息2015年试二对Hadoop环境下三种典型的索引构建性能进行对比，空间对象的数量分别选取31232个、62464个、93696个、124928个、156160个。得到的实验结果如下。1)以单机环境下Ｒ树索引构建性能为例，得到的实验结果如图7所示，根据其时间，计算出的加速比随时间变化如图8所示。图5空间对象分块计算步骤图7单机和Hadoop集群Ｒ索引构建时间对比Fig．5SpaceobjectblockcalculationstepFig．7ＲindexconstructiontimecomparisonbetweensinglemachineandHadoopcluster图6合并并生成最终Ｒ树Fig．6MergeandgeneratethefinalＲtree3个步骤进行，主要区别在于步骤1对空间数据进行划分的图8不同空间对象数量Ｒ索引构建加速比时候，网格索引更适合处理分布比较均匀的空间对象。Fig．8ConstructionofＲindexfordifferentspaceobjectsＲ+树索引的目的也是为了管理非均匀分布的数据。根据实验结果可以看出，采用Hadoop集群之后，索引Ｒ+树是在Ｒ树的基础上确保需要进行复制的空间数据构建时间的加速比在28～45之间，极大地提高了空间对分割且不相交。Ｒ+树在空间连接时效率更高，其可以独象的Ｒ树索引构建效率。立处理每个相交的区域。构建Ｒ+树索引需要的3个步2)空间对象个数相同的情况下，在Hadoop集群中对骤也与Ｒ树构建的步骤类似，区别在于步骤1中如果空典型的三种索引网格索引、Ｒ树索引和Ｒ+索引构建性能间数据记录产生重叠，则使用Ｒ+树索引结构进行空间数进行测试，得到实验结果如图9所示。据划分。3实验和结果分析3．1实验环境构建的Hadoop集群运行在VirualBox上，由3个虚拟机Hadoop集群组成。其中，虚拟机的操作系统为Ubuntu10．04LTS，内存1024MB，块大小为64MB。实验数据集，选自某地区的矢量数据。为了便于处理，数据采用csv格式，每一行存储一个空间位置信息数据。在利用MapＲeduce进行处理时，直接按照文本格式图9Hadoop集群不同空间对象数量逐行读取即可。情况下索引构建时间3．2实验结果Fig．9Indexconstructiontimeofdifferent为了测试Hadoop集群下索引构建性能，本文做两个spaceobjectsinHadoopcluster测试。测试一与单机环境下索引构建性能进行对比，测通过图9可以得到如下结论，相同空间对象数据量的 第10期李振举等:云计算环境下空间索引构建研究17情况下，Grid索引构建速度最快，Ｒ树其次，Ｒ+树索引构［8］刘义，景宁，陈荦，等．MapＲeduce框架下基于Ｒ－树建相对最慢;随着空间对象数量的增加，空间索引构建时的k－近邻连接算法［J］．软件学报，2013，24(8):间也会相应增加。1836－1851．［9］EldawyA，LiY，MokbelMF，etal．CG_Hadoop:com-4结束语putationalgeometryinMapＲeduce［C］．Proceedingsofthe21stACMSIGSPATIALInternationalConferenceon遥感矢量数据是遥感数据的一个重要类型，对于空AdvancesinGeographicInformationSystems，Orlando，间对象显示、基于位置的服务等领域应用广泛。空间索FL，USA:ACM，2013:294－303．引作为管理遥感矢量数据的一种典型技术，在处理矢量［10］EldawyA，MokbelMF．SpatialHadoop:AMapＲeduce大数据时索引构建速度会成为瓶颈。本文通过引入云计FrameworkforSpatialData［C］．IEEEInternationalCon-算环境Hadoop利用MapＲeduce模型构建空间索引，与单ferenceonDataEngineering，ICDE2015，Seoul，South机索引构建相比，提高了索引构建速度。同时发现，在相Korea:IEEE，2015．同的云环境下，网格索引构建速度相对较快，其次为Ｒ树［11］AjiA，WangF，VoH，etal．Hadoopgis:ahighper-索引，再次为Ｒ+树索引。下一步研究将把构建的索引应formancespatialdatawarehousingsystemovermapreduce用到空间数据的查询和分析中，并对其性能进行测试。［C］．ProceedingsoftheVLDBEndowment，Trento，Ita-ly:VeryLargeDatabaseEndowment，2013:1009－参考文献:1020．［1］杨宜舟，吴立新，郭甲腾，等．一种实现拓扑关系高效并［12］MokbelMF，AlarabiL，BaoJ，etal．MNTG:anextensi-行计算的矢量数据划分方法［J］．地理与地理信息科bleweb－basedtrafficgenerator［M］．Springer，2013．学，2013，29(4):25－29．［13］AlarabiL，EldawyA，AlghamdiＲ，etal．TAＲEEG:a［2］MadduriK，BaderDA，BerryJW，etal．Parallelshor-MapＲeduce－basedwebserviceforextractingspatialdatatestpathalgorithmsforsolvinglarge－scaleinstancesfromOpenStreetMap［C］．Proceedingsofthe2014ACM［C］．9thDIMACSImplementationChallenge———TheSIGMODinternationalconferenceonManagementofdata，ShortestPathProblem，NewJersey，USA:ＲutgersUni-NewYork，NY，USA:ACM，897－900．versity，2006:1－39．［14］EldawyA，MokbelMF，AlharthiS，etal．SHAHED:A［3］WaughTC，HopkinsS．AnalgorithmforpolygonoverlayMapＲeduce－basedSystemforQueryingandVisualizingusingcooperativeparallelprocessing［J］．InternationalSpatio－temporalSatelliteData［C］．InternationalConfer-JournalofGeographicalInformationScience，1992，6enceonDataEngineering，ICDE2015，Seoul，SouthKo-(6):457－467．rea:IEEE，2015．［4］史英杰，孟小峰．云数据管理系统中查询技术研究综述［15］CaryA，SunZ，HristidisV，etal．Experiencesonpro-［J］．计算机学报，2013，36(2):209－225．cessingspatialdatawithmapreduce［C］．Scientificand［5］郭菁，周洞汝，郭薇，等．空间数据库索引技术的研究StatisticalDatabaseManagement，NewOrleans，LA，［J］．计算机应用研究，2003，20(12):12－14．USA:Springer，2009:302－319．［6］吴信才．空间数据库［M］．北京:科学出版社，2009．［16］LiuY，JingN，ChenL，etal．Parallelbulk－loadingof［7］DeanJ，GhemawatS．MapＲeduce:simplifieddatapro-spatialdatawithMapＲeduce:AnＲ－treecase［J］．Wu-cessingonlargeclusters［J］．CommunicationsofthehanUniversityJournalofNaturalSciences，2011，16ACM，2008，51(1):107－113．(6):513－519．［编辑:胡雪］(上接第12页)震灾情场景模拟系统［J］．自然灾害学报，2011，20(3):参考文献:145－150．［1］刘文全，贾永刚，卢芳．基于ArcGISEngine的渤海石油［5］史廷玉，赵保成，谢树俊．基于三维GIS的制药行业消防平台溢油应急决策支持系统的设计与实现［J］．海洋环安全应急救援平台设计和研究［J］．南开大学学报，境科学，2010，29(6):866－869．2014，47(4):48－53．［2］方力．ArcGIS在重点污染源监控系统中的应用［J］．环［6］骆社周，朱岳．基于SketchUp与ArcGIS的虚拟校园建设境保护与循环经，2010(4):58－60．［J］．测绘与空间地理信息，2014，37(3):4－6．［3］黄金华，李国忠，孙晓茹，等．石油化工行业突发事故应［7］黄伟群．浅谈社会安全视频监控系统智能分析技术的实急指挥系统之初探［J］．城市勘测，2009(3):13－15．际应用［J］．广东公安科技，2012，109(3):51－55．［4］兰日清，王自法，丰彪．基于ArcGIS技术的桥梁隧道地［编辑:任亚茹］