EN中文

Journal of Geo-information Science >

2020 , Vol. 22 >Issue 7: 1487 - 1496

DOI: https://doi.org/10.12082/dqxxkx.2020.190255

Parallel Construction and Distributed Storage for Vector Tile

  • NIE Pei , 1, 2 ,
  • CHEN Guangsheng , 1, 2, * ,
  • JING Weipeng 1, 2
Expand
  • 1. College of Information and Computer Engineering, Northeast Forestry University, Harbin 150040, China;
  • 2. Heilongjiang Province Engineering Technology Research Center for Forestry Ecological Big Data Storage and High Performance(Cloud) Computing,Harbin 150040, China
CHEN Guangsheng, E-mail:

Received date: 2019-05-23

  Request revised date: 2019-11-12

  Online published: 2020-09-25

Supported by

National Natural Science Foundation of China(31770768)

The Natural Science Foundation of Heilongjiang Province of China(F2017001)

Heilongjiang Province Applied Technology Research and Development Program Major Project(GA18B301)

Copyright

Copyright reserved © 2020
Fold

Abstract

With the deepening of the information technology, Internet maps containing multi-source geospatial information are widely used in many fields such as forestry, ocean, land, transportation, and military. At the same time, due to the advancement of Earth observation, surveying, and mapping technology, spatial data with high precision and wide coverage has grown rapidly, leading to an era of geospatial big data. Under this background, how to quickly and efficiently construct Internet map services becomes the current research priorities and challenges. Grid tiles has been used to construct Internet maps at the beginning, and played an important role in the fast-growing popularity of Internet maps. However, with the mobilization of maps and the gradual deepening of applications, the disadvantages of large size and low efficiency of applying grid tiles are becoming more and more obvious, which is difficult to meet the needs of applications. Vector tiles have many advantages over traditional grid tiles, such as small in size, high in generation efficiency, and support dynamic interaction, are becoming the focus of next generation Internet map service research. In order to further accelerate the processing speed and enhance the scalability in current vector tile application, this study uses big data technology for vector tile processing. Firstly, we uses the parallel computing framework-Spark, to build the vector tile pyramid model. Specifically, through customizing the Spark conversion function, the steps of tile generation are parallelized, and the original vector data GeoJson is converted into a vector tile set-MapBox Vector Tile (Mvt). Then we designs a tile storage model-VectorTile Store, to store the generated Mvt based on the distributed memory filesystem-Alluxio. The VectorTile Store model stores data with key-value pairs, with the tile metadata occupying the first eight key-value pairs, and each single tile occupying a key-value pair. When the data is being written, a hash index is built based on the key for fast access. This model efficiently stores massive tiles and is highly scalable. The experimental results show that the vector tile parallel construction algorithm and distributed storage model proposed in this paper are more efficient than traditional schemes, and are more suitable for massive vector tile data processing.

Key words： vector tile; web map service; parallel processing; spark; distributed storage; alluxio

Cite this article

NIE Pei , CHEN Guangsheng , JING Weipeng . Parallel Construction and Distributed Storage for Vector Tile[J]. Journal of Geo-information Science, 2020 , 22(7) : 1487 -1496 . DOI: 10.12082/dqxxkx.2020.190255

1 引言

