基于MapRedue的大规模矢量空间数据选择查询处理

摘 要：为高效地处理大规模矢量空间数据，基于Hadoop的并行计算框架mapredue，实现了一种分布式的矢量空间数据选择查询处理方法。首先，分析OGC简单要素标准与Hadoop的Key/Value数据模型，设计了可存储于Hadoop HDFS的矢量文件格式；其次，根据两阶段的过滤-精炼策略，对Map 输入数据分片、选择查询处理过程及Reduce结果合并等关键步骤进行了详细阐述；最后，基于上述技术，利用Hadoop集群环境对所提出的方法进行验证，该方法具有较好的可行性和较高的效率。

关键词：MapRedue 选择查询 存储模型 Key/Value 矢量数据文件

中图分类号： 文献标识码：A 文章编号：1674-098X（2014）03（c）-0193-02

随着全球空间数据集的急剧增长，海量空间数据带来了丰富的信息，而面对如此庞大和复杂的数据集，随之产生了数据存储与管理问题。国内外很多学者尝试利用Hadoop云计算技术处理矢量空间数据。张书彬等利用MapReduce并行处理空间查询的数据分割方法、副本避免方法实现空间查询[1]；赵彦荣等基于Hadoop提出了一种并行连接查询算法CHMJ[2]，提高了连接查询的处理效率；尹芳等基于开源Hadoop 的矢量空间数据分布式处理研究[3]；王永刚对Hadoop云计算平台下地理信息服务的若干关键技术进行了研究[4]。

基于上述研究，该文以Hadoop分布式文件系统存储矢量空间数据，根据空间查询处理的两阶段过滤与精炼策略，并充分利用MapRedue并行计算框架处理海量数据的优势，设计一种简单实用的选择查询方法，有效提高了对大规模矢量空间数据的查询处理效率。

1 基本概念

1.1 空间选择查询

在GIS中，常见的对空间矢量数据的查询有三种，即：空间选择查询、空间连接查询和最近邻查询。其中，空间选择查询和连接查询是最基本的查询操作。空间选择查询是最重要的一种空间查询操作，它能够作为其他空间查询操作（如空间连接查询和最近邻查询）的基础。代表性的空间选择查询包括空间点查询和空间区域查询。点查询（Point Query）通过给定一个查询点P和一个空间对象集M，查找出M中所有包含点P的空间对象。区域查询通过给定一个多边形区域R和一个空间对象集M，查找出M中所有与R相交或被R包含的空间对象。

1.2 MapReduce并行计算框架

Hadoop是一款开源分布式系统基础架构，它支持在商用硬件构建的大型集群上运行应用程序，实现对海量数据的分布式处理。其核心技术包括并行计算框架MapReduce和分布式文件系统HDFS，分别是Google MapReduce和GFS的开源实现。MapReduce是一种并行计算的编程模型，用于大规模数据集（大于1TB）的并行运算。

2 基于MapReduce的空间选择查询

2.1 矢量数据存储模型

目前，开放地理信息联盟OGC（Open Geospatial Consortium）制定了许多与空间信息、基于位置服务相关的标准，其中简单要素模型（图1）是OGC最为重要的几何对象模型。简单要素几何对象中主要定义了点、线、面和集合对象。通过将空间对象与空间参考系进行关联，空间对象被抽象表达为空间参考系统（Spatial Reference System）所描述的几何体（Geometry）。大多数空间关系及空间分析都基于这个类层次体系进行研究，并且平台是独立的，可以应用到分布式计算系统[5]。该文中同样采用简单要素模型来存储矢量数据。

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文件系统。

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%。

4 结语

该文根据hadoop的分布式存储特点和矢量数据的存储模型，设计一种适合hadoop存储的矢量数据文件，通过对矢量数据MapReduce处理流程的分析，实现基于hadoop过滤-精炼算法的矢量数据的选择查询方法，通过实验，验证了本文提出方法的正确性和有效性。下一步，将研究基于MapRedue的大规模矢量空间数据连接查询处理方法。

参考文献

[1] 张书彬，韩冀中，刘志勇，等.基于MapReduce实现空间查询的研究[J]. 高技术通讯，2010，20（7）：719-726.

[2] 赵彦荣，王伟平，孟丹，等.基于Hadoop的高效连接查询处理算法CHMJ[J].软件学报，2012（4）：124.

[3] 尹芳，冯敏，诸云强，等，基于开源Hadoop 的矢量空间数据分布式处理研究[J].计算机工程与应用，2013（16）.

[4] 王永刚.基于Hadoop云计算平台的地理信息服务若干关键技术研究[D].北京：中国科学院研究生院遥感应用研究，2011.

[5] 范建永，龙明，熊伟.基于HBase的矢量空间数据分布式存储研究[J].地理与地理信息，2012，28（5）：39-42.