一种面向矢量瓦片高效构建的空间索引方法

提高生活质量的一个方向就是优化居住空间。 #生活乐趣# #生活质量# #生活质量改善# #舒适居住空间#

矢量数据模型是地理信息系统中常用的空间对象表达模型[1]。然而, 目前的网络地图应用对矢量数据的多尺度可视化效率十分低下, 难以保证良好的交互体验[2]。矢量数据的多尺度表达可通过多尺度空间数据库[3-4]、多尺度空间索引树(如C-Tree、Gap-Tree等)[5-6]、基于层次细节(level of detail, LOD)的瓦片金字塔[7]等技术实现。其中, 矢量瓦片技术通过将海量数据化整为零、分层分片组织, 为大数据背景下矢量网络地图的多尺度可视化提供了有效的解决方案[8-9]。

目前, 矢量瓦片技术已有了一些突破性进展, 但对于切片阶段的矢量数据源查询方法依旧以传统方式为主。通用的矢量数据源包括以文件格式组织的空间数据文件及扩展了空间特性的数据库系统, 如基于网格索引的Shapefile文件和以四叉树或R-树索引的PostGIS、Oracle Spatial等空间数据库[10-11]。现行的切片项目通常以支持空间索引的数据源组织矢量数据, 例如, 王梅欣[12]在其分布式矢量瓦片生产系统中使用Shapefile文件作为输入源, 并用GDAL(geospatial data abstraction library)加载sbn与sbx索引文件进行检索加速。文献[13-16]将PostGIS作为数据存储层以加速数据检索。由此可见, 空间索引是矢量切片过程中空间数据高效检索的关键, 然而, 上述数据源提供的空间索引主要针对通用的空间范围检索, 对矢量数据的形态分布及对矢量切片场景中的空间数据检索均未经过特定优化。事实上, 矢量数据形态分布复杂, 无法以一种索引解决所有类型的数据组织问题[17-18]。矢量瓦片金字塔是对矢量数据的分级分片组织, 矢量瓦片的构建过程与金字塔上下文密切相关。在矢量切片场景中可通过瓦片金字塔的划分规则与瓦片间的映射关系对索引的组织与查询方式进行改进, 使之适应瓦片构建过程中密集的数据检索操作[7]。

综上所述, 当前的矢量切片项目普遍未考虑矢量瓦片金字塔自身的特点, 仅简单地使用各数据源提供的空间索引应对海量密集的空间检索。因此, 本文提出了一种基于改进网格及STR R-树的混合索引作为切片程序与数据源之间的检索加速器, 以基于矢量瓦片金字塔特点的查询方式提高空间数据的检索效率, 以二级索引优化索引结构, 应对不同类型数据的空间分布问题。

1 矢量瓦片金字塔

瓦片地图金字塔模型是一种多分辨率的LOD模型[9]。如图 1所示, 在不变的地理空间范围下, 依据四叉树剖分方式依次递归构建, 瓦片以坐标(缩放层级、行号、列号)标识, 可将上下级瓦片间的映射关系表示如下:

图  1  矢量瓦片金字塔模型

Figure  1.  Vector Tiles Pyramid Model