内含多源地理空间信息的互联网地图在诸多领域如林业、海洋、国土、交通、军事等领域被广泛运用,与此同时,高精度、覆盖面大的空间数据爆炸式增长,地理空间大数据时代已经来临[1]。在此背景下,如何快速高效地构建互联网地图服务是当前的研究重点与难点[2]。
栅格数据及矢量数据是地理空间应用的两种重要的基础数据类型,与栅格数据相比,矢量数据存储空间小,使用灵活,制图发布后仍支持查询更改操作,并且可以动态更改样式。在许多地图服务提供产商中,如谷歌地图、百度地图,采取了很多的方式方法来提升在线地图的访问效率,其中瓦片技术是最为有效的方法[3]。瓦片是指在网络地图服务中进行地图浏览、查询、编辑、分析等操作时,对出现的地图数据按照特定的方式进行预先切图和存储,以便在以后访问同样的地图数据时不需要服务器重新生成,从而提高数据的访问效率[4]。
矢量瓦片是将地图中的矢量图层以瓦片的形式进行切分和存储,与栅格瓦片相比,矢量瓦片体积小、生成效率高、可动态交互、支持在线编辑与样式的修改,这都是传统栅格瓦片所不具备的特性[5]。随着地理空间数据的增长,单机存储、处理速度与互联网快速响应需求间的矛盾愈加凸显,将分布式存储、并行计算等一系列大数据技术应用到空间数据处理成为大势所趋,在当前研究中,大多数研究人员仅对栅格瓦片的并行构建和分布式存储进行研究,刘义等[6]利用MapReduce进行批量栅格瓦片金字塔并行构建,提升了瓦片构建速度。赫高进等[7]提出使用MPI的金字塔并行构建算法,对构建遥感影像金字塔过程中的重采样与I/O过程进行并行处理,大大缩短了遥感影像金字塔构建时间。Zhang等[8]、陈桦等[9]基于分布式文件系统HDFS及分布式数据库Hbase进行海量栅格瓦片的存储,保证了大量并发用户访问的性能,提高了客户端浏览地图的速度。在矢量瓦片研究方面,陈举平等[10]介绍矢量瓦片地图技术实现原理、数据标准,对矢量瓦片的数据组织模型、数据编码规则和地图渲染引擎的关键技术进行阐述。张立强等[11]对矢量地图可视化进行研究,提出了基于多核CPU及GPU的矢量地图快速可视化的方法,在一定程度提升上了矢量瓦片的显示速度,但这种方法是利用专用硬件上进行加速,扩展性不强。金澄等[12]对矢量数据抽稀进行研究,提出一种改进的Visvalingam算法,解决了最小权重值查找效率低下及线化简前后拓扑一致性保持等问题,为矢量数据简化提供了新方案。朱笑笑等[13]提出一种顾及要素空间分布特征的稠疏矢量瓦片构建方法,使得同一层级矢量瓦片间的数据量相对均衡,提升了矢量瓦片的加载渲染效率,获得了较好的用户体验,但该研究仅从数据分布角度进行研究,当瓦片数量很大时,构建速度和存储组织将成为挑战。
从上述可见,和栅格瓦片相比,当前对于矢量瓦片的研究大多还处在单机小数据量阶段,对于矢量瓦片的快速构建及分布式存储研究较少,而矢量瓦片较栅格瓦片有诸多优势,在未来的应用及研究中,如何快速高效地组织海量矢量瓦片必将是互联网地图服务及GIS技术研究的重中之重。由此,本文旨在加快矢量数据的处理速度,提供更快的瓦片访问接口,对矢量瓦片的并行构建及分布式存储进行研究,利用Spark并行处理框架对原始矢量数据进行处理,快速构建矢量瓦片mvt;对于产生的海量矢量瓦片,提出一种基于内存分布式文件系统的存储模型-VectorTileStore,通过自定义元数据及瓦片的存储顺序,高效地组织矢量数据,为互联网地图服务提供快速的数据访问接口。

2 矢量瓦片解析

2.1 瓦片金字塔模型

瓦片是将特定空间范围内的地图数据在某一分辨率或者比例尺下进行切分,形成若干行列的数据块,这个数据块就是瓦片。而瓦片数据模型要满足用户对于不同区域不同分辨率比例尺的数据访问,所以瓦片模型通常是一个金字塔层次模型,从最顶层（0层）到最底层（N层）,分辨率递增,比例尺递增。瓦片模型相邻层级之间的比例尺和分辨率关系为1:2（2:1）,瓦片数量为1:4（4:1）,瓦片大小在不同层次保持一致,这里指的大小是瓦片在屏幕上的分辨率,即瓦片的长×宽,而随着层次的递增,瓦片的比例尺递增,单个瓦片表示的空间范围递减,相邻层级的瓦片空间范围关系为4:1（1:4）。
以0-2级为例,如图1所示,第0级只包含一张瓦片,第1级包含4块瓦片,第2级包含16块,瓦片编号为（层级,行,列）。由此可得到第N层级瓦片数量Tiles-N如式（1）所示,其中N代表层级号。
Ti l e s - N = 4 N
图1 第0级到第2级瓦片

Fig. 1 Diagram of tiles from level 0 to level 2

当层数越来越多,整个矢量瓦片就形成了一个层次金字塔式的模型,从第0层到第N层,单层表示的地理空间范围不变,但是瓦片数量逐级递增,所以分辨率递增,若第0级分辨率为R,则第N级分辨率RN如式(2)所示。
R N = 2 N R

2.2 GeoJson矢量数据

