一种面向矢量瓦片高效构建的空间索引方法
发布时间：2021-01-08 22:24
针对矢量瓦片在构建过程中对原始矢量数据源检索性能的不足,提出了一种基于改进网格与递归网格排序（sort-tile-recursive,STR）R-树的混合索引结构,用于提升对数据源的空间查询效率。该混合索引通过瓦片金字塔上下文信息改进了一级网格索引的查询方式,减少了查询过程中的空间比较。同时,使用STR R-树作为二级索引,有效减轻了因矢量数据空间分布不均衡所带来的影响,实现了二级查询优化。实验表明,对比数据库常用空间索引（如网格索引、四叉树索引、R-树/R*树索引）,该混合索引对不同空间分布的矢量数据适应良好,能显著提高对矢量数据源的查询性能,加速瓦片的构建。
【文章来源】：武汉大学学报(信息科学版). 2020,45(10)北大核心
【文章页数】：9 页
【部分图文】：
矢量瓦片金字塔模型
对于线、多边形等数据，需基于几何体最小外包矩形的左上角与右下角点利用式（4）计算两点对应的网格坐标，分别为T1(tx1,ty1)和T2(tx2,ty2)，取所有与外包矩形重叠的网格T (tx,ty):tx1≤tx≤tx2且ty1≤ty≤ty2且tx,ty∈Z，并冗余存储该空间对象。对网格索引的范围查询与非单点数据的存储过程相似，可根据上述规则实现快速定位。然而，由于普通网格索引的划分规则与金字塔划分规则不同，如图2所示，在瓦片范围查询时，查询矩形无法与网格索引相适应，易产生多路查询。此外，由于矢量数据空间分布不均衡，网格索引中各存储单元的负载亦会发生严重倾斜。若以细粒度划分网格以解决倾斜问题，将会导致数据的过度冗余，增加内存压力[18]。综上所述，为减少多路查询和二级过滤时的数据量，依据金字塔划分方式对网格索引进行划分，以适应矢量瓦片的范围查询。同时，为顾及矢量数据多样的空间分布特征，以二级索引优化网格结构，加速二级检索。
其中，网格索引的划分将依据预先设定的冗余度值与矢量瓦片金字塔上下文唯一确定。由于矢量瓦片金字塔中每一层级划分粒度的不同，对于同一份矢量数据，依据金字塔每一层级构建的网格索引冗余度也不尽相同。确定适宜冗余度大小的网格索引划分是改进网格索引构建的关键。如图1所示，假设以金字塔第二层级作为基准层级构建网格索引，以该层级表示的空间范围作为网格索引的四至范围，以瓦片表示的实际尺寸作为网格单元的大小。基准层级的确定可通过二分法实现，首先依据矢量数据的空间形态初步确定初始层级，再依据冗余度判定，最终确定最接近预设经验冗余度值的层级为基准层级。如图4所示，混合索引的二级结构以单链表或STR R-树实现。单链表是以单向指针相连的常用数据结构，拥有较高的空间利用率，但在范围搜索时需通过线性搜索遍历所有对象。STR R-树是对R-树打包方式的改进，其通过对静态有界的多维数据进行良好的空间划分形成高度平衡的R-树，从而增强空间范围查询的性能[21]。通常情况下，STR R-树在检索时的时间复杂度为对数时间，但由于节点间的区域重叠，其真正的时间复杂度将介于对数时间与线性时间之间。基于对数时间复杂度与线性时间复杂度的变化特点，当索引的数据量较小时，STR R-树无法发挥其优势，故在二级组织结构选择时将以网格单元中存储的数据量进行评估，若数据量大于预设的经验阈值，则构建二级STR R-树索引，否则仍以链表结构存储。如图3(b）所示，设定阈值为10，那么网格索引结构中G1、G4网格将构建STR R-树二级索引，而网格G2、G3则不进行构建。
【参考文献】：
期刊论文
[1]顾及要素空间分布特征的稠疏矢量瓦片构建方法研究[J]. 朱笑笑,张丰,杜震洪,刘仁义,余华芬. 浙江大学学报(理学版). 2017(05)
[2]网络环境下矢量数据高效并行可视化方法[J]. 郭明强,黄颖,吴亮,谢忠. 武汉大学学报(信息科学版). 2014(11)
[3]基于Hilbert曲线的STR索引改进算法[J]. 戴晶,吴明光,郑培蓓,王蕾,崔登吉,陈泰生. 武汉大学学报(信息科学版). 2014(07)
[4]一种面向服务器制图可视化的矢量数据多尺度组织方法[J]. 孙璐,陈荦,刘露,苏德国. 计算机工程与科学. 2014(02)
[5]矢量数据多尺度空间索引方法的研究[J]. 程昌秀. 武汉大学学报(信息科学版). 2009(05)
[6]对空间数据多尺度表达有关问题的思考[J]. 艾廷华,成建国. 武汉大学学报(信息科学版). 2005(05)
[7]从数字地图到空间信息网格——空间信息多级网格理论思考[J]. 李德仁,朱欣焰,龚健雅. 武汉大学学报(信息科学版). 2003(06)
[8]矢量和栅格一体化的数据模型[J]. 杨树强,陈火旺,王峰. 软件学报. 1998(02)
硕士论文
[1]分布式矢量瓦片生产与访问系统的设计与实现[D]. 王梅欣.西安电子科技大学 2016
本文编号：2965414
【文章来源】：武汉大学学报(信息科学版). 2020,45(10)北大核心
【文章页数】：9 页
【部分图文】：
矢量瓦片金字塔模型
对于线、多边形等数据，需基于几何体最小外包矩形的左上角与右下角点利用式（4）计算两点对应的网格坐标，分别为T1(tx1,ty1)和T2(tx2,ty2)，取所有与外包矩形重叠的网格T (tx,ty):tx1≤tx≤tx2且ty1≤ty≤ty2且tx,ty∈Z，并冗余存储该空间对象。对网格索引的范围查询与非单点数据的存储过程相似，可根据上述规则实现快速定位。然而，由于普通网格索引的划分规则与金字塔划分规则不同，如图2所示，在瓦片范围查询时，查询矩形无法与网格索引相适应，易产生多路查询。此外，由于矢量数据空间分布不均衡，网格索引中各存储单元的负载亦会发生严重倾斜。若以细粒度划分网格以解决倾斜问题，将会导致数据的过度冗余，增加内存压力[18]。综上所述，为减少多路查询和二级过滤时的数据量，依据金字塔划分方式对网格索引进行划分，以适应矢量瓦片的范围查询。同时，为顾及矢量数据多样的空间分布特征，以二级索引优化网格结构，加速二级检索。
其中，网格索引的划分将依据预先设定的冗余度值与矢量瓦片金字塔上下文唯一确定。由于矢量瓦片金字塔中每一层级划分粒度的不同，对于同一份矢量数据，依据金字塔每一层级构建的网格索引冗余度也不尽相同。确定适宜冗余度大小的网格索引划分是改进网格索引构建的关键。如图1所示，假设以金字塔第二层级作为基准层级构建网格索引，以该层级表示的空间范围作为网格索引的四至范围，以瓦片表示的实际尺寸作为网格单元的大小。基准层级的确定可通过二分法实现，首先依据矢量数据的空间形态初步确定初始层级，再依据冗余度判定，最终确定最接近预设经验冗余度值的层级为基准层级。如图4所示，混合索引的二级结构以单链表或STR R-树实现。单链表是以单向指针相连的常用数据结构，拥有较高的空间利用率，但在范围搜索时需通过线性搜索遍历所有对象。STR R-树是对R-树打包方式的改进，其通过对静态有界的多维数据进行良好的空间划分形成高度平衡的R-树，从而增强空间范围查询的性能[21]。通常情况下，STR R-树在检索时的时间复杂度为对数时间，但由于节点间的区域重叠，其真正的时间复杂度将介于对数时间与线性时间之间。基于对数时间复杂度与线性时间复杂度的变化特点，当索引的数据量较小时，STR R-树无法发挥其优势，故在二级组织结构选择时将以网格单元中存储的数据量进行评估，若数据量大于预设的经验阈值，则构建二级STR R-树索引，否则仍以链表结构存储。如图3(b）所示，设定阈值为10，那么网格索引结构中G1、G4网格将构建STR R-树二级索引，而网格G2、G3则不进行构建。
【参考文献】：
期刊论文
[1]顾及要素空间分布特征的稠疏矢量瓦片构建方法研究[J]. 朱笑笑,张丰,杜震洪,刘仁义,余华芬. 浙江大学学报(理学版). 2017(05)
[2]网络环境下矢量数据高效并行可视化方法[J]. 郭明强,黄颖,吴亮,谢忠. 武汉大学学报(信息科学版). 2014(11)
[3]基于Hilbert曲线的STR索引改进算法[J]. 戴晶,吴明光,郑培蓓,王蕾,崔登吉,陈泰生. 武汉大学学报(信息科学版). 2014(07)
[4]一种面向服务器制图可视化的矢量数据多尺度组织方法[J]. 孙璐,陈荦,刘露,苏德国. 计算机工程与科学. 2014(02)
[5]矢量数据多尺度空间索引方法的研究[J]. 程昌秀. 武汉大学学报(信息科学版). 2009(05)
[6]对空间数据多尺度表达有关问题的思考[J]. 艾廷华,成建国. 武汉大学学报(信息科学版). 2005(05)
[7]从数字地图到空间信息网格——空间信息多级网格理论思考[J]. 李德仁,朱欣焰,龚健雅. 武汉大学学报(信息科学版). 2003(06)
[8]矢量和栅格一体化的数据模型[J]. 杨树强,陈火旺,王峰. 软件学报. 1998(02)
硕士论文
[1]分布式矢量瓦片生产与访问系统的设计与实现[D]. 王梅欣.西安电子科技大学 2016
本文编号：2965414
本文链接：https://www.wllwen.com/kejilunwen/dizhicehuilunwen/2965414.html
