一种支持并行处理的矢量数据存储与查询方法

陈 洁，褚龙现，夏栋梁

（1.铜川职业技术学院 人文科学系 ，陕西 铜川727031；2.平顶山学院 软件学院，河南 平顶山467000；3.武汉大学 计算机学院，湖北 武汉430072）

一种支持并行处理的矢量数据存储与查询方法

陈 洁1，褚龙现2，3，夏栋梁2

（1.铜川职业技术学院 人文科学系 ，陕西 铜川727031；2.平顶山学院 软件学院，河南 平顶山467000；3.武汉大学 计算机学院，湖北 武汉430072）

为了提高海量空间矢量数据的存储和拓扑关系查询效率，提出一种矢量数据的分布式存储与索引方法。设计了基于HBase的空间数据存储模型和索引构建方案，采用Spark计算框架实现了网格空间索引的并行构建算法，利用索引完成了空间拓扑关系的分布式查询。最后在Hadoop集群上统计了相同数据集的拓扑包含查询时间，结果表明提出的并行存储与查询方法可行性好，比直接查询HBase算法快4～5倍。

空间关系；并行；Spark；HBase；区域查询

空间对象拓扑关系是空间关系的重要组成部分和主要研究内容，主要表达了点、线和面等空间对象的关联、包含和邻接关系[1-2]，拓扑关系的判定是地理信息系统中最常见和最基础的操作[3]。空间拓扑关系查询一般指的是从矢量数据集中查找与查询对象满足特定拓扑关系的要素的过程，随着空间数据获取方法和技术的不断革新，空间数据集变得越来越大，TB、PB级大小的矢量数据的出现促使研究分布式数据存储和查询成为地理信息系统技术创新的热点[4]。

随着Apache Hadoop[5]的出现，空间数据的并行存储与分布式拓扑关系查询成为可能。目前有关拓扑关系查询研究大都集中在将海量矢量数据存储在HDFS或HBase数据库中，并构建索引实现空间查询[6-8]，这些方法重点关注了数据表行键的设计，且在MapReduce计算框架下实现[9]，对空间索引的并行构建优化和数据过滤查询研究较少。

文中主要研究矢量数据存储到HBase的数据模型和索引结构设计，实现基于Spark的空间网格索引并行构建和拓扑关系的分布式查询方法。将矢量数据中心点经纬度连接作为行键，数据信息以WKT格式存储，最后给出拓扑包含关系查询算法。

1 相关工作

1.1 HBase

HBase是Hadoop的分布式数据库[10]，采用列式存储方式来存储数据，这种方式可以排除空元素的保存，节省存储空间。从逻辑结构上看，数据库中的数据仍然包含行和列，且多个不同的列构成一个列族，数据的唯一性由行键来确定，同时根据不同时间一行数据可以有多个不同值。于是，数据表中单元格的值由4个属性唯一确定：

（行键，列族，列名，时间戳）->单元格值

1.2 Spark

Spark是一个可以运行在Hadoop上的并行软件框架，能够实现MapReduce功能的同时确保中间输出结果保存在内存中，并行处理过程不需要重复I/O操作[11]。Spark进行并行处理的根本是弹性分布式数据集（Resilient Distributed Dataset，RDD），RDD是分布式内存中只读的分区集合，有3种方式创建：现有RDD转换而来、集合转换和读取文件，且RDD可以相互依赖。

1.3 空间拓扑关系

空间拓扑关系使用关联、邻接和包含体现地理空间要素之间的关系，要素类型包括点、线和面。拓扑关联表达不同要素之间关系，拓扑邻接表达相同要素之间的关系，拓扑包含则表达不同级别或不同层次的多边形实体之间的关系[12]。文中主要研究拓扑包含关系查询的优化算法，其中包含关系如图1所示。

图1 拓扑包含关系

2 存储模型设计与索引构建

2.1 数据模型

1）行键设计