矢量瓦片是在特定数据块上所有矢量数据的集合,因此在介绍矢量瓦片之前,需要对矢量数据的组织结构进行了解,常见的矢量数据组织存储形式有Shapefile、GeoJson、TopoJson等,其中GeoJson基于JavaScript语法格式的地理空间数据交换格式,具有很强的通用性,被多数软件平台和GIS厂商支持,近年来成为矢量数据组织格式的首选[14]。
GeoJson对象可以表示几何图形的位置信息及其属性值。GeoJson支持下面几何类型：点、线、面、多点、多线、多面和几何集合,一个完整的GeoJson数据结构是一个Json对象,在GeoJson里,对象由键值对集合组成。对每个键值对来说,键总是字符串,值要么是字符串、数字、对象、数组,要么是文本常量“True”、“False”和“Null”中的一个。在GeoJson中,特定的键值对表示特定的信息,其中对于空间数据起支撑作用的有以下5个字段：
Geometry: 该字段对几何矢量进行描述,其中包含矢量数据的类型和坐标信息;
Coordinates: 描述矢量数据的位置信息,以二维或三维坐标点或数组来标识;
Properties: 描述矢量数据的属性信息,以一个Json对象标识;
CRS：矢量数据的坐标参考系统,位于层级结构最顶层,默认参考系为地理坐标参考系WGS84
Bbox：表征几何对象的坐标范围,为一个2*n数组,n为几何对象的维数;
图2为一个矢量面的GeoJson结构,其中没有定义CRS,使用默认的WGS84（epsg：4326）。
图2 矢量面GeoJson结构

Fig. 2 GeoJson structure of polygon

2.3 Mvt瓦片格式

矢量瓦片表示投影在正方形区块的矢量数据,是对原始矢量数据切分后的块内表示。对于矢量瓦片的组织,尚无统一标准,而MapBox公司制定的瓦片数据标准格式mvt（MapBox Vector Tile）是目前较为通用的矢量瓦片数据组织文件格式[15],许多GIS桌面平台都支持mvt格式的矢量瓦片。mvt采用Google Protocol Buffer（pbf）进行编码,默认投影坐标系为Web Mercator（epsg:3857）,mvt文件中不包含投影和空间范围信息,其假定解码方已知投影信息及编号方式,通过编号规则和图层范围即可获取单块瓦片的空间范围。与GeoJson类似,mvt中也有相应的字段来描述瓦片内的几何矢量数据。
（1）Layers：图层,矢量瓦片由一系列图层组成,每个图层必须包含一个Features几何对象,Features的属性值也以键值对形式（keys,values）存储到图层这一级下。图层必须包含一个extent字段,用来记录瓦片的长和宽,而在mvt中,几何对象的坐标被转化成以瓦片左上角为原点,瓦片宽为x轴,瓦片长为y轴的坐标系下的坐标点,也就是说几何对象的坐标记录是其在瓦片内的相对位置,而不是真实的空间地理位置。
（2）Features： 用来描述几何对象的字段,内部必须包含geometry字段和type字段。geometry字段用来记录几何对象的块内坐标,type字段来标识该几何对象的类型,如点、线、面等。Features内部有两个可选字段：tags和id,tags字段用于索引Layers层次下的键值对,表示该几何对象的属性,值得注意的是,tags字段总是成对出现,表示在keys和values的索引;id为几何对象的标识符,相对于其他几何对象该字段是唯一的。
图3为一个图层中只包含一个矢量点的mvt瓦片结构,其中图层名为“points”,图层内仅包含一个几何对象,几何对象的坐标、类型及属性索引值存储在Features字段中,瓦片的长宽由extent标识,几何对象的属性值由keys及values存储。可见mvt中不包含图层空间范围、坐标参考系、瓦片编号等元数据,这些元数据将在第4节进行介绍。
图3 mvt瓦片结构

Fig. 3 Structure of mvt

3 并行构建矢量瓦片

这节将基于并行处理框架Spark,对原始矢量数据GeoJson快速构建矢量瓦片集mvt,生成矢量瓦片金字塔模型。

3.1 Spark并行计算框架

