留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

俞丽君 张丰 刘仁义 杜震洪

俞丽君, 张丰, 刘仁义, 杜震洪. 一种面向矢量瓦片高效构建的空间索引方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(10): 1633-1641. doi: 10.13203/j.whugis20180032
引用本文: 俞丽君, 张丰, 刘仁义, 杜震洪. 一种面向矢量瓦片高效构建的空间索引方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(10): 1633-1641. doi: 10.13203/j.whugis20180032
YU Lijun, ZHANG Feng, LIU Renyi, DU Zhenhong. A Spatial Indexing Method for Efficient Generation of Vector Tiles[J]. Geomatics and Information Science of Wuhan University, 2020, 45(10): 1633-1641. doi: 10.13203/j.whugis20180032
Citation: YU Lijun, ZHANG Feng, LIU Renyi, DU Zhenhong. A Spatial Indexing Method for Efficient Generation of Vector Tiles[J]. Geomatics and Information Science of Wuhan University, 2020, 45(10): 1633-1641. doi: 10.13203/j.whugis20180032

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

doi: 10.13203/j.whugis20180032
基金项目: 

国家自然科学基金 41471313

国家自然科学基金 41671391

国家重点研发计划 2017YFB0503600

国家重点研发计划 2016YFC0803105

详细信息

A Spatial Indexing Method for Efficient Generation of Vector Tiles

Funds: 

The National Natural Science Foundation of China 41471313

The National Natural Science Foundation of China 41671391

the National Key Research and Development Program of China 2017YFB0503600

the National Key Research and Development Program of China 2016YFC0803105

