留言板

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

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

虚拟战场环境时空数据的Hilbert码索引方法

吴宇豪 曹雪峰

吴宇豪, 曹雪峰. 虚拟战场环境时空数据的Hilbert码索引方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(9): 1403-1411. doi: 10.13203/j.whugis20190394
引用本文: 吴宇豪, 曹雪峰. 虚拟战场环境时空数据的Hilbert码索引方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(9): 1403-1411. doi: 10.13203/j.whugis20190394
WU Yuhao, CAO Xuefeng. Hilbert Code Index Method for Spatiotemporal Data of Virtual Battlefield Environment[J]. Geomatics and Information Science of Wuhan University, 2020, 45(9): 1403-1411. doi: 10.13203/j.whugis20190394
Citation: WU Yuhao, CAO Xuefeng. Hilbert Code Index Method for Spatiotemporal Data of Virtual Battlefield Environment[J]. Geomatics and Information Science of Wuhan University, 2020, 45(9): 1403-1411. doi: 10.13203/j.whugis20190394

虚拟战场环境时空数据的Hilbert码索引方法

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

国防科技项目基金 3601015

国家自然科学基金 41401465

国家自然科学基金 41371384

详细信息
    作者简介:

    吴宇豪,硕士生,主要从事全球离散网格研究。514536575@qq.com

    通讯作者: 曹雪峰,博士,副教授。CAO_Xue_Feng@163.com
  • 中图分类号: P208

Hilbert Code Index Method for Spatiotemporal Data of Virtual Battlefield Environment

Funds: 

The National Defense Science and Technology Project Foundation of China 3601015

the National Natural Science Foundation of China 41401465

the National Natural Science Foundation of China 41371384