Spark是由伯克利大学AMPlab于2009年提交的一个项目,现已是Apache软件基金会下最活跃的开源项目之一[16]。简单来说,Spark是用于大规模数据处理的统一分析引擎,通常运行在集群之上,提供强大的并行计算能力。Spark属于广为人知的Hadoop生态圈,可以对Hadoop下的数据源进行读取处理,Spark将中间结果保存在内存中,不需要进行磁盘I/O,因此在进行多次数据计算迭代时,Spark具有更好的性能,由此Spark也被称为继MapReduce后的下一代计算分析引擎。
弹性分布式数据集RDD（Resilient Distributed Dataset）是Spark的理论基石,是对分布式内存的抽象使用,它表示已被分区、只读的、并提供一组丰富的操作方式来操作这些数据集合,操作类型主要分为3种：① 输入操作,通过该操作构建分布式内存中的RDD,比如读取输入txt文件;② 转化操作,转化操作是对数据进行处理的过程,将一个RDD通过自定义的方法转化为另一个RDD,最典型的转化操作是RDD的map映射操作;③ 行动操作,只有调用行动操作时才会触发Spark作业的提交并返回相应的结果,之前的操作都被绘制成一幅有向无环图,计算的时候按图索骥,得到最优的运算路径。

3.2 并行构建流程

由2.1节可知,原始数据GeoJson描述的是一个图层上的全局范围内的矢量数据,内部包含空间范围,坐标系等元数据信息;而mvt表示的为某一区块上的数据,记录几何对象的相对位置,不包含元数据,这两种矢量数据结构的默认参考坐标系也不同。因此,从原始矢量数据转到矢量瓦片,需要进行诸如坐标系转化、数据切分、网格块计算、数据抽稀等等一系列复杂的过程,单机下生成大数据量的瓦片集将相当耗时,因此运用高性能计算技术进行瓦片数据处理是很有必要的,本文采取的生成矢量瓦片的算法步骤如下：
（1）根据矢量瓦片生成的层级数N和图层数据的空间范围[Xmin, Ymin, Xmax, Ymax]（也就是GeoJson最外层的Bbox）,进行数据划分和空间范围的计算,对于第N层i行j列的瓦片,空间范围Bbox-of-Tile(N, i, j)计算如下：
Bbox - of - Tile N , i , j = ( X max - X min ) × ( i - 1 ) 4 N , ( Y max - Y min ) × ( j - 1 ) 4 N , ( X max - X min ) × i 4 N , ( Y max - Y min ) × j 4 N ( i , j = 1,2 , 3 , … )
（2）对GeoJson进行预处理,将一个Feature（几何对象）组织成一行,键值对用制表符分隔,这一步的目的是为了便于Spark并行读取。
（3）将GeoJson的几何对象坐标（X, Y）（默认WGS84）转换到mvt默认的坐标系Web Mercator
Transform [ X , Y WGS 84 → X , Y Web - Mercator ]
（4）对于单个几何对象（也就是一行数据）,根据步骤（1）计算出来的瓦片空间范围,判断几何对象在各层级的瓦片块归属,若几何对象跨越多块瓦片,则将其切分为多个几何子对象,划归到不同的瓦片块,确定了几何对象所属的瓦片块,以瓦片块编号（层级,行号,列号）为键标识几何对象。需要注意的是,在对几何对象进行切分时,仅仅是对其位置坐标信息进行切分,其子对象的描述信息如type、bbox、properties保持一致。
（5）将几何对象的坐标（经过步骤（3）的转化,现在的坐标系为web Mercator）转换到块内坐标,若几何对象所属的瓦片Bbox为[x1, y1, x2, y2],瓦片的长宽为extent,坐标点（x,y）转换成块内坐标（xtile, ytile）如式（5）所示。
xtile = x × extent x 2 - x 1           ytile = y × extent y 2 - y 1
（6）同键几何对象归并,同键意味着位于同一层级下同一瓦片,将同一瓦片块内的所有几何对象合并就组成了瓦片数据;然而当瓦片层级很小时,如图2的第0层,该层只有一块瓦片,所有空间对象存储在单张瓦片上,在维持相同瓦片分辨率的前提下将会造成大量数据冗余,同时影响数据的空间表达效果,因此,当瓦片层级小于某一级别时,在归并的同时需要进行矢量数据抽稀,简化几何对象,提升瓦片访问效率,本文采取的抽稀算法为Douglas-Peucker算法[17]。
（7）经历归并抽稀操作后,单块瓦片中的几何对象组成单条记录,调用Spark行动操作,写入mvt文件。
依据上述的算法步骤,利用Spark进行矢量瓦片的并行构建,Spark并行构建算法流程算法1所示,在并行处理之前,需要将原始矢量数据GeoJson预处理转化成文本文件txt,方便后续处理;在Spark进行并行构建瓦片的过程中,主要调用了Map、MapToPair、MapValues、ReuceBykey这4个转换操作,通过自定义转换处理函数,完成瓦片构建任务的各个步骤,其中后2种转换操作仅针对键值对RDD;最后调用foreach行动操作,自定义输出函数将生成的瓦片保存到磁盘中。