More Information
    Author Bio:

    YU Lijun, postgraduate, specializes in Web GIS applications and spatial big data organization and management. E-mail: yulijunzj@zju.edu.cn

    Corresponding author: ZHANG Feng, PhD, associate professor. E-mail: zfcarnation@zju.edu.cn
  • 摘要: 针对矢量瓦片在构建过程中对原始矢量数据源检索性能的不足, 提出了一种基于改进网格与递归网格排序(sort-tile-recursive, STR) R-树的混合索引结构, 用于提升对数据源的空间查询效率。该混合索引通过瓦片金字塔上下文信息改进了一级网格索引的查询方式, 减少了查询过程中的空间比较。同时, 使用STR R-树作为二级索引, 有效减轻了因矢量数据空间分布不均衡所带来的影响, 实现了二级查询优化。实验表明, 对比数据库常用空间索引(如网格索引、四叉树索引、R-树/R*树索引), 该混合索引对不同空间分布的矢量数据适应良好, 能显著提高对矢量数据源的查询性能, 加速瓦片的构建。
  • 图  1  矢量瓦片金字塔模型

    Figure  1.  Vector Tiles Pyramid Model

    图  2  网格索引

    Figure  2.  Grid Index

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

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

    图  4  混合索引数据结构

    Figure  4.  Data Structure of Hybrid Index

    图  5  查询方式对比

    Figure  5.  Comparison of Spatial Range Query

    图  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)

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

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

    表  1  测试数据

    Table  1.   Test Data

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

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV
  • [1] 杨树强, 陈火旺, 王峰.矢量和栅格一体化的数据模型[J].软件学报, 1998, 9(2):12-17 http://www.cqvip.com/Main/Detail.aspx?id=2901965

    Yang Shuqiang, Chen Huowang, Wang Feng. An Unification Data Model of Vector and Raster[J]. Journal of Software, 1998, 9(2):12-17 http://www.cqvip.com/Main/Detail.aspx?id=2901965
    [2] 郭明强, 黄颖, 吴亮, 等.网络环境下矢量数据高效并行可视化方法[J].武汉大学学报·信息科学版, 2014, 39(11): 1 382-1 386 doi:  10.13203/j.whugis20130296

    Guo Mingqiang, Huang Ying, Wu Liang, et al. An Efficient Method for Parallel Visualization of Vector Maps Under the Network Environment[J]. Geomatics and Information Science of Wuhan University, 2014, 39(11):1 382-1 386 doi:  10.13203/j.whugis20130296
    [3] Cecconi A. Integration of Cartographic Generalization and Multi-scale Databases for Enhanced Web Mapping[D]. Switzerland: ETH Zürich, 2003
    [4] 艾廷华, 成建国.对空间数据多尺度表达有关问题的思考[J].武汉大学学报·信息科学版. 2005, 30(5): 377-382 doi:  10.3321/j.issn:1671-8860.2005.05.001

    Ai Tinghua, Cheng Jianguo. Key Issues of Multi-scale Representation of Spatial Data[J]. Geomatics and Information Science of Wuhan University, 2005, 30(5):377-382 doi:  10.3321/j.issn:1671-8860.2005.05.001
    [5] Cheng C, Niu F, Cai J, et al. Extensions of GAP-tree and Its Implementation Based on a Non-Topological Data Model[J]. International Journal of Geographical Information Science, 2008, 22(6): 657-673 doi:  10.1080/13658810701602120
    [6] 程昌秀.矢量数据多尺度空间索引方法的研究[J].武汉大学学报·信息科学版, 2009, 34(5): 597-601 http://www.cnki.com.cn/Article/CJFDTotal-WHCH200905023.htm

    Cheng Changxiu. A Multi-scale Spatial Index Method[J]. Geomatics and Information Science of Wuhan University, 2009, 34(5): 597-601 http://www.cnki.com.cn/Article/CJFDTotal-WHCH200905023.htm
    [7] 孙璐, 陈荦, 刘露, 等.一种面向服务器制图可视化的矢量数据多尺度组织方法[J].计算机工程与科学, 2014, 36(2):226-232 http://www.cqvip.com/QK/94293X/20142/49932889.html

    Sun Lu, Chen Luo, Liu Lu, et al. A Multi-scale Management Method for Visualization of Vector Data on Server Cluster[J]. Computer Engineering & Science, 2014, 36(2):226-232 http://www.cqvip.com/QK/94293X/20142/49932889.html
    [8] Wan L, Huang Z, Peng X. An Effective NoSQL-based Vector Map Tile Management Approach[J]. ISPRS International Journal of Geo-Information, 2016, 5(11): 215 http://www.researchgate.net/publication/310389408_An_Effective_NoSQL-Based_Vector_Map_Tile_Management_Approach
    [9] García R, de Castro J P, Verdú E, et al. Web Map Tile Services for Spatial Data Infrastructures: Management and Optimization[M]//Bateira C. Cartography-A Tool for Spatial Analysis.Philippines: InTech, 2012
    [10] Růžička J. Comparing Speed of Web Map Service with GeoServer on ESRI Shapefile and PostGIS[J]. Geo-informatics FCE CTU, 2016, 15(1): 3-9 http://www.ingentaconnect.com/content/doaj/18022669/2016/00000015/00000001/art00002
    [11] Obe R O, Hsu L S. PostGIS in Action[M]. Greenwich, CT, USA: Manning Publications Co, 2011
    [12] 王梅欣.分布式矢量瓦片生产与访问系统的设计与实现[D].西安: 西安电子科技大学, 2016

    Wang Meixin. The Design and Implementation of the Distributed Vector Tile Generation and Access System[D]. Xi'an: Xidian University, 2016
    [13] Shang X H. A Study on Efficient Vector Mapping with Vector Tiles Based on Cloud Server Architecture[D]. Alberta: University of Calgary, 2015
    [14] Moshi M, Nahar N, Rahman R, et al. MapBeing: An Architecture for Manipulating and Publishing Vector Data in Web Based Geographic Information System[C]. The 8th Conference on Software, Knowledge, Information Management and Applications (SKIMA), Dhaka, Bangladesh, 2014
    [15] 朱笑笑, 张丰, 杜震洪, 等.顾及要素空间分布特征的稠疏矢量瓦片构建方法研究[J].浙江大学学报(理学版), 2017, 44(5):591-598 http://d.wanfangdata.com.cn/Periodical/zjdxxb201705015

    Zhu Xiaoxiao, Zhang Feng, Du Zhenhong, et al. A Method of the Dense-Sparse Vector Tile Generation Accounting for Spatial Distribution of Feature[J]. Journal of Zhejiang University: Science Edition, 2017, 44(5):591-598 http://d.wanfangdata.com.cn/Periodical/zjdxxb201705015
    [16] Teslya N. Web Mapping Service for Mobile Tourist Guide[C]. The 15th Conference of Open Innovations Association (FRUCT), Saint-Petersburg, Russia, 2014
    [17] 戴晶, 吴明光, 郑培蓓, 等.基于Hilbert曲线的STR索引改进算法[J].武汉大学学报·信息科学版, 2014, 39(7): 777-781 doi:  10.13203/j.whugis20130166

    Dai Jing, Wu Mingguang, Zheng Peibei, et al. An Improved STR-Tree Spatial Index Algorithm Based on Hilbert-Curve[J]. Geomatics and Information Scien-ce of Wuhan University, 2014, 39(7): 777-781 doi:  10.13203/j.whugis20130166
    [18] Zhang F, Zhou J, Liu R, et al. A New Design of High-Performance Large-Scale GIS Computing at a Finer Spatial Granularity: A Case Study of Spatial Join with Spark for Sustainability[J]. Sustainability, 2016, 8(9):926 doi:  10.3390/su8090926
    [19] 李德仁, 朱欣焰, 龚健雅.从数字地图到空间信息网格-空间信息多级网格理论思考[J].武汉大学学报·信息科学版, 2003, 28(6):642-650 doi:  10.3321/j.issn:1671-8860.2003.06.004

    Li Deren, Zhu Xinyan, Gong Jianya. From Digital Map to Spatial Information Multi-grid-A Thought of Spatial Information Multi-grid Theory[J]. Geomatics and Information Science of Wuhan University, 2003, 28(6):642-650 doi:  10.3321/j.issn:1671-8860.2003.06.004
    [20] Zhang F, Zheng Y, Xu D, et al. Real-Time Spatial Queries for Moving Objects Using Storm Topology[J]. International Journal of Geo-Information, 2016, 5(10):178 doi:  10.3390/ijgi5100178
    [21] Leutenegger S T, Lopez M A, Edgington J. STR: A Simple and Efficient Algorithm for R-Tree Packing[C]. Proceedings of the 13th IEEE ICDC, Birmingham, UK, 1997
    [22] Sun L S, He D Z, Zhao P F. A Research of Publishing Map Technique Based on Geoserver[J]. Asian Journal of Applied Sciences, 2015, 8:185-195 http://www.researchgate.net/publication/277661281_A_Research_of_Publishing_Map_Technique_Based_on_Geoserver
    [23] Moten D. Rtree[CP/OL]. https://github.com/davidmoten/rtree, 2014
  • [1] 刘鹏程, 许小峰, 杨敏.  一种顾及符号完整性的矢量瓦片地图改进方案 . 武汉大学学报 ● 信息科学版, 2022, 47(3): 455-462. doi: 10.13203/j.whugis20200033
    [2] 牛磊, 宋宜全, 张宏敏, 侯绍洋.  一种针对室内疏散的集成Hilbert曲线的R*树空间索引 . 武汉大学学报 ● 信息科学版, 2018, 43(9): 1416-1421. doi: 10.13203/j.whugis20160352
    [3] 翟卫欣, 程承旗, 童晓冲, 陈波.  利用地球立体剖分格网生成Subdivision R-树索引模型 . 武汉大学学报 ● 信息科学版, 2016, 41(4): 443-449. doi: 10.13203/j.whugis20140104
    [4] 刘爱龙, 杜清运, 张东, 蔡忠亮, 李鹤元.  嵌入式环境下全球尺度瓦片地图数据组织与索引机制 . 武汉大学学报 ● 信息科学版, 2015, 40(4): 516-520. doi: 10.13203/j.whugis20140415
    [5] 戴 晶, 吴明光, 郑培蓓, 王 蕾, 崔登吉, 陈泰生.  基于 hilbert曲线的str索引改进算法 . 武汉大学学报 ● 信息科学版, 2014, 39(7): 777-781.
    [6] 杨建思.  一种利用面元拟合的地面点云数据三维R树索引方法 . 武汉大学学报 ● 信息科学版, 2013, 38(11): 1313-1316.
    [7] 李海亭, 李艳红, 彭清山.  一种基于标准纬线变更的瓦片索引方法 . 武汉大学学报 ● 信息科学版, 2012, 37(1): 122-125.
    [8] 付仲良, 刘思远.  MR-tree空间索引的Voronoi图改进及其并行空间查询方法 . 武汉大学学报 ● 信息科学版, 2012, 37(12): 1490-1494.
    [9] 陈迪, 朱欣焰, 周春辉, 苏科华.  区域分片下的分布式空间查询处理与并行调度方法 . 武汉大学学报 ● 信息科学版, 2012, 37(8): 892-896.
    [10] 龚俊, 谢潇.  基于R树索引的三维可视化查询方法 . 武汉大学学报 ● 信息科学版, 2011, 36(10): 1140-1143.
    [11] 邓敏, 黄雪萍, 刘慧敏, 李光强.  利用自然语言空间关系的空间查询方法研究 . 武汉大学学报 ● 信息科学版, 2011, 36(9): 1089-1093.
    [12] 周芹, 钟耳顺, 黄耀欢, 郭会.  大型空间数据库的并发索引策略CQR树 . 武汉大学学报 ● 信息科学版, 2009, 34(7): 856-858.
    [13] 程昌秀.  矢量数据多尺度空间索引方法的研究 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 597-601.
    [14] 王涛, 毋河海, 刘纪平.  基于区间树索引的等高线提取算法 . 武汉大学学报 ● 信息科学版, 2007, 32(2): 131-134.
    [15] 朱庆, 龚俊.  一种改进的真三维R树空间索引方法 . 武汉大学学报 ● 信息科学版, 2006, 31(4): 340-343.
    [16] 余亮, 边馥苓.  一种原生XML空间索引及查询语言 . 武汉大学学报 ● 信息科学版, 2006, 31(10): 936-939.
    [17] 郭晶, 刘广军, 董绪荣, 郭磊.  基于空间网格和Hilbert R-tree的二级R-tree空间索引 . 武汉大学学报 ● 信息科学版, 2005, 30(12): 1084-1088.
    [18] 郭菁, 郭薇, 胡志勇.  大型GIS空间数据库的有效索引结构QR-树 . 武汉大学学报 ● 信息科学版, 2003, 28(3): 306-310.
    [19] 马林兵, 龚健雅.  空间信息自然语言查询接口的研究与应用 . 武汉大学学报 ● 信息科学版, 2003, 28(3): 301-305.
    [20] 谈国新, 林宗坚, 卢健.  多值图像的自适应空间索引结构研究 . 武汉大学学报 ● 信息科学版, 1995, 20(4): 296-300.
  • 加载中