HBase数据表中每一行数据根据时间戳不同可以有多个值，但是不同行的确定是通过行键标识的。在HBase中只支持行键查询，且数据根据行键按字典升序存储[13]。为了确保行键的唯一性，在存储矢量空间数据时首先计算矢量数据空间中心点经纬度，然后使用“@”将经纬度坐标按字符串连接在一起组成行键。其中，经度取12位（符号位1位，整数3位，小数8位），纬度取11位（符号位1位，整数2位，小数8位），负值符号位为1，正值符号位为0，整数不足部分前面补0，小数不足的后面补0。如中心点坐标 为 （98.23125441，-80.54824512）， 则 行 键 ，009823125441@180548245120。

2）列族设计

矢量数据一般包括几何属性和非几何属性，在HBase数据表设计时包含两个列族Geo和Attribute分别保存几何数据和非几何数据。其中，Geo包含wkt列，Attribute根据实际非几何属性个数包含不同列。为方便拓扑关系判定，几何数据以WKT格式存储点、线和面，最终设计的数据表存储模型如表1所示。

表1 矢量数据存储模型

2.2 索引并行构建

为了提高数据查询效率，针对矢量数据构建网格索引。构建的索引表结构如表2所示。

表2 索引表存储模型

按照经纬度 （1，0.5） 划分网格， 全球共有360*360个网格，使用二维数组Cell[360][360]表示。每个网格编码使用i@j表示，其中i和j分别为数组Cell的下标。按照公式（1）可以计算出空间坐标点p（longitude，latitude）所属的网格的下标。

其中，h=1，w=0.5。

索引表使用网格编码作为行键，列rowkeys:ids的值为包含在对应网格中空间对象行键的组合，不同行键之间使用逗号分隔。应用Spark并行构建方法，构建算法的过程如图2所示。

图2 Spark并行构建索引流程

并行构建索引具体步骤：

1）newAPIHadoopRDD读取HBase中数据表，得到RDD[K，V]，其中K为自主编号，V为行数据；

2）map变换，获取数据的行键并截取字符串得到矢量数据中心点的经纬度，计算得出中心点所属网格编码，以网格编码为Key，以数据行键为Value，形成mapRDD；

3）reduceByKey变换，以网格索引为Key，以"，"拼接原Value构成新的Value，形成reduceRDD；

4）map（convert）变换，convert是向HBase表的变换函数，形成resultRDD；

5）saveAsHadoopDataset将 resultRDD写到索引表。

3 拓扑关系并行查询算法

拓扑包含关系并行查询的基本思想是：首先将输入的区域构造为空间对象，接着获取空间对象的最小外接矩形MBR，按照公式（2）得到MBR相关的网格索引编码集合，然后扫描索引表获取矢量数据的行键并进一步取出数据，最后依次判断取出wkt数据是否包含在输入区域中，若是则为结果。

其中，CodeMBR是多边形区域最小外接矩形相关的网格编码集合，MBR两个顶点为Min（minx，miny），Max（maxx，maxy），N表示自然数。

实现流程如图3所示。

图3 拓扑包含并行查询流程

4 实验与分析

实验环境的平台搭建为：云平台4个节点构成的Hadoop集群，每台机器2.6GHz CPU和4GB内存，安装CentOS6.4操作系统，Hadoop版本为2.6.0，HBase版本为 0.98.6.1，Zookeeper版本为 3.4.6，Spark版本为1.4.1。实验数据为：纽约2013年的出租车运营记录和纽约市行政区划[14]。

表3 实验数据集

应用Spark计算框架完成索引的并行构建，各个数据集花费时间分别为：D1花费180.25s，D2花费339.12s，D3花费525.54s。

拓扑包含实验查询出租车计时开始的坐标点在每个行政区出现的次数，使用文献[7]和本文两种算法对如表3所示的3个数据集进行拓扑包含查询，花费时间如图4所示。

图4 不同区域查询运行时间

实验结果表明，在HBase中借助空间网格索引和Spark并行处理框架能有效提高空间拓扑关系查询效率。根据Spark运行特点，随着集群中节点数的增加和数据量的增大，本文查询执行效率将提高更多。