4 矢量瓦片分布式存储

由矢量瓦片的结构和构建过程可见,原始矢量数据生成矢量瓦片,文件数量成百上千倍增加,随着空间数据量和数据处理任务的飞速增长,无疑将给单机存储带来巨大压力。当前对于矢量瓦片的分布式存储研究较少,大多采用传统的关系型数据库进行瓦片数据存储,如对于矢量瓦片集及其元数据的组织,Mapbox为其制定了关系型数据库SQLite下的存储格式MBTiles[18],但随着瓦片数量的增长,这种轻量级的关系型数据库存储方式必将受到挑战。由此,本文基于内存分布式文件系统Alluxio设计一个面向矢量瓦片的存储模型-VectorTileStore,将图层区域上所有的矢量瓦片存储在一个键值对结构中,兼容瓦片生成过程中产生的元数据,将其合并到存储模型中,为后续的矢量数据处理奠定基础。

4.1 内存分布式文件系统Alluxio

Alluxio是由UC Berkeley AMPLab实验室于2013年开源的一个新项目,作为世界上首款以内存为中心的虚拟分布式存储系统,它能够统一数据访问并成为连接计算框架和底层存储系统的桥梁,应用程序只需要连接Alluxio便能够访问底层任意存储系统中的数据,除此之外,Alluxio以内存为中心的架构使得数据访问比现有的解决方案能快若干个数量级。本质上, Alluxio是个分布式的内存文件系统,部署在计算平台如Spark、Mapreduce之下以及存储平台如HDFS、 S3之上,通过全局地隔离计算平台与存储平台,它在减轻计算框架内存压力的同时,也赋予了计算框架内存快速大量数据读写的能力。Alluxio把内存存储的功能从Spark/MapReduce中分离出来,使Spark/MapReduce可以更专注计算的本身,以求通过更细的分工达到更高的执行效率[19]。

4.2 分布式存储模型-VectorTileStore

在第3节并行构建瓦片生成的mvt瓦片文件里,并不包含图层和瓦片的元数据,而这些元数据对于瓦片生成和后续的矢量数据调用及处理不可或缺,因此在进行数据存储时,除了生成的mvt瓦片,也需要考虑元数据。本文考虑的矢量瓦片元数据主要有以下8个字段：
Format： 矢量瓦片格式,mvt瓦片的编码方式是pbf;
Bounds：矢量瓦片数据集的范围,标识整个矢量图层的空间范围,所有层级的瓦片都在该范围内,和GeoJson中的Bbox结构一致;
Center：矢量图层的中心点及默认显示层级;
Minzoom：矢量瓦片金字塔层级的最小级别,定义为0;
Maxzoom：矢量瓦片金字塔层级的最大级别,依据需求进行定义,该值也就是上文所说的层级数N;
Description：描述字段,用于描述瓦片集的来源或风格;
Version：矢量瓦片的版本;
Attributes：矢量图层的属性字段,定义为一个Json,该字段描述瓦片集中各个图层的属性信息,包括图层ID、图层显示的最大和最小层级（单一图层的最大层级和最小层级和瓦片集的最大最小层级关系为（layer.minzoom>=Minzoom;layer.maxzoom<=Maxzoom））、图层中几何对象的属性字段及其类型。
这些元数据要么是在原始数据中包含的,要么是在瓦片构建过程中产生的。
本文基于Alluxio分布式文件系统下的键值对文件KeyValueStore[20]进行矢量瓦片的存储,设计一个面向矢量瓦片的分布式存储模型-VectorTileStore。Alluxio下有一个原生的键值对文件KeyValueStore,其包含两个键值对结构,一个用于存储数据,另一个作为索引,提供快速查询数据接口,其索引是一个哈希表,哈希表中单个bucket与数据文件中的单个键值对一一对应,记录键的哈希值及对应键值对在数据文件的offset;基于此索引结构,只需给定键,通过哈希算法就能在内存中快速找到数据。Alluxio架构及内置的KeyValueStore结构如图4,Alluxio采用了标准的Master-Worker模式,运行中的Alluxio系统由一个Master和多个Worker构成,Alluxio Master用于管理全部文件的元数据信息,负责监控各个Alluxio Worker的状态,支持ZooKeeper进行容错,以Standby Master作为备份节点;Alluxio Worker为数据节点,管理本地的Ramdisk,是真正进行文件数据存储的节点,文件数据以数据块的形式存储在各节点Ramdisk上;在Alluxio中,KeyValueStore被切分成多个数据块,分布在各个数据节点上进行存储,如图4中, KeyValueStore存储在3个Worker节点上。
图4 Alluxio架构及KeyValueStore结构