$$ \left\{ {\begin{array}{*{20}{c}} {t{x_j} = tx, {\rm{}}t{x_i} \times {2^{j - i}} \le tx < \left( {t{x_i} + 1} \right) \times {2^{j - i}}}\\ {t{y_j} = ty, {\rm{}}t{y_i} \times {2^{j - i}} \le ty < \left( {t{x_i} + 1} \right) \times {2^{j - i}}} \end{array}} \right. $$ (1) $$ \left\{ {\begin{array}{*{20}{c}} {t{x_i} = \left\lfloor {t{x_j} \times {2^{i - j}}} \right\rfloor }\\ {t{y_i} = \left\lfloor {t{y_j} \times {2^{i - j}}} \right\rfloor } \end{array}} \right. $$ (2)

式(1)、式(2)中, tx、ty代表整型瓦片坐标, 以i、j代表层级, 且j≥i。其中式(1)代表低层级向高层级的映射, 式(2)反之。

矢量瓦片金字塔中的瓦片数量随层级的增加呈指数增长, 但由于其层级间特定的映射关系, 所有矢量瓦片均可由金字塔中的某一层级瓦片合并或分裂所得。同一层级各矢量瓦片表示的空间范围大小相同, 空间位置呈规则排列的特征, 符合网格索引的划分规则。

综上所述, 矢量瓦片金字塔模型是对矢量数据在多个尺度上的分片管理模型, 其通过特定划分的多级网格结构组织数据。此外, 在矢量瓦片构建过程中需根据金字塔中每一张矢量瓦片所表示的空间范围对矢量数据源进行范围检索, 再根据查询得到的结果数据进行后续的切片操作。由此可见, 矢量瓦片金字塔不仅是矢量瓦片与矢量数据的分级组织模型, 在矢量瓦片构建过程的数据检索阶段亦起着十分重要的作用。

2 网格索引

网格索引是一种根据预定义的哈希规则计算空间对象所在网格坐标, 并将空间数据与之关联的索引机制[19]。网格索引对点数据的组织可通过一对一的映射关系进行精确计算[20], 而对于线、面等复杂数据, 由于空间对象可能跨越多个网格, 将形成一对多的映射关系, 对此, 引入冗余度作为数据集在索引中冗余存储的度量, 冗余度的计算公式如下:

$$ \alpha = \frac{{\mathop \sum \nolimits\limits_{i = 0}^n \mathop \sum \nolimits\limits_{k = 0}^m {N_{{\rm{til}}{{\rm{e}}_{i, k}}}}}}{N} $$ (3)

式中, ${N_{{\rm{til}}{{\rm{e}}_{i, k}}}}$代表大小为n×m的网格索引中坐标为(i, k)的网格单元存储的数据量大小; N代表矢量数据集的总数据量。

如图 2所示, 在目标投影坐标系统中, 设坐标系原点为$P1\left( {x1, y1} \right)$, 网格单元x轴方向大小为${\rm{cell}}x$, y轴方向大小为${\rm{cell}}y$, 目标点坐标为$P2\left( {x2, y2} \right)$, 那么该点所对应的网格坐标的计算公式如下:

图  2  网格索引

Figure  2.  Grid Index

$$ \left\{ {\begin{array}{*{20}{c}} {tx = \left\lfloor {\frac{{\left( {x2 - x1} \right)}}{{{\rm{cell}}x}}} \right\rfloor }\\ {ty = \left\lfloor {\frac{{\left( {y2 - y1} \right)}}{{{\rm{cell}}y}}} \right\rfloor } \end{array}} \right. $$ (4)

对于线、多边形等数据, 需基于几何体最小外包矩形的左上角与右下角点利用式(4)计算两点对应的网格坐标, 分别为$T1\left( {tx1, ty1} \right)$和$T2\left( {tx2, ty2} \right)$, 取所有与外包矩形重叠的网格$T{\rm{}}\left( {tx, ty} \right):tx1 \le tx \le tx2$且$ty1 \le ty \le ty2$且$tx, ty \in Z$, 并冗余存储该空间对象。

对网格索引的范围查询与非单点数据的存储过程相似, 可根据上述规则实现快速定位。然而, 由于普通网格索引的划分规则与金字塔划分规则不同, 如图 2所示, 在瓦片范围查询时, 查询矩形无法与网格索引相适应, 易产生多路查询。此外, 由于矢量数据空间分布不均衡, 网格索引中各存储单元的负载亦会发生严重倾斜。若以细粒度划分网格以解决倾斜问题, 将会导致数据的过度冗余, 增加内存压力[18]。综上所述, 为减少多路查询和二级过滤时的数据量, 依据金字塔划分方式对网格索引进行划分, 以适应矢量瓦片的范围查询。同时, 为顾及矢量数据多样的空间分布特征, 以二级索引优化网格结构, 加速二级检索。

3 面向矢量瓦片高效构建的索引实现与查询优化

在矢量切片场景中, 良好的空间数据组织方式可应对不同形态分布的矢量数据的组织, 优化查询, 加速瓦片构建。依据矢量瓦片金字塔划分规则, 本文提出一种针对该特定查询场景改进的混合索引结构, 用于组织矢量瓦片的原始数据, 实现瓦片构建过程中数据查询方式的优化。

3.1   混合索引结构设计与实现

如图 3所示, 混合索引结构由两部分构成, 顶层以基于瓦片金字塔划分规则的网格索引对全局矢量数据进行分片组织, 局部以可选的STR R-树索引优化组织。

图  3  基于改进网格及STR R-树的混合索引

Figure  3.  Hybrid Index Based on Improved Grid and STR R-tree

其中, 网格索引的划分将依据预先设定的冗余度值与矢量瓦片金字塔上下文唯一确定。由于矢量瓦片金字塔中每一层级划分粒度的不同, 对于同一份矢量数据, 依据金字塔每一层级构建的网格索引冗余度也不尽相同。确定适宜冗余度大小的网格索引划分是改进网格索引构建的关键。如图 1所示, 假设以金字塔第二层级作为基准层级构建网格索引, 以该层级表示的空间范围作为网格索引的四至范围, 以瓦片表示的实际尺寸作为网格单元的大小。基准层级的确定可通过二分法实现, 首先依据矢量数据的空间形态初步确定初始层级, 再依据冗余度判定, 最终确定最接近预设经验冗余度值的层级为基准层级。

如图 4所示, 混合索引的二级结构以单链表或STR R-树实现。单链表是以单向指针相连的常用数据结构, 拥有较高的空间利用率, 但在范围搜索时需通过线性搜索遍历所有对象。STR R-树是对R-树打包方式的改进, 其通过对静态有界的多维数据进行良好的空间划分形成高度平衡的R-树, 从而增强空间范围查询的性能[21]。通常情况下, STR R-树在检索时的时间复杂度为对数时间, 但由于节点间的区域重叠, 其真正的时间复杂度将介于对数时间与线性时间之间。基于对数时间复杂度与线性时间复杂度的变化特点, 当索引的数据量较小时, STR R-树无法发挥其优势, 故在二级组织结构选择时将以网格单元中存储的数据量进行评估, 若数据量大于预设的经验阈值, 则构建二级STR R-树索引, 否则仍以链表结构存储。如图 3 (b)所示, 设定阈值为10, 那么网格索引结构中G1、G4网格将构建STR R-树二级索引, 而网格G2、G3则不进行构建。

图  4  混合索引数据结构

Figure  4.  Data Structure of Hybrid Index

3.2   矢量数据源查询方法优化

对矢量切片原始数据的范围检索是依据矢量瓦片所对应的空间范围构建查询矩形, 并对空间索引进行范围查询的过程。对网格索引的划分需适应瓦片的范围查询, 否则易产生多路查询, 见图 5(e)、5(f)。以传统查询方式对基于金字塔划分的网格索引进行查询时仍会出现边界归属问题, 见图 5(c)、5(d), 当查询矩形右下角与网格边界重合时将命中无效的网格, 导致多路查询, 增加二级检索的压力。因此, 需根据金字塔层级瓦片间的映射规则改进混合索引的一级查询, 如图 5(a)、5 (b)就是以矢量瓦片坐标代替空间信息进行网格定位。

图  5  查询方式对比

Figure  5.  Comparison of Spatial Range Query

此外, 矢量数据空间分布不均易导致网格索引负载失衡, 仅以线性结构组织的高负载网格将难以满足大数据量情景下的高效检索, 因此基于混合索引的实现原理, 需根据不同的二级索引结构采取不同的检索策略, 对单链表进行检索时需遍历所有数据, 而对STR R-树检索时可依据与上层节点(非叶子节点)的比较排除无关的区域, 减少无效查询, 图 3中构建的查询矩形是对高负载网格的查询, 而从图 4可见, 基于STR R-树的二级索引可明显缩短查询路径, 减少不必要的空间比较。对混合索引的具体查询步骤如下:

1) 根据当前瓦片的层级信息确定其在网格索引对应于矢量瓦片金字塔中层级的上层还是下层, 若在网格索引上层(包括索引所在层级)则进入步骤2), 否则进入步骤3)。

