2014 NO.09Science and Technology Innovation Herald科技创新导报基于MapRedue的大规模矢量空间数据选择查询处理
何涛 刘强 郑泽忠 刘帅
(电子科技大学资源与环境学院 四川成都 611731)
摘 要：为高效地处理大规模矢量空间数据，基于Hadoop的并行计算框架MapRedue，实现了一种分布式的矢量空间数据选择查询处理方法。首先，分析OGC简单要素标准与Hadoop的Key/Value数据模型，设计了可存储于Hadoop HDFS的矢量文件格式；其次，根据两阶段的过滤-精炼策略，对Map 输入数据分片、选择查询处理过程及Reduce结果合并等关键步骤进行了详细阐述；最后，基于上述技术，利用Hadoop集群环境对所提出的方法进行验证，该方法具有较好的可行性和较高的效率。关键词：MapRedue 选择查询 存储模型 Key/Value 矢量数据文件中图分类号: 文献标识码：Ａ 文章编号：1674-098X(2014)03(c)-0193-02
Abstract:The paper has achieved a vector spatial data distributed select query method based on Hadoop parallel computing framework MapRedue,in order to efficiently process massive vector spatial data.Firstly,the paper designs vector file format able to store in Hadoop HDFS,by analyzing OGC Simple Features standard and Hadoop’s Key/Value data model.Then,the key procedures including data partitioning and select query processing mechanism of Map step,results merging of Reduce step etc. are elaborated in detail according to the two-stage filtration-Refining Strategies.Finally,based on the above technology,the proposed method which has good feasibility and higher efficiency is verified in the Hadoop cluster environment.Key words:MapRedue select query storage model Key/Value vector data file
随着全球空间数据集的急剧增长，海量空间数据带来了丰富的信息，而面对如此庞大和复杂的数据集，随之产生了数据存储与管理问题。国内外很多学者尝试利用Hadoop云计算技术处理矢量空间数据。张书彬等利用MapReduce并行处理空间查询的数据分割方法、副本避免方法实现空间查询[1]；赵彦荣等基于Hadoop提出了一种并行连接查询算法CHMJ[2],提高了连接查询的处理效率；尹芳等基于开源Hadoop 的矢量空间数据分布式处理研究；王永刚对Hadoop云计算平台下地理信息服务的若干关键技术进行了研究。
基于上述研究，该文以Hadoop分布式
[4]
[3]
文件系统存储矢量空间数据，根据空间查询处理的两阶段过滤与精炼策略，并充分利用MapRedue并行计算框架处理海量数据的优势，设计一种简单实用的选择查询方法，有效提高了对大规模矢量空间数据的查询处理效率。
能够作为其他空间查询操作（如空间连接查询和最近邻查询）的基础。代表性的空间选择查询包括空间点查询和空间区域查询。点查询(Point Query)通过给定一个查询点P和一个空间对象集M，查找出M中所有包含点P的空间对象。区域查询通过给定一个多边形区域R和一个空间对象集M，查找出M中所有与R相交或被R包含的空间对象。
1.2 MapReduce并行计算框架
Hadoop是一款开源分布式系统基础架构，它支持在商用硬件构建的大型集群上运行应用程序，实现对海量数据的分布式处理。其核心技术包括并行计算框架
1 基本概念
1.1 空间选择查询
在GIS中，常见的对空间矢量数据的查询有三种，即：空间选择查询、空间连接查询和最近邻查询。其中，空间选择查询和连接查询是最基本的查询操作。空间选择查询是最重要的一种空间查询操作，它
图1 矢量数据文件
图2 矢量数据查询时间
科技创新导报 Science and Technology Innovation Herald
Copyright©博看网 www.bookan.com.cn. All Rights Reserved.193
科技创新导报2014 NO.09Science and Technology Innovation Herald学术论坛
[3] 尹芳,冯敏,诸云强,等,基于开源
Hadoop 的矢量空间数据分布式处理研究[J].计算机工程与应用,2013(16).[4] 王永刚.基于Hadoop云计算平台的地
理信息服务若干关键技术研究[D].北京:中国科学院研究生院遥感应用研究,2011.
[5] 范建永,龙明,熊伟.基于HBase的矢量
空间数据分布式存储研究[J].地理与地理信息,2012,28(5):39-42.
MapReduce和分布式文件系统HDFS，分别是Google MapReduce和GFS的开源实现。MapReduce是一种并行计算的编程模型，用于大规模数据集（大于1TB）的并行运算。
3 实验与结果分析
3.1 实验环境与数据
实验平台使用1台计算机作为宿主机，安装VMware9虚拟机，同时虚拟出3台相同的计算机。三台虚拟机分别安装Linux操作系统，并部署Hadoop-1.0.0构成分布式处理集群，其中一台同时作为master节点和slave节点,另外两台作为slave节点。宿主机：CPU：AMD 5200+，内存：4.00 GB，操作系统：win7(64位)，开发环境：eclipse3.7.1；虚拟机：操作系统均为Ubuntu-11.10-desktop-i386，内存：512 MB。实验数据：矢量数据(数据量：168MB，133099个线空间对象)，格式：ESRI Shapefile文件。3.2 矢量数据查询实验
由空间选择查询算法可知，实验步骤如下：（1）将矢量数据存入HDFS；（2）选取查询窗口；（3）执行基于MapReduce的矢量数据过滤-精炼算法；（4）查询结果写入HDFS（图2）。
从实验结果可以得出，第一，当集群中节点数目相同时，随着查询数据量的增大，查询时间变长，是因为查询窗口包含数据条数增加，使得过滤-精炼过程的开销也相应变大。第二，对于同一个查询窗口，集群中节点数量增加，查询时间依次减小，其原因是Hadoop中默认块大小是64MB，HDFS上文件通常是按照64MB被切分为不同的数据块，每个数据块尽可能分散存储在不同数据节点中，并且每块对应一个Map任务，因此168MB的矢量数据对应3个Map任务，随着节点数增加，任务执行的并行程度提高，当节点数为3时，3个Map任务可以实现并行执行，查询窗口1,2,3相对于单节点的查询效率分别提高了13.3%、16.3%和15.08%。
2 基于MapReduce的空间选择查询
2.1 矢量数据存储模型
目前，开放地理信息联盟OGC（Open Geospatial Consortium）制定了许多与空间信息、基于位置服务相关的标准，其中简单要素模型（图１）是OGC最为重要的几何对象模型。简单要素几何对象中主要定义了点、线、面和集合对象。通过将空间对象与空间参考系进行关联，空间对象被抽象表达为空间参考系统(Spatial Reference System)所描述的几何体（Geometry）。大多数空间关系及空间分析都基于这个类层次体系进行研究，并且平台是独立的，可以应用到分布式计算系统。该文中同样采用简单要素模型来存储矢量数据。
2.2 HDFS矢量数据文件
在OGC简单要素模型中，可以采用WKT（Well-Known Text）和WKB（Well-Known Binary）两种编码方式表示几何对象。WKT通过文本来描述几何对象和空间参考，而WKB通过二进制字节形式描述空间对象。由于HDFS不直接支持矢量数据结构，矢量数据需要进行转化后才能在Hadoop中使用。Hadoop非常擅长处理非结构化文本数据，默认使用文本作为输入，因此本文采用WKT来描述矢量空间对象，利用开源GeoTools-2.7.5工具包，设计了一种便于在hadoop中分布式存储的矢量数据文件，如图1。
在矢量数据文件中，每一行表示一个空间对象。通过HDFS来存储和管理矢量数据文件，就是直接将创建的矢量数据文件上传到HDFS文件系统，然后HDFS对其进行自动分片，生成大量的数据块（缺省为64M），分别存储到不同的节点上。2.3 MapReduce矢量数据选择查询方法
由于空间查询多为计算密集型操作，为了提高查询效率，本文采用两阶段的过滤-精炼算法。第一阶段过滤,将空间对象用其最小外包矩形表示,当查询区域为矩形时，两个矩形是否相交最多只需要4次判断就能确定，过滤后得到候选集。第二阶段精炼，通过对候选集使用精确的几何条件和属性条件判断，最终获得符合查询要求的空间对象集。
在map函数中，从HDFS矢量数据文件依次读取空间对象，经过过滤阶段和精炼阶段的筛选，reduce函数将满足查询条件的空间对象集输出到HDFS文件系统。
[5]
4 结语
该文根据hadoop的分布式存储特点和矢量数据的存储模型，设计一种适合hadoop存储的矢量数据文件，通过对矢量数据MapReduce处理流程的分析，实现基于hadoop过滤-精炼算法的矢量数据的选择查询方法，通过实验，验证了本文提出方法的正确性和有效性。下一步，将研究基于MapRedue的大规模矢量空间数据连接查询处理方法。
参考文献
[1] 张书彬,韩冀中,刘志勇，等.基于
MapReduce实现空间查询的研究[J]. 高技术通讯,2010,20(7)：719-726.[2] 赵彦荣,王伟平,孟丹，等.基于Hadoop
的高效连接查询处理算法CHMJ[J].软件学报,2012（4）：124.
194
科技创新导报 Science and Technology Innovation Herald
Copyright©博看网 www.bookan.com.cn. All Rights Reserved.
因篇幅问题不能全部显示，请点此查看更多更全内容