Fig. 4 Achitecture of alluxio and structure of key value store

基于KeyValueStore,本文通过指定特定数据的存储位置,将瓦片数据集存储在键值对中,设计的存储模型VectorTileStore如图5所示,前8个键值对用于存储矢量瓦片元数据,对应上文列举的8个元数据字段,对于任何数据源和各种层级的瓦片数据集,都拥有这部分数据,可以理解为文件头或者保留字段;从第9个键值对开始,存放生成的矢量瓦片mvt,一块瓦片占据一个键值对。模型键为Int类型,从1开始递增,值为Text（String）类型存放瓦片数据或元数据字符串,其中前八个键值对固定存放元数据,其键从1递增到8,则瓦片编号（层号n,行号i,列号j）与键key的对应关系如（6）式,存储的次序按瓦片层号、行号、列号由小到大排列,即优先存储层级小的瓦片,而对同层级的瓦片来说,按行遍历进行存储。
key   =   9   n = 0 key   =   ( i - 1 ) × 2 n + j + ( 4 0 + 4 1 + … + 4 n - 1 ) + 8    n ≥ 1
图5 瓦片分布式存储模型

Fig. 5 Distributed storage model for tiles

5 实验结果与分析

5.1 实验环境与实验数据

本文使用5台浪潮英信I8000刀片服务器,其中一台作为主节点,其余4台作为计算节点,节点主机配置为Xeon E5-2620 v2 6核2.10GHz处理器,32GB内存,200 GB 硬盘,采用Tenda TEG1024G千兆以太网交换机连接,各节点安装的是RedHat6.2,Linux内核版本为2.6.32,运行Spark-1.5.0、Hadoop-2.5.2及Alluxio-1.6.0,运行模式为Standalone模式,配置应用程序允许使用的核数（SPARK_WORKER_CORES）为节点所有核数,配置应用程序允许使用的内存（SPARK_WORKER_MEMORY）为8G,坐标系转换库使用proj4-5.0.0;为了进行单机瓦片构建及存储对比实验,本文在主节点上安装了SQLite-3.28.0,单机瓦片构建工具选取Mapbox的tippecanoe[21]。
实验数据选取开源平台OpenStreetMap下的塞浦路斯、塞尔维亚、希腊、比利时、奥地利、荷兰6个欧洲国家数据[22],实验数据集包含水系、铁路、道路路网、建筑物、土地利用等多个图层,各国数据的图层数、数据条目数（几何对象数量）及文件大小如表2所示。

5.2 矢量瓦片构建对比实验

该实验对比单节点串行瓦片构建实验,基于第3节提出的算法进行矢量瓦片的并行构建,实验数据集为欧洲6个国家的数据,构建的瓦片金字塔从第0层至第9层共10层数据,考虑到数据传输效率及几何保真,当瓦片层级小于5时,即从第4层开始数据抽稀,对矢量点线面进行简化。各国数据集下的瓦片数量及数据量如表3所示,记录了各国数据集2种算法运行时间（图6）,其中塞浦路斯记为Cypr,塞尔维亚记为Serb,希腊记为Gree,比利时记为Belg,奥地利记为Aust,荷兰记为Neth。
图6 瓦片构建时间对比

Fig. 6 Comparison chart for tile construction time

从图6的实验结果可见,本文提出的矢量瓦片并行构建算法在各个实验数据集下,较单机串行构建算法运行时间更少,算法效率更高,特别随着实验数据量增大,二者时间效率差距越拉越大,这是由于Spark在完成任务初始化后,将数据分配给各个工作节点进行处理,各个节点分而治之,并发地完成任务,而单机构建始终处于“大包大揽”状态,单节点完成数据读取、处理、写磁盘等一系列操作。

5.3 矢量瓦片存储对比实验