2) 根据式(1)计算坐标为$T\left( {i, t{x_i}, t{y_i}} \right)$的瓦片在网格索引中对应的所有网格$G\left( {j, t{x_j}, t{y_j}} \right)$。如图 1中, 瓦片$Q1$查询得到$\left\{ {R1, R2, R3, R4} \right\}{\rm{}}$, 瓦片$Q6$查询得到$\left\{ {R6} \right\}$, 将查询所得的网格单元中的数据加入结果集中, 进行去重后返回。

3) 根据式(2)计算坐标为$T\left( {j, t{x_j}, t{y_j}} \right)$的瓦片在网格索引中对应的网格$G\left( {i, t{x_i}, t{y_i}} \right)$。如图 1所示, 瓦片$Q2Q3Q4Q5$查询得$\left\{ {R5} \right\}$, 再根据瓦片的空间范围信息进行二级精确查询, 若网格单元中使用了STR R-树索引, 则进行递归检索; 若没有构建, 则遍历所有数据进行空间查询。

4 实验与分析

实验中使用OpenStreetMap全国范围内的土地利用、水系、路网、房屋4种不同类型的数据进行索引构建, 测试混合索引对不同空间分布数据的适应性及其在3~17级矢量瓦片构建过程中对原始矢量数据的查询性能, 构建的混合索引中一级网格的冗余度均限制在[1.1, 1.25]之间。实验数据如表 1所示, 其中, 水系与路网数据要素形态差异明显, 多数要素空间跨度较大, 空间分布严重失衡; 而土地利用与房屋数据则更为细碎, 形态差异较小, 空间分布较为均匀, 呈多点聚集的分布状态。