图(8) / 表(5)
计量
  • 文章访问数:  823
  • HTML全文浏览量:  176
  • PDF下载量:  107
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-04-05
  • 刊出日期:  2020-10-05

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

doi: 10.13203/j.whugis20180032
    基金项目:

    国家自然科学基金 41471313

    国家自然科学基金 41671391

    国家重点研发计划 2017YFB0503600

    国家重点研发计划 2016YFC0803105

    作者简介:

    俞丽君, 硕士, 主要从事WebGIS应用和空间大数据组织管理研究。yulijunzj@zju.edu.cn

    通讯作者: 张丰, 博士, 副教授。zfcarnation@zju.edu.cn
  • 中图分类号: P208

摘要: 针对矢量瓦片在构建过程中对原始矢量数据源检索性能的不足, 提出了一种基于改进网格与递归网格排序(sort-tile-recursive, STR) R-树的混合索引结构, 用于提升对数据源的空间查询效率。该混合索引通过瓦片金字塔上下文信息改进了一级网格索引的查询方式, 减少了查询过程中的空间比较。同时, 使用STR R-树作为二级索引, 有效减轻了因矢量数据空间分布不均衡所带来的影响, 实现了二级查询优化。实验表明, 对比数据库常用空间索引(如网格索引、四叉树索引、R-树/R*树索引), 该混合索引对不同空间分布的矢量数据适应良好, 能显著提高对矢量数据源的查询性能, 加速瓦片的构建。