5.3.1 写入对比实验
该实验以SQLite下的瓦片存储格式MBTiles为对比实验,基于第4节提出的分布式瓦片存储模型VectorTileStore进行瓦片集的存储,实验数据集为5.2小节构建的矢量瓦片集。将欧洲六国的瓦片集分别进行存储,记录两种数据存储格式的写入时间,如图7,从实验结果可见,当瓦片集数据量较少时（如Cypr和Serb）,MBTiles存储格式写入时间更少,当瓦片集数据量增长到一定数量,VectorTileStore写入效率更高,消耗时间更少,较单机数据库存储有明显的性能优势;这是因为当数据量较少时,Alluxio主从节点通信及任务初始化操作消耗的时间占比更大,而SQLite是一个轻量级关系型数据库,占用资源很少,处理速度快,所以此时MBTiles的写入性能更好,当数据达到一定量级后,频繁进行数据写入,此时内存存储模型的优势就体现出来,较数据库的磁盘写入更快,消耗时间更少。 VectorTileStore是分布式存储结构,数据存储在多个节点上,当单机容量到达上限,该模型能更好地适配海量瓦片数据存储。
图7 瓦片写入时间对比

Fig. 7 Comparison chart for tile writing time

5.3.2 读取对比实验
该实验基于5.3.1节的瓦片数据存储,对MBTiles和VectorTileStore进行数据读取,进行2组实验,第1组为单块瓦片读取实验,记录各国数据集下瓦片读取时间,结果如图8;第2组为并发读取实验,客户端同时读取10块瓦片,记录读取时间（图9）。从实验结果可见,VectorTileStore读取速度更快,消耗时间更少,特别在多任务并发读取时,VectorTileStore的优势更加明显,这是因为VectorTileStore将数据分布式存储在集群各个节点内存中,根据瓦片编号进行按序存储,构建高效索引,当并发读取数据时,MBTiles在单个节点启动多个线程进行处理,而VectorTileStore将数据存储在分布式集群中,各个节点分别启动读取任务,节点间资源独立,所以较单机读取速度更快。
图8 单块瓦片读取时间对比

Fig. 8 Comparison chart for single tile reading time

图9 瓦片并发读取时间对比

Fig. 9 Comparison chart for tile concurrent reading time

通过上述实验结果及分析可见,本文提出的矢量瓦片并行构建算法及分布式存储模型VectorTileStore较传统方案时间效率更高,更适合海量矢量瓦片数据处理。

6 结论与讨论

在互联网地图服务领域,矢量瓦片较栅格瓦片有诸多优势,必将是下一代互联网地图研究的重点,本文针对矢量瓦片快速构建及分布式存储进行研究,得到以下结论：
（1）本文基于Spark的并行矢量瓦片构建算法较tippecanoe单机瓦片构建速度明显提升,通过对比实验表明,并行构建算法运行时间平均减少49.6%。
（2）对于生成的矢量瓦片集,本文提出的矢量瓦片存储模型VectorTileStore兼容瓦片元数据,较MBTiles瓦片存储格式更适配海量矢量瓦片数据存取,时间效率更高。
（3）基于高性能计算技术开展矢量瓦片相关研究是可行且有一定优势的。
下一步的研究工作是基于当前研究,利用上层计算框架Spark/MapReduce与存储模型交互,进行矢量数据的并行分析处理如可视化、矢量查询等。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
张晓祥. 大数据时代的空间分析[J]. 武汉大学学报·信息科学版, 2014,39(6):655-659.

[ Zhang X X, Liu S. Spatial analysis in the era of big data[J]. Geomatics and Information Science of Wuhan University, 2014,39(6):655-659. ]

[2]
周侗, 龙毅. 我国近期移动地图与互联网地图发展综述[J]. 地理与地理信息科学, 2012,28(5):1-5.

[ Zhou T, Long Y. Review about recently development of mobile map and Internet map in china[J]. Geography and Geo-Information Science, 2012,28(5):1-5. ]

[3]
Wei X, Lu X, Sun H. Fast view of mass remote sensing images based-on image pyramid[C]// International Conference on Intelligent Networks & Intelligent Systems. IEEE, 2008.

[4]
聂沛, 陈广胜, 景维鹏. 一种面向遥感影像的分布式存储方法[J]. 测绘工程, 2018,27(11):43-48.

[ Nie P, Chen G S, Jing W P. A distributed storage method for remote sensing images[J]. Engineering of Surveying and Mapping, 2018,27(11):43-48. ]

[5]
朱秀丽, 周治武, 李静. 网络矢量地图瓦片技术研究[J]. 测绘通报, 2016(11):106-109.

[ Zhu X L, Zhou Z W, Li J. Research for web map vector tiles technology[J]. Bulletin of Surveying and Mapping, 2016(11):106-109. ]