表  1  测试数据

Table  1.  Test Data

数据名称 数据类型 数据量/万 数据大小/MB 水系数据 面 11 278 土地利用数据 面 23 140 路网数据 线 200 893 房屋数据 面 80 264

实验的硬件环境为主频3.6 GHz, i7-4790处理器(4核)和8 GB内存的台式计算机, 虚拟机设置5 GB堆内存。

4.1   适应性分析

为了验证混合索引能否适应空间数据的非均匀分布, 如图 6与图 7所示, 对水系数据进行索引可视化制图, 通过对比发现混合索引可通过构建二级STR R-树索引的方式减轻因矢量数据空间分布不均匀所带来的影响。从图 6可见, 四叉树索引为非平衡树结构, 难以应对非均匀分布的数据; R*树索引与STR R-树索引在大数据量情况下, 节点间的重叠面积与树的深度都会增加; 网格索引在数据密集区域将过饱和存储数据。从图 7全局图可见, 算法只对有数据区域构建网格索引, 在数据密集区域构建二级STR R-树索引。从图 7局部图可见, 图中的填充矩形代表R-树的叶子节点, 不同的填充颜色代表不同的R-树, 每一棵STR R-树归属不同的网格。由此可见, 该混合索引可较好地分散数据的压力, 同时很好地顾及了数据密集区域的索引优化。

图  6  4种空间索引(水系数据)

Figure  6.  Four Spatial Indexes (River Networks)

图  7  基于改进网格与STR R-树的混合索引(水系数据)

Figure  7.  The Hybrid Index Based on Improved Grid and STR R-Tree (River Networks)