5 结束语

文中分析了空间拓扑关系查询特点，提出一种基于HBase的矢量数据存储模型，设计了支持并行处理的空间网格索引构建算法，应用Spark计算框架实现了空间拓扑关系查询。实验验证了本文提出的数据存储索引和分布式拓扑查询方法的有效性，下一步将研究如何优化线、面拓扑关系的分布式判定方法。

[1]陈军，赵仁亮.GIS空间关系的基本问题与研究进展[J].测绘学报，1999，28（2）:95-102.

[2]Eliseo C，Paolino D F.Approximate topological relations[J].International Journal of Approximate reasoning.1997，16（2）:173-204.

[3]Zhan F B.Approximate AnalysisofBinaryTopological Relations Between Geographic Regions with Indeterminate Boundaries[J].Soft Computing，1998，2（2）:28-34.

[4]吴华意，刘波，李大军，等.空间对象拓扑关系研究综述[J].武汉大学学报信息科学版，2014，39（11）: 1269-1276.

[5]YANG G.The application of MapReduce in the cloud computing[C]//Proceedings of the 2011 2nd InternationalSymposium on IntelligenceInformation Processing and Trusted Computing.Piscataway:IEEE，2011:154-156.

[6]WANG L，CHEN B，LIU Y.Distributed storage and index of vector spatial data based on HBase[C]// Proceedings of the 2013 21st International Conference on Geoinformatics.Piscataway:IEEE，2013: 1-5.

[7]郑坤，付艳丽.基于HBase和GeoTools的矢量空间数据存储模型研究[J].计算机应用与软件，2015，32（3）:23-26.

[8]丁琛.基于HBase的空间数据分布式存储和并行化查询算法的研究[D].南京:南京师范大学，2012.

[9]辛大欣，屈伟.基于Hadoop的云计算算法研究[J].电子设计工程，2013，21（3）:33-35.

[10]Tom White.Hadoop:The Definitive Guide[M].2nd ed.O’ReillyMedia，Inc，2011.

[11]M.Zaharia，M.Chowdhury，M.J.Franklin，S. Shenker，and I.Stoica.Spark:Cluster Computing with Working Sets[C]//In 2nd USENIX Conference on Hot Topics in Cloud Computing（HotCloud），2010.

[12]Maribeth Price.Mastering ArcGIS[M].McGraw-Hill Education，2015.

[13]Zheng kun，Yanli Fu.Research on Vector Spatial Data Storage Schema Based on Hadoop Platform[J]. InternationalJournalofDatabase Theory and Application，2013，6（5）:85-94.

[14]NYC Taxi Trips[EB/OL].http://www.andresmh.com/ 2013.

A vector data storage and query method supporting parallel compute

CHEN Jie1，CHU Long-xian2，3，XIA Dong-liang2
（1.Department of Humanities，Tongchuan Vocational and Technical College，Tongchuan 727031，China；2.Software School，Pingdingshan University，Pingdingshan 467000，China；3.Computer School，Wuhan University，Wuhan 430072，China）

To improve the storage efficiency of massive spatial vector data and query efficiency of topotaxy relation，a distributed storage and index method of vector data is proposed.A spatial data storage modal and index build method is designed based on HBase.The parallel build algorithm of grid spatial index is realized by using Spark compute framework，and the distributed query of spatial topotaxy relation is then achieved by using the index.The query time consumption of topologically containing based on same data sets on Hadoop cluster is counted，statistic data shows that the proposed method on parallel storage and query is feasible and 4～5 times faster than directly query method of HBase.

spatial relation；parallel；spark；HBase；regional query

TN91

A

1674－6236（2017）10-0031-03

2016-04-13稿件编号：201604131

河南省教育厅科学技术研究重点项目（12B520040）；平顶山学院青年基金项目（PXYQNJJ2016013）

陈 洁（1979—），女，江苏溧水人，硕士，讲师。研究方向：大数据，旅游与城市发展。