[6]
刘义, 陈荦, 景宁, 等. 利用MapReduce进行批量遥感影像瓦片金字塔构建[J]. 武汉大学学报·信息科学版, 2013,38(3):278-282.

[ Liu Y, Chen L, Jing N, et al. Parallel batch-building remote sensing image tile pyramid with MapReduce[J]. Geomatics and Information Science of Wuhan University, 2013,38(3):278-282. ]

[7]
赫高进, 吴秋云, 陈荦, 等. 基于MPI的大规模遥感影像金字塔并行构建方法[J]. 地球信息科学学报, 2015,17(5):515-522.

DOI

[ Hao G J, Wu Q Y, Chen L, et al. An MPI-based parallel pyramid building algorithm for large-scale RS image[J]. Journal of Geo-information Science, 2015,17(5):515-522. ]

[8]
Zhang G, Xie C, Shi L, et al. A tile-based scalable raster data management system based on HDFS[C]// Geoinformatics (GEOINFORMATICS), 2012 20th International Conference on. IEEE, 2012.

[9]
陈桦, 李艳明, 朱美正. 一种支持大量并发用户的瓦片缓存方案研究[J]. 计算机工程与科学, 2012,34(12):144-149.

[ Chen H, Li Y M, Zhu M Z. Research on tile buffer policy supporting large number of concurrent[J]. Computer Engineering & Science, 2012,34(12):144-149. ]

[10]
陈举平, 丁建勋. 矢量瓦片地图关键技术研究[J]. 地理空间信息, 2017(8):44-47.

[ Chen J P, Ding J X. Research on key technologies of vector tiles map[J]. Geospatial Information, 2017(8):44-47. ]

[11]
张立强, 徐翔, 谭继强. 基于并行技术的大规模矢量地图可视化方法[J]. 地理与地理信息科学, 2013,29(4):13-16.

[ Zhang L Q, Xu X, Tang J Q. Visualization of large-scale parallel vector maps based on parallel implementation[J]. Geography and Geo-Information Science, 2013,29(4):13-16. ]

[12]
金澄, 安晓亚, 崔海福, 等. 矢量瓦片地图线化简算法研究[J]. 地球信息科学学报, 2019,21(10):1502-1509.

DOI

[ Jin C, An X Y, Cui H F, et al. An algorithm for simplifying linear elements of vector tile maps[J]. Journal of Geo-information Science, 2019,21(10):1502-1509. ]

[13]
朱笑笑, 张丰, 杜震洪. 顾及要素空间分布特征的稠疏矢量瓦片构建方法研究[J]. 浙江大学学报:理学版, 2017(44):591-598.

[ Zhu X X, Zhang F, Du Z H. A method of the dense-sparse vector tile generation accounting for the spatial distribution of features[J]. Journal of Zhejiang University (Science Edition), 2017(44):591-598. ]

[14]
Butler H, Daly M, Doyle A, et al. The geojson format[S]. https://tools.ietf.org/html/rfc7946. 2016-08.

[15]
Vladimir A, John F, Eric F, et al. Mapbox vector tile specification[EB/OL]. https://github.com/mapbox/vector-tile-spec. 2018-05.

[16]
Zaharia M, Chowdhury M, Franklin M J, et al. Spark: cluster computing with working sets[C]// Usenix Conference on Hot Topics in Cloud Computing. 2010.

[17]
Douglas D H, Peucker T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973,10(2):112-122.

DOI

[18]
Eric F, Konstantin K, Tom M, et al. MBTiles specification[EB/OL]. https://github.com/mapbox/mbtiles-spec. 2018-02.

[19]
Li H, Ghodsi A, Zaharia M, et al. Tachyon: reliable, memory speed storage for cluster computing frameworks[C]// Proceedings of the ACM Symposium on Cloud Computing. ACM, 2014:1-15.

[20]
The Alluxio Open Foundation. Key-value system client api[EB/OL]. https://github.com/Alluxio/alluxio/blob/bra nch-1.8/docs/en/api/Key-Value-System-API.md. 2018-10.

[21]
Eric Fischer, Spring Meyer , Tippecanoe[EB/OL]. https://github.com/mapbox/tippecanoe, 2014-02-2.

[22]
Geofabrik GmbH, OpenStreetMap Contributors. OpenStreetMap Data Extracts[EB/OL]. https://download.geofabrik.de/, 2018.

Options
Outlines

/

〈 〉