4.2   查询性能评估

为验证混合索引在矢量瓦片构建场景中的数据检索性能, 分别与冗余度在[1.1, 1.25]之间的普通网格索引(未改进查询方式)、基于JTS(Java拓扑套件, Java Topology Suit)空间索引库改进的四叉树索引[22]、JTS空间索引库中实现的STR R-树索引、Moten[23]实现的R*树索引在并行和串行两种运行环境中进行矢量瓦片原始数据范围查询的效率对比。

图 8表示不同索引在并行构建3~17级矢量瓦片时完成矢量数据检索的总耗时, 对比其他空间索引, 本文提出的混合索引在该检索场景中有4倍至百倍的效率提升。同时, 与表 2~表 5中串行环境下的3~17级范围检索总耗时对比, 混合索引可较好地适应高并发检索的应用场景。

图  8  并行化构建场景中各索引查询性能对比(3~17级)

Figure  8.  Comparison of Query Performance of Each Index in Parallel Generation (3~17)

表  2  矢量瓦片金字塔各层级查询效率对比(水系数据)

Table  2.  Comparison of Query Performance of All Levels in Vector Tile Pyramid (River Networks)

瓦片金字塔层级 查询效率/s 368×268网格索引 改进的四叉树索引 STR R-树索引 R*树索引 改进的网格索引 基于改进网格与STR R-树的混合索引 3~9 0.30 0.59 0.11 0.73 0.23 0.22 10 0.13 0.81 0.08 0.98 0.04 0.04 11~15 14.47 219.34 27.70 241.21 7.47 6.90 16 47.76 789.18 86.20 868.26 21.83 20.00 17 169.35 > 1 800.00 286.90 3 600.00 85.18 75.42 3~17 232.01 > 3 600.00 400.99 > 3 600.00 114.75 102.58

表  3  瓦片金字塔各层级查询效率对比(房屋数据)

Table  3.  Comparison of Query Performance of All Levels in Vector Tile Pyramid (Buildings)

瓦片金字塔层级 查询效率/s 8 207×10 570网格索引 改进的四叉树索引 STR R-树索引 R*树索引 改进的网格索引 基于改进网格与STR R-树的混合索引 3~14 21.72 34.02 13.16 95.91 25.84 25.72 15 12.28 102.25 29.02 303.09 9.14 9.27 16 35 395.37 120.18 > 1 800.00 21.34 21.13 17 121.28 1 453.88 350.02 > 2 600.00 68.04 65.94 3~17 190.28 > 1 600.00 512.38 > 5 400.00 124.36 122.06

表  4  瓦片金字塔各层级查询效率对比(路网数据)

Table  4.  Comparison of Query Performance of All Levels in Vector Tile Pyramid (Roads)

瓦片金字塔层级 查询效率/s 564×434网格索引 改进的四叉树索引 STR R-树索引 R*树索引 改进的网格索引 基于改进网格与STR R-树的混合索引 3~10 14.9 34.11 1.25 12.32 8.22 8.22 11 6.07 43.45 0.51 18.9 0.42 0.40 12~15 109.3 > 3 600.00 66.51 > 1 800.00 108.37 64.69 16 297.55 > 7 200.00 163.76 > 5 400.00 302.88 159.19 17 > 1 800.00 > 9 000.00 643.78 > 7 200.00 852.34 596.33 3~17 > 3 600.00 > 21 600.00 875.81 > 14 400.00 1272.23 828.83

表  5  瓦片金字塔各层级查询效率对比(土地利用数据)

Table  5.  Comparison of Query Performance of All Levels in Vector Tile Pyramid (Landuse)