More Information
    Author Bio:

    WU Yuhao, postgraduate, specializes in the discrete global grid system. E-mail:514536575@qq.com

    Corresponding author: CAO Xuefeng, PhD, associate professor. E-mail:CAO_Xue_Feng@163.com
  • 摘要: 在虚拟战场环境中,时空数据的高效组织是动态描述战场关键要素、实时分析军事行动计划的前提。首先对经度、纬度、时间进行同步层次嵌套细分来构建规则的多分辨率时空网格,然后基于Hilbert曲线设计时空格元编码,进而根据虚拟战场环境时空数据与时空格元Hilbert码的对应关系,提出一种基于Hilbert码的时空数据索引方法。在此基础上设计实验, 比较格元编码的时空邻近性、索引构建效率以及查询效率。结果表明,Hilbert码方法在邻近性上优于Morton码,索引构建速度满足大规模时空数据处理需要,且查询效率优于直接基于经度、纬度、时间查询和基于Morton码查询的方法,可作为虚拟战场中作战计划推演、战场环境要素可视化与分析等时空操作的基础。
  • 图  1  时空网格

    Figure  1.  Spatiotemporal Grid

    图  2  Hilbert曲线及其编码示例

    Figure  2.  Hilbert Curve and Its Encoding Examples

    图  3  Hilbert码索引框架

    Figure  3.  Hilbert Code Indexing Framework

    图  4  查询范围至Hilbert码转换

    Figure  4.  Query Range to Hilbert Code Conversion

    图  5  平均最大邻近距离对比

    Figure  5.  Comparison of Average Maximum Neighbor

    图  6  编码索引构建时间对比

    Figure  6.  Comparison of Coding Index Construction Time

    图  7  数据查询时间对比

    Figure  7.  Comparison of Data Query Time

    表  1  三维Hilbert曲线基因列表

    Table  1.   List of 3D Hilbert Curve Genes

    坐标变换 交换 求反
    G (0) tφ -
    G (1) λφ -
    G (2) - -
    G (3) tφ t′, φ
    G (4) tφ -
    G (5) - -
    G (6) λφ λ′, φ
    G (7) tφ t′, φ
    下载: 导出CSV

    表  2  细分码的映射关系f

    Table  2.   Encoding Mapping Relationship f

    (rφ, rλ, rt) 细分码(rφ, rλ, rt)
    (0, 0, 0) 0
    (0, 0, 1) 1
    (1, 0, 1) 2
    (1, 0, 0) 3
    (1, 0, 0) 3
    (1, 1, 0) 4
    (1, 1, 1) 5
    (0, 1, 1) 6
    (0, 1, 0) 7
    下载: 导出CSV

    表  3  平均最大邻近距离

    Table  3.   Average Maximum Neighbor Distance

    层级m 编码半径 平均最大邻近距离
    Hilbert码 Morton码 经纬度-时间直接编码
    1 1 1.00 2.00 2.00
    2 2 2.00 3.31 4.28
    3 4 3.27 5.10 9.15
    4 8 4.35 7.03 18.43
    5 16 5.85 9.32 38.81
    下载: 导出CSV

    表  4  编码索引构建时间/s

    Table  4.   Encoding Index Build Time/s

    层级 编码类型 数据量
    30万 60万 90万 120万 150万
    6 Hilbert 0.74 1.23 1.85 2.70 3.15
    Morton 0.61 1.21 2.08 2.52 3.12
    12 Hilbert 1.05 2.04 3.02 4.24 5.15
    Morton 0.98 1.98 2.95 4.06 4.97
    18 Hilbert 1.38 2.78 4.20 5.73 6.96
    Morton 1.31 2.63 3.99 5.56 6.62
    24 Hilbert 1.74 3.49 5.25 7.47 8.76
    Morton 1.64 3.29 4.95 6.84 8.31
    下载: 导出CSV
  • [1] 龚建华, 周洁萍, 张利辉.虚拟地理环境研究进展与理论框架[J].地球科学进展, 2010, 25(9):915-926 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dqkxjz201009003

    Gong Jianhua, Zhou Jieping, Zhang Lihui. Research Progress and Theoretical Framework of Virtual GeoGraphical Environment[J].Advances in Earth Science, 2010, 25(9):915-926 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dqkxjz201009003
    [2] Lin H, Chen M, Lu G. Virtual Geographic Environment:A Workspace for Computer-Aided Geographic Experiments[J]. Annals of the Association of American Geographers, 2013, 103(3):465-482 doi:  10.1080/00045608.2012.689234
    [3] Xu B, Lin H, Chou L, et al. Collaborative Virtual Geographic Environments: A Case Study of Air Pollution Simulation[J]. Information Sciences, 2011, 181(11):2 231-2 246 doi:  10.1016/j.ins.2011.01.017
    [4] 徐丙立, 林珲, 朱军, 等.面向珠三角空气污染模拟的虚拟地理环境系统研究[J].武汉大学学报·信息科学版, 2009, 34(6): 636-640 http://ch.whu.edu.cn/article/id/1336

    Xu Bingli, Lin Hui, Zhu Jun, et al. Construction of a Virtual Geographic Environment for Air Pollution Simulation in Pearl River Delta[J]. Geomatics and Information Science of Wuhan University, 2009, 34(6): 636-640 http://ch.whu.edu.cn/article/id/1336
    [5] 常晓猛, 乐阳, 李清泉, 等.利用位置的虚拟社交网络地理骨干网提取[J].武汉大学学报·信息科学版, 2014, 39(6): 706-710 doi:  10.13203/j.whugis20140105

    Chang Xiaomeng, Yue Yang, Li Qingquan, et al. Extracting the Geographic Backbone of Location-based Social Network[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6): 706-710 doi:  10.13203/j.whugis20140105
    [6] 李锋, 万刚, 蒋秉川, 等.虚拟地理环境时空建模及其作战计划推演应用[J].测绘学报, 2018, 47(8):1 072-1 079 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb201808007

    Li Feng, Wan Gang, Jiang Bingchuan, et al. Spatio-Temporal Modeling of Virtual Geographical Environment and Its Application to the Deduction of Battle Plans[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(8):1 072-1 079 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb201808007
    [7] Sahr K, White D, Kimerling A J. Geodesic Discrete Global Grid Systems[J]. Cartography and Geographic Information Science, 2003, 30(2):121-134 doi:  10.1559/152304003100011090
    [8] 赵学胜, 贲进, 孙文彬, 等.地球剖分格网研究进展综述[J].测绘学报, 2016, 45(z1):1-14 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb2016z1004

    Zhao Xuesheng, Ben Jin, Sun Wenbin, et al. Review of the Research Progress of Earth Grid[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(z1):1-14 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb2016z1004
    [9] Guan X, Bo C, Li Z, et al. ST-hash: An Efficient Spatiotemporal Index for Massive Trajectory Data in a NoSQL Database[C]. 25th International Conference on Geoinformatics, Buffalo, New York, USA, 2017
    [10] Qian C, Yi C, Cheng C, et al. GeoSOT-Based Spatiotemporal Index of Massive Trajectory Data[J]. ISPRS International Journal of Geo-Information, 2019, 8(6): 284-292 doi:  10.3390/ijgi8060284
    [11] Samet H. Foundations of Multidimensional and Metric Data Structures[M]. San Francisco :Morgan Kaufmann, 2006
    [12] Faloutsos C. Multiattribute Hashing Using Gray Codes[C]. ACM Sigmod International Conference on Management of Data, Washington D C, USA, 1986
    [13] 赵学胜, 王磊, 王洪彬, 等.全球离散格网的建模方法及基本问题[J].地理与地理信息科学, 2012, 28(1):29-34 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dlxygtyj201201006

    Zhao Xuesheng, Wang Lei, Wang Hongbin, et al. Modeling Methods and Basic Problems of Global Discrete Grid[J]. Geography and Geographic Information Science, 2012, 28(1):29-34 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dlxygtyj201201006
    [14] 童晓冲, 王嵘, 王林, 等.一种有效的多尺度时间段剖分方法与整数编码计算[J].测绘学报, 2016, 45(b12):66-76 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb2016z1011

    Tong Xiaochong, Wang Rong, Wang Lin, et al. An Effective Multi-Scale Time Division Method and Integer Coding Calculation[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(b12):66-76 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb2016z1011
    [15] Moon B, Jagadish H V, Faloutsos C, et al. Analysis of the Clustering Properties of the Hilbert Space-Filling Curve[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1):124-141 doi:  10.1109/69.908985
    [16] Butz A R.Convergence with Hilbert's Space Filling Curve[J].Journal of Computer and System Sciences, 1969, 3(2):128-146 doi:  10.1016/S0022-0000(69)80010-3
    [17] Faloutsos C, Roseman S. Fractals for Secondary Key Retrieval[C]. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Philadelphia, Pennsylvania, USA, 1989
    [18] Peano G. Sur Une Courbe, Qui Remplit Toute Une Aire Plane[J]. Mathematische Annalen, 1890, 36(1): 157-160 doi:  10.1007/BF01199438
    [19] Li C, Feng Y. Algorithm for Analyzing N-Dimensional Hilbert Curve[C].International Conference on Advances in Web-Age Information Management, Hangzhou, China, 2005
    [20] Guan X, Van O P, Cheng B. A Parallel N-dimensional Space-Filling Curve Library and Its Application in Massive Point Cloud Management[J]. ISPRS International Journal of Geo-Information, 2018, 7(8): 327-333 doi:  10.3390/ijgi7080327
  • 加载中
图(7) / 表(4)
计量
  • 文章访问数:  69
  • HTML全文浏览量:  23
  • PDF下载量:  19
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-04-07
  • 刊出日期:  2020-09-05

虚拟战场环境时空数据的Hilbert码索引方法

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

    国防科技项目基金 3601015

    国家自然科学基金 41401465

    国家自然科学基金 41371384

    作者简介:

    吴宇豪,硕士生,主要从事全球离散网格研究。514536575@qq.com

    通讯作者: 曹雪峰,博士,副教授。CAO_Xue_Feng@163.com
  • 中图分类号: P208

摘要: 在虚拟战场环境中,时空数据的高效组织是动态描述战场关键要素、实时分析军事行动计划的前提。首先对经度、纬度、时间进行同步层次嵌套细分来构建规则的多分辨率时空网格,然后基于Hilbert曲线设计时空格元编码,进而根据虚拟战场环境时空数据与时空格元Hilbert码的对应关系,提出一种基于Hilbert码的时空数据索引方法。在此基础上设计实验, 比较格元编码的时空邻近性、索引构建效率以及查询效率。结果表明,Hilbert码方法在邻近性上优于Morton码,索引构建速度满足大规模时空数据处理需要,且查询效率优于直接基于经度、纬度、时间查询和基于Morton码查询的方法,可作为虚拟战场中作战计划推演、战场环境要素可视化与分析等时空操作的基础。

English Abstract

吴宇豪, 曹雪峰. 虚拟战场环境时空数据的Hilbert码索引方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(9): 1403-1411. doi: 10.13203/j.whugis20190394
引用本文: 吴宇豪, 曹雪峰. 虚拟战场环境时空数据的Hilbert码索引方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(9): 1403-1411. doi: 10.13203/j.whugis20190394
WU Yuhao, CAO Xuefeng. Hilbert Code Index Method for Spatiotemporal Data of Virtual Battlefield Environment[J]. Geomatics and Information Science of Wuhan University, 2020, 45(9): 1403-1411. doi: 10.13203/j.whugis20190394
Citation: WU Yuhao, CAO Xuefeng. Hilbert Code Index Method for Spatiotemporal Data of Virtual Battlefield Environment[J]. Geomatics and Information Science of Wuhan University, 2020, 45(9): 1403-1411. doi: 10.13203/j.whugis20190394
  • 虚拟地理环境是现实地理环境在计算机中的逼真模拟和数字化表达[1],是研究“人地关系”和大规模复杂性地理问题的虚拟实验室[2],是实现多角色协同研判地学问题的科学工具[3],在环境保护[4]、道路交通[5]、军事计划[6]等领域得到广泛应用。在军事研究中,虚拟地理环境又演变为虚拟战场环境,在战场环境可视化、作战计划推演中发挥重要作用。

    时空数据是描述动态战场环境和作战行动的基础,虚拟战场环境中时空数据的高效组织是战场环境可视化表达和作战计划量化推演的前提。现有的虚拟战场环境系统中,常采用固定分辨率的网格作为时空数据组织的基础,难以满足信息化作战下多军兵种联合作战对战场多维度、多尺度仿真建模的需求。近年来,随着全球离散网格技术的逐步成熟,基于全球离散网格的虚拟战场环境数据组织越来越成为人们的关注点。全球离散网格是基于(椭)球面的一种可以无限细分但又不改变形状的地球拟合网格,当细分到一定程度时,可以达到模拟地球的目的[7]。网格剖分结果具有唯一性、确定性,剖分得到的每一个格元都有规则的唯一编码,从而构成了一种层次嵌套、多分辨率、统一的空间结构。作为一种新兴的非欧氏几何的空间数据组织方式,全球离散网格已经被应用于解决许多全球范围的空间问题[8]

    然而,目前的全球离散网格主要是对全球空间进行剖分,能描述战场的一个瞬时状态,但不能有效满足虚拟战场环境时空数据动态组织和管理的需要[6]。为有效实现对虚拟战场时间信息的描述,还需要对时间进行剖分编码。为达到这一目的,已有部分学者尝试对时间与空间进行同时剖分组织[9-10]。这些模型采用构造较为简单的Z曲线进行网格填充,设计相应的Morton码索引。因Z曲线自身存在跳跃现象问题,使得该Morton码的连续性不强[11],空间查询的效率提高有限[12]。且这类时空剖分模型的时间剖分结果中存在大量零碎时间单元,难以与现实作战指挥常用时间单位对应,在数据操作处理中效率较差。

    针对上述问题,本文利用虚拟战场环境时空数据,在全球离散网格上进一步引入时间维度构建嵌套剖分、多分辨率规则的时空网格,并设计基于Hilbert曲线的时空编码索引方法,实现时空数据的有效索引与高效查询,进而为虚拟地理环境中作战计划推演、战场环境要素可视化提供时空操作基础框架。

    • 按照剖分模式分类,全球离散网格可分为经纬度网格、正多面体网格以及自适应网格[13]3类。其中,正多面体网格使用了复杂的投影变换,空间坐标变换较为繁琐,网格单元边界与地理坐标网基本不一致,与现有的空间环境数据采集输出格式相差较大,所需的数据转化工作量较大;自适应网格的划分规则不存在多尺度特性,很难进行多尺度海量数据的关联和操作。因此,本文以经纬度球面网格为基础,通过对时间维度进行同步剖分建立全球范围的时空网格。

    • 通常来说,整数形式的时间单元更有益于时空数据的组织[14]。现有的时间剖分研究通常直接对时间维进行剖分,但在作战指挥常用时间单位(年、月、日、时、分、秒等)进制基础上,直接剖分时间维会出现大量非整数的零碎时间单元。如文献[10]中直接对时间维度进行循环二分,在第3次剖分之后就出现了非整月的时间片段,最终得到的时间剖分单元尺寸很难与现实时间进行对应。从符合作战指挥使用习惯与便捷数据处理角度出发,以剖分得到的时间单元尽量为整数单元为目标,本文参照文献[14]中采用的时间虚拟扩展方法,将1 a扩展为16个月,1月扩展为32 d,1 d扩展为32 h,1 h扩展为64 min,1 min扩展为64 s,保证了时间维度在多次二分剖分后得到的时间单元仍为整数单元,符合作战指挥中时间单位使用习惯,且有利于提高时间信息处理的效率。

      与单向递增的时间维度不同,现实空间中的经纬度分为西经、东经、南纬、北纬等区域,在数学计算过程中需要添加正负号加以区分,存在双向变化的情况,不利于与时间维度进行整合。为保持时空范围的单调递增性质,对现实空间中的经纬度进行扩展,定义纬度λ ∈ (0°,180°),即将原地理纬度值加上90°;定义经度φ ∈ (0°,360°),即将原经度值加上180°。

      通过时空维度扩展,本文采用八叉剖分方法对时空域进行剖分(如图 1所示),其层级剖分过程如下:

      图  1  时空网格

      Figure 1.  Spatiotemporal Grid

      1)第0层仅有1个初始时空格元,其范围为经过处理的经度φ ∈ (0°,360°),纬度λ ∈ (0°,180°)以及经过虚拟扩展的时间维t ∈ (0月,16月)。

      2)第1层网格由第0层网格的八叉剖分得到,即分别对3个维度再进行二等分,最终得到8个子格元,其分辨率为(180°,90°,8月)。

      3)第2层网格由第1层网格递归八叉剖分得到,最终得到64个子格元,其分辨率为(90°,45°,4月)。由于在时间维度上进行了扩展,该层级的64个子格元中含有16个不具有现实意义的虚拟格元,即在现实数据生产中并不会出现落入虚拟格元中的数据,为加快网格剖分的速率,虚拟网格不再进行递归剖分。

      4)继续按上述步骤递归剖分,直至达到所需分辨率网格。

    • 空间填充曲线是一种能够通过递归覆盖指定区域的一维曲线[15]。常用的空间填充曲线有Hilbert曲线、Peano曲线、Sierpinski曲线和Morton曲线等。使用空间填充曲线建立剖分编码的基本思路是:按照某种规则将n维空间规则划分为无缝无叠的超立方体网格单元(称为格元),再以一维曲线不遗漏、不交叉地穿行所有格元,实现n维空间Rn与一维空间R1的一一映射,格元在一维曲线上的排列次序即为其编码[8]。大量研究通过实验验证了Hilbert曲线可以获得最佳的聚类效果[16-17]。因此,本文使用Hilbert曲线对时空网格进行填充,设计一种时空耦合的一维Hilbert码。

      Hilbert曲线属于Peano曲线族[18],最早由意大利数学家Peano提出,具有自相似性、递归性等特性。三维Hilbert曲线可实现三维空间至一维空间的一一映射,其对边长为T的立方体空间作嵌套八叉剖分,第一次剖分得到8个子格元,经过m次剖分后得到8m个个子格元,每个子格元边长为T/2mm层级子格元对应m阶曲线。

      将三维m阶Hilbert曲线记作Hm3,以三维一阶Hilbert曲线H13为例,其递归生成三维二阶Hilbert曲线H23的过程可以由一系列坐标变换指令组成。其中,坐标变换由两种形式组成,分别定义为交换“↔”与求反“'”。在图 2(a)中,本文中待剖分的时空范围是由经度φ、纬度λ、时间t构成的三维数学空间,图 2(b)表示将tλ进行交换的结果,图 2(c)φ求反的结果。

      图  2  Hilbert曲线及其编码示例

      Figure 2.  Hilbert Curve and Its Encoding Examples

      将曲线H13经过坐标变换G (i)(i = 0,1,2…7)后得到的结果记为H13 (i),H23曲线由8个H13 (i)首尾相连构成,如图 2(d)所示。其中,各个位置上的坐标变换G (i)形式如表 1所示,将G ∈ {G (0),G (1),G (2)…G (7)}称为三维Hilbert曲线的基因列表[19]

      表 1  三维Hilbert曲线基因列表

      Table 1.  List of 3D Hilbert Curve Genes

      坐标变换 交换 求反
      G (0) tφ -
      G (1) λφ -
      G (2) - -
      G (3) tφ t′, φ
      G (4) tφ -
      G (5) - -
      G (6) λφ λ′, φ
      G (7) tφ t′, φ

      根据Hilbert的递归性与自相似性质,将8个H23分别作坐标变换后得到的H23 (i)首尾相连即可得到H33,以此类推即可获得任意层级的Hilbert曲线。

      H13曲线对1层级的8个格元进行填充,按每个格元的填充顺序分配一个标识码ε1,[∙]1表示层级为1。H13曲线对2层级的64个格元进行填充,每个格元的标识由两部分衔接组成,第1部分为该格元所在的1层级格元标识码ε1,第2部分为其在第2层级格元中的细分码ε2,即h2 = ε1ε2(⊕表示左移一位后相加),如图 2(d)所示。

      结合Hilbert曲线的递归性、连续性以及单调性,可以推出Hm3曲线填充的8m个格元均可由一个m位八进制标识码hm = ε1ε2⊕…⊕εm标识。对于给定的时空格元,可以先求解其在每一层中的细分码,然后将各层级细分码进行拼接得到最终的Hilbert曲线编码。

      针对一组三维坐标为(φλt)的虚拟战场环境时空数据,其落入的格元Hilbert码即为数据的Hilbert码。时空网格中一个格元每一层级的细分码可通过其在每一次剖分中的位置进行判定。使用rφ ∈ {0,1},rλ ∈ {0,1},rt ∈ {0,1}标识1个格元1次剖分后的子格元位置,0、1分别代表某一维度的左右子段,(rφrλrt)与细分码的映射关系如表 2所示,映射关系f实际即为H13曲线上格元的填充顺序。

      表 2  细分码的映射关系f

      Table 2.  Encoding Mapping Relationship f

      (rφ, rλ, rt) 细分码(rφ, rλ, rt)
      (0, 0, 0) 0
      (0, 0, 1) 1
      (1, 0, 1) 2
      (1, 0, 0) 3
      (1, 0, 0) 3
      (1, 1, 0) 4
      (1, 1, 1) 5
      (0, 1, 1) 6
      (0, 1, 0) 7

      计算一条位于(φλt)处的虚拟战场环境时空数据所对应阶Hilbert码的具体步骤如下:

      1)令循环变量n = m。根据式(1)判断(φλt)在每层剖分中所处的子格元:

      $$ \left\{{\begin{array}{*{20}{c}} {{r_\varphi} = \left( {\varphi \& \left( {{2^{n - 1}} \times 360} \right)} \right) > 0}\\ {{r_\lambda} = \left( {\lambda \& \left( {{2^{n - 1}} \times 180} \right)} \right) > 0}\\ {{r_t} = \left( {t\& \left( {{2^{n - 1}} \times 16} \right)} \right) > 0} \end{array}} \right. $$ (1)

      2)由映射关系f计算细分码,如式(2)所示:

      $$ {\varepsilon ^{m - n + 1}} \leftarrow f\left( {{r_\varphi}, {r_\lambda}, {\rm{}}{r_t}} \right) $$ (2)

      3)将细分码εm - n + 1 衔接至上一层级Hilbert码hm - n + 1

      4)对φλt 3个维度作坐标变换。

      5)循环变量n减1。若n ≠ 1,转至步骤1);否则输出Hilbert码hm,算法结束。

      本文最终得到的时空格元Hilbert码具有3个主要特点:①全球时空唯一性。本文时空网格中的所有格元有且仅有一个Hilbert码与之对应。②层次性。Hilbert码内嵌不同层级格元之间的关联或从属关系,能体现格元的递归剖分结构、嵌套关系与继承性以及时空的多尺度特性。一个格元Hilbert码包含其各层级父格元的Hilbert信息,即m层级格元的Hilbert码继承了从第1级至第(m - 1)级的层级信息。③一维性。采用降维处理,以一维的Hilbert码来表示三维的时空。

    • 一条原始虚拟战场环境时空数据落入的格元Hilbert码即为数据的Hilbert码。因此虚拟战场环境数据集中的所有数据,可按照以下算法步骤计算得到一个唯一对应的Hilbert码,从而构建Hilbert码至时空数据的对应关系:

      1)将全球时空域初始化为根格元,设定其层级为0,设定循环变量n = 1。将虚拟战场环境数据集P内所有数据加入至根格元。

      2)剖分生成第n层级格元,计算所有时空数据的第n阶Hilbert码,添加入对应的第n层级格元中。

      3)若n = m,停止剖分,索引构建完毕;否则,转至步骤2)继续进行格元剖分。

      所有时空数据Hilbert码计算完毕后,一个Hilbert码对应于多条时空数据,而一条数据对应唯一的Hilbert码。将Hilbert码与时空数据之间的对应关系存放到关系型数据库中,构建如图 3所示的索引框架。

      图  3  Hilbert码索引框架

      Figure 3.  Hilbert Code Indexing Framework

      本文Hilbert码索引框架主要分为查询转换与存储管理两大模块。作业员通过查询转换模块将查询需求转换成Hilbert码。存储管理模块主要用于时空数据集的存储、时空数据Hilbert码索引构建以及利用Hilbert码对时空数据进行索引。当有新的数据加入时,首先需要计算数据的Hilbert码,然后将数据插入数据库中。而当需要删除一条数据时,首先计算数据对应的Hilbert码,然后在该Hilbert码对应的数据集合中删除该条数据。

    • 虚拟战场环境时空数据查询以空间查询区域和时间间隔作为输入,目标是筛选出指定查询范围内的所有数据,例如,输入的查询条件为$\left({\begin{array}{*{20}{c}} {{\rm{min}}\varphi, {\rm{min}}\lambda, {\rm{min}}t,}\\ {{\rm{max}}\varphi, {\rm{max}}\lambda, {\rm{max}}t} \end{array}} \right)$,则查找所有在(min i,max i)(i=的点:将查询条件看作一个三维空间中的矩形框,其起始与终止角点分别为PminPmax,如图 4中灰色矩形框为查询范围。

      图  4  查询范围至Hilbert码转换

      Figure 4.  Query Range to Hilbert Code Conversion

      依据本文的虚拟战场环境Hilbert码索引,设计相应的数据查询过程,步骤如下:(1)将查询范围转换为Hilbert码。(2)将Hilbert码作为数据库SQL查询语句中的条件,索引得到对应的数据后,再次进行细查询。查询过程中,将格元分为两大类:第1类是被完全包含在查询范围内的格元,如图 4中Hilbert码为{00~07,70~77}的格元。第2类是部分与查询范围相交的格元,如图 4中Hilbert码为{30~31,36~41,46~47}的格元。对于完全包含在查询范围内的格元,由其几何关系可知, 所有在该类格元内的数据均在查询范围内,因此该类格元内的数据不需要参与细筛选过程,可直接提取。对于部分与查询范围相交的格元,因为无法判定其中的所有数据均在查询范围内,所以需要进行细筛选步骤,即将其中所有数据进行式(1)计算,筛选出符合式(1)的数据。由此所得数据即为查询范围内的所有数据。

      使用对经度、纬度、时间等3个维度分别建立索引的平表查询方法时,在没有任何查询优化的情况下,需要对全表进行遍历计算筛选。而利用本文建立的Hilbert码索引进行查询,无需进行全表遍历计算,对于被完全包含在查询范围内的格元数据可直接提取,只需对部分与查询范围相交的格元内数据进行计算,计算次数较平表查询方法更少,起到优化查询效率的效果。

    • 为了验证本文所提Hilbert码索引方法的性能,将本文Hilbert码索引方法与Z-Morton码索引方法和经纬度-时间直接查询方法在相同数据集、相同测试环境下进行比较。本文实验硬件环境为CPU IntelCorei7-7700 K(双核4.2 GHz),内存64 GB,硬盘7 200转/min;软件环境为Visual Studio 2015,Release版本,x64,C++,MySQL数据库。实验数据集为虚拟战场环境中某项作战计划推演所涉及的机动目标轨迹数据,约150万条数据,每条数据中包含当前机动目标在t时刻时的经纬度坐标以及其他属性值。实验数据集中时间跨度为23 h,经度跨度为0.09°,纬度跨度为0.09°。

    • 填充曲线编码的最理想目标是保持时空数据和编码的时空邻近性,即时间和空间上相近的数据在编码索引上也是相近的,编码上相近的数据在时间先后和空间位置上也是相近的。对时空数据的各种查询、检索等操作通常需要涉及大量数据点,时空数据和编码良好的邻近性使这些数据点分布在较少的若干个曲线分段上,由于曲线分段的数量远远少于数据点的数量,使数据访问强度大大降低,对于提高数据操作性能作用显著。因此,邻近性是体现编码索引好坏的重要指标。

      时空邻近性可以通过平均最大邻近距离表示[17],其计算方式如下:针对编码及其对应格元g,给定编码距离(两个编码的数值之差的绝对值)半径R,计算所有与编码距离小于R的编码所对应的格元g′与g之间的曼哈顿距离,记录其最大值作为编码在code半径R内的最大邻近距离。计算层级内所有编码的最大邻近距离,求取其平均值即为平均最大邻近距离。平均最大邻近距离越小,则表明编码的邻近性越高,时空连续性越好。为对比本文Hilbert码方法与现有Morton码方法[9-10]以及经纬度-时间直接编码的时空邻近性,分别计算了这3种编码在层级m下的平均最大邻近距离,其中编码半径2m - 1

      表 3统计了1~5层级下,本文Hilbert码、Morton码以及经纬度-时间直接编码的平均最大邻近距离,图 5统计分析了表 3的结果。结合表 3图 5可知,随着层级的增加,3种编码方法的平均最大邻近距离均逐步增大;相同层级下,经纬度-时间直接编码的平均最大邻近距离最大,Morton码次之,本文Hilbert码最小,证明了本文Hilbert码的邻近性最优,能够保持更好的时空连续性。

      表 3  平均最大邻近距离

      Table 3.  Average Maximum Neighbor Distance

      层级m 编码半径 平均最大邻近距离
      Hilbert码 Morton码 经纬度-时间直接编码
      1 1 1.00 2.00 2.00
      2 2 2.00 3.31 4.28
      3 4 3.27 5.10 9.15
      4 8 4.35 7.03 18.43
      5 16 5.85 9.32 38.81

      图  5  平均最大邻近距离对比

      Figure 5.  Comparison of Average Maximum Neighbor

      Distance

    • 为对比本文编码与Morton编码索引的构建效率,针对数据集内30万、60万、90万、120万、150万条时空轨迹数据,依照本文Hilbert码、Morton码方法在各层级下生成编码。记录两种编码方法的生成时间,验证对比使用两种编码构建数据索引的代价。

      表 4统计了两种编码方法构建索引的部分层级时间信息。图 6统计分析了表 4中的信息,其中图 6(a)表示在60万条数据量下不同层级格元编码索引构建时间对比;图 6(b)表示在24层级下,不同数据量编码索引构建的总时间。

      表 4  编码索引构建时间/s

      Table 4.  Encoding Index Build Time/s

      层级 编码类型 数据量
      30万 60万 90万 120万 150万
      6 Hilbert 0.74 1.23 1.85 2.70 3.15
      Morton 0.61 1.21 2.08 2.52 3.12
      12 Hilbert 1.05 2.04 3.02 4.24 5.15
      Morton 0.98 1.98 2.95 4.06 4.97
      18 Hilbert 1.38 2.78 4.20 5.73 6.96
      Morton 1.31 2.63 3.99 5.56 6.62
      24 Hilbert 1.74 3.49 5.25 7.47 8.76
      Morton 1.64 3.29 4.95 6.84 8.31

      图  6  编码索引构建时间对比

      Figure 6.  Comparison of Coding Index Construction Time

      综合分析表 4图 6可以看出,在不同层级下,本文Hilbert码索引构建时间要略慢于Morton码(见图 6(a)),其原因在于,本文采用的Hilbert曲线相对于Morton曲线的构造复杂度更高,所需的编码计算时间更长。此外,随着格元层级的递增,两种方法构建编码的时间也随之增加。分析其原因是,随着层级的增加,剖分网格的分辨率提高,所需剖分的次数增多,使得编码索引构建耗时增加。在数据量增加的情况下,编码索引的构建时间也会随着增加(见图 6(b)),说明两种编码索引构建时间与数据量正相关。计算每条数据构建索引的平均时间,在层级24下,本文Hilbert码索引每条数据耗时约5.84 μs,Morton码索引每条数据耗时约5.55 μs,两种编码索引的耗时均小于6.0 μs,且平均耗时差距为0.3 μs,在数据操作中编码索引构建代价可以忽略不计。

    • 针对90万条时空轨迹数据,分别采用本文Hilbert码、Morton码以及经纬度-时间直接编码的方法构建数据索引。在此基础上,将时空轨迹数据及其编码的对应关系保存到MySQL数据库中,并对编码建立B-tree索引。设计实验对比3种索引方法的查询效率,设置不同范围的查询窗口如下:空间范围分别为0.02° × 0.02°、0.04° × 0.04°、0.06° × 0.06°、0.08° × 0.08°,时间范围为。在第16层级下,按照不同范围的查询窗口进行随机查询120~200 min,每种查询分别重复查询1 000次,计算3种方式的平均查询时间,其结果如图 7所示。

      图  7  数据查询时间对比

      Figure 7.  Comparison of Data Query Time

      分析图 7可知,本文Hilbert码索引的查询效率优于Morton码索引方法以及经纬度-时间直接查询方法。相较于经纬度-时间直接查询方法,由于本文Hilbert码将由经度、纬度以及时间标识的三维数据编码为一维的Hilbert码,实现了数据的降维处理,在查询时只需对相应Hilbert码索引的数据进行筛选,计算次数较经纬度-时间直接查询方法更少,效率有所提高。相较于Morton码索引,本文所采用的Hilbert码方法较Morton码方法的时空邻近性更优,查询范围对应的Hilbert码的连续性更高,数据分布在更少的曲线段上,查询时的数据访问强度更低,效率更高。

      对比不同查询范围的查询结果,在查询范围较小时,本文Hilbert码以及Morton码对比经纬度-时间直接查询方法的效率提升更加明显。但是,随着查询范围的扩大,本文Hilbert码以及Morton码所需的查询时间逐步接近经纬度-时间直接查询方法,分析其原因如下:(1)随着查询范围扩大,数据分布的曲线段数增加,导致在SQL查询语句中WHERE的条件增多且变得更加零碎,使得SQL语句的执行效率较低。优化解决该问题的有效方法是合并间隔较小的曲线段[20],使得曲线段数量减小,但是本文为了直接对比Hilbert码与其余方法的查询效率,并未在实验过程中进行优化。(2)随着查询范围扩大,通过曲线编码索引出的数据与原始数据集大小区别不大,所需计算的次数相当,使得查询效率与经纬度-时间直接查询方法较为接近。

    • 针对虚拟战场环境时空数据组织需求,本文设计了一种基于Hilbert曲线的虚拟战场环境时空数据编码索引方法,并从时空剖分方法、编码设计以及索引结构方面进行了详细的叙述。为验证本文方法的性能,设计了针对编码邻近性、索引构建效率以及数据查询效率等方面的对比实验。由实验结果可以看出,在编码的邻近性方面,本文编码要优于现有的Morton码,能够以更好的时空连续性组织时空数据。相比于经纬度-时间直接编码方法和Morton码方法,本文Hilbert码的数据查询速率更快。在下一步工作中,将考虑时空数据分布不均匀,除了时间和空间信息还有更丰富的属性信息等情况,寻求更有针对性、更高效的虚拟战场环境时空数据索引方法。

参考文献 (20)

目录

    /

    返回文章
    返回