English Abstract

俞丽君, 张丰, 刘仁义, 杜震洪. 一种面向矢量瓦片高效构建的空间索引方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(10): 1633-1641. doi: 10.13203/j.whugis20180032
引用本文: 俞丽君, 张丰, 刘仁义, 杜震洪. 一种面向矢量瓦片高效构建的空间索引方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(10): 1633-1641. doi: 10.13203/j.whugis20180032
YU Lijun, ZHANG Feng, LIU Renyi, DU Zhenhong. A Spatial Indexing Method for Efficient Generation of Vector Tiles[J]. Geomatics and Information Science of Wuhan University, 2020, 45(10): 1633-1641. doi: 10.13203/j.whugis20180032
Citation: YU Lijun, ZHANG Feng, LIU Renyi, DU Zhenhong. A Spatial Indexing Method for Efficient Generation of Vector Tiles[J]. Geomatics and Information Science of Wuhan University, 2020, 45(10): 1633-1641. doi: 10.13203/j.whugis20180032
  • 矢量数据模型是地理信息系统中常用的空间对象表达模型[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-树的混合索引作为切片程序与数据源之间的检索加速器, 以基于矢量瓦片金字塔特点的查询方式提高空间数据的检索效率, 以二级索引优化索引结构, 应对不同类型数据的空间分布问题。

    • 瓦片地图金字塔模型是一种多分辨率的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)中, txty代表整型瓦片坐标, 以ij代表层级, 且ji。其中式(1)代表低层级向高层级的映射, 式(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所示, 混合索引结构由两部分构成, 顶层以基于瓦片金字塔划分规则的网格索引对全局矢量数据进行分片组织, 局部以可选的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

    • 对矢量切片原始数据的范围检索是依据矢量瓦片所对应的空间范围构建查询矩形, 并对空间索引进行范围查询的过程。对网格索引的划分需适应瓦片的范围查询, 否则易产生多路查询, 见图 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-树索引, 则进行递归检索; 若没有构建, 则遍历所有数据进行空间查询。

    • 实验中使用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堆内存。

    • 为了验证混合索引能否适应空间数据的非均匀分布, 如图 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)

    • 为验证混合索引在矢量瓦片构建场景中的数据检索性能, 分别与冗余度在[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-树将无法体现优势, 同时也会因为索引结构内存占用过高而影响整体的检索效率。

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

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

参考文献 (23)

目录

    /

    返回文章
    返回