瓦片金字塔层级 查询效率/s 345×266网格索引 改进的四叉树索引 STR R-树索引 R*树索引 改进的网格索引 基于改进网格与STR R-树的混合索引 3~10 0.63 1.36 0.44 1.41 0.67 0.73 11 0.16 2.11 0.43 1.82 0.09 0.09 12~15 16.17 192.60 28.60 251.65 7.21 6.88 16 55.38 554.94 80.58 741.29 17.63 16.39 17 216.55 > 1 800.00 311.34 > 1 800.00 65.98 63.02 3~17 288.89 > 3 600.00 421.39 > 3 600.00 91.58 87.11

为了进一步分析索引本身的查询性能, 排除线程调度与网络传输带来的性能影响。设计串行环境下的对比实验, 由表 2~表 5的对比可知:

1) 改进的查询方式在高层级矢量瓦片构建时发挥了重要作用。改进的网格索引在划分方式与查询方式上都依据矢量瓦片金字塔进行了优化。基于不同层级瓦片的映射关系, 通过瓦片坐标的换算快速定位到相应的网格坐标, 在高层级瓦片查询时不会构成多路查询, 在低层级瓦片查询时可避免二次查找。

2) 网格索引本身的冗余存储特点会略微增加查询的成本。当瓦片的层级小于网格索引所在层级时, 混合索引的查询性能略低于STR R-树索引, 这是由于混合索引查询得到的结果可能存在着冗余, 需进行去重操作。

3) 基于STR R-树的二级索引可有效加速数据检索。对比改进的网格索引和基于改进网格与STR R-树的混合索引, 发现随着瓦片层级的增加, 两种索引的性能差距越为明显。由于矢量瓦片的查询范围会逐级减小, 若不采用二级索引, 在高层级瓦片进行数据源范围查询时将遍历网格单元内全部的数据, 增加很多无效检索。

4) 对比改进了查询方式的网格索引, 发现混合索引对空间分布严重失衡的水系、路网数据具有较高的效率, 而对于分布较为均匀的土地利用与房屋数据的优势较小。混合索引是改进的网格索引在二级存储结构上的扩展, 当数据分布不均匀时, 负载过重的网格将以STR R-树代替单链表进行存储, 在检索时可避免对存储单元的完全遍历。而当数据分布较为均匀时, 若设置较高的经验阈值, 混合索引将退化为网格索引; 反之, STR R-树将无法体现优势, 同时也会因为索引结构内存占用过高而影响整体的检索效率。

5 结语

矢量瓦片是网络地图发展中的一个重要实现, 如何高效构建矢量瓦片必然会成为其中的一个研究重点, 而对矢量切片原始空间数据的范围检索是构建矢量瓦片的起点, 选取一种合适的空间索引对矢量瓦片快速构建具有重要意义。

本文提出的基于改进网格及STR R-树的混合索引有效提高了矢量瓦片构建场景中对矢量数据进行空间范围查询的性能。该混合索引利用矢量瓦片金字塔的组织与结构特点, 改进了网格索引的查询方式, 同时, 基于STR R-树构建二级索引, 优化查询。实验表明, 与其他数据库常用空间索引相比, 在矢量切片串行及并行化范围查询任务中, 混合索引在应对不同形态分布的空间数据的查询时具有普遍优势。然而, 本文的研究仅局限于内存空间索引, 对大数据量的情况可能存在内存容量的限制。对此, 可从构建外存索引或分布式索引这两方面进行更深入的探索。

网址：一种面向矢量瓦片高效构建的空间索引方法 https://www.yuejiaxmz.com/news/view/289506

相关内容

构建一个半开放式创意、高效的工作空间
一种果蔬保鲜型瓦楞纸箱的制作方法
【经验分享】高效使用搜索引擎的几个方法
一种植物叶面高效清洁剂的制作方法
五种时间，高效管理你的正向生活
「 微 居 」一种极小户型的空间释放 / 戏构建筑设计
提高室内空气质量的5种方法
一种抽屉式三维类血管化组织培养器官芯片及其构建方法与流程
家的解码:空间句法对家空间研究的内容与方法
高效学习的18种常用方法

随便看看