留言板

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

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

一种针对室内疏散的集成Hilbert曲线的R*树空间索引

牛磊 宋宜全 张宏敏 侯绍洋

牛磊, 宋宜全, 张宏敏, 侯绍洋. 一种针对室内疏散的集成Hilbert曲线的R*树空间索引[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1416-1421. doi: 10.13203/j.whugis20160352
引用本文: 牛磊, 宋宜全, 张宏敏, 侯绍洋. 一种针对室内疏散的集成Hilbert曲线的R*树空间索引[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1416-1421. doi: 10.13203/j.whugis20160352
NIU Lei, SONG Yiquan, ZHANG Hongmin, HOU Shaoyang. A Hilbert-Curve-Based R* Tree Index Optimized for Indoor Evacuation[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1416-1421. doi: 10.13203/j.whugis20160352
Citation: NIU Lei, SONG Yiquan, ZHANG Hongmin, HOU Shaoyang. A Hilbert-Curve-Based R* Tree Index Optimized for Indoor Evacuation[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1416-1421. doi: 10.13203/j.whugis20160352

一种针对室内疏散的集成Hilbert曲线的R*树空间索引

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

国家自然科学基金 41771433

国家自然科学基金 41501440

国家自然科学基金 41571387

国家自然科学基金 41701454

河南省高等学校重点科研项目 15A170002

河南省重点科技攻关计划 152102310321

天津市科技计划 15ZCZDSF00390

详细信息
    作者简介:

    牛磊, 博士, 副教授, 主要从事三维信息系统、室内建模和疏散研究。niuneilneo@vip.163.com

  • 中图分类号: P208

A Hilbert-Curve-Based R* Tree Index Optimized for Indoor Evacuation

Funds: 

The National Natural Science Foundation of China 41771433

The National Natural Science Foundation of China 41501440

The National Natural Science Foundation of China 41571387

The National Natural Science Foundation of China 41701454

the Key Research Program of Henan Higher Education 15A170002

the Foundation of Henan Science and Technology 152102310321

the Tianjin Science and Technology Planning Project 15ZCZDSF00390

More Information
    Author Bio:

    NIU Lei, PhD, associate professor, specializes in 3D GIS, indoor modelling and evacuation research. E-mail:niuneilneo@vip.163.com

图(7) / 表(2)
计量
  • 文章访问数:  1014
  • HTML全文浏览量:  61
  • PDF下载量:  262
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-12-04
  • 刊出日期:  2018-09-05

一种针对室内疏散的集成Hilbert曲线的R*树空间索引

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

    国家自然科学基金 41771433

    国家自然科学基金 41501440

    国家自然科学基金 41571387

    国家自然科学基金 41701454

    河南省高等学校重点科研项目 15A170002

    河南省重点科技攻关计划 152102310321

    天津市科技计划 15ZCZDSF00390

    作者简介:

    牛磊, 博士, 副教授, 主要从事三维信息系统、室内建模和疏散研究。niuneilneo@vip.163.com

  • 中图分类号: P208

摘要: 基于位置的服务需要快速查询、插入和删除研究对象,这种需求在室内疏散相关的应用中被进一步加强,因此有必要引入空间索引优化针对室内空间对象的操作效能。在室内紧凑空间环境下,现有的空间索引效率较低,所以将R*树索引和Hilbert曲线相结合,提出了一种新型的集成Hilbert曲线的索引。将这种新型索引和标准R*树索引进行对比,结果表明,新索引能够显著提升多种空间操作效率。

English Abstract

牛磊, 宋宜全, 张宏敏, 侯绍洋. 一种针对室内疏散的集成Hilbert曲线的R*树空间索引[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1416-1421. doi: 10.13203/j.whugis20160352
引用本文: 牛磊, 宋宜全, 张宏敏, 侯绍洋. 一种针对室内疏散的集成Hilbert曲线的R*树空间索引[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1416-1421. doi: 10.13203/j.whugis20160352
NIU Lei, SONG Yiquan, ZHANG Hongmin, HOU Shaoyang. A Hilbert-Curve-Based R* Tree Index Optimized for Indoor Evacuation[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1416-1421. doi: 10.13203/j.whugis20160352
Citation: NIU Lei, SONG Yiquan, ZHANG Hongmin, HOU Shaoyang. A Hilbert-Curve-Based R* Tree Index Optimized for Indoor Evacuation[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1416-1421. doi: 10.13203/j.whugis20160352
  • 室内疏散方案可以指导用户从空间内的一点到达另一点,此类应用离不开位置范围的确定[1-6]。在确定位置范围的过程中引入空间索引,可以减少此过程的时间耗费和降低定位出错的几率[7-11]

    用于优化空间操作的典型索引有四叉树索引、KD树索引和R树索引等[12-16]。这些索引通过减小搜索空间范围达到优化操作性能的目的。在这类索引中,面向对象的R树索引空间操作性能表现较优。不同于四叉树和KD树这些单纯从平衡节点数据量出发的通用索引,R树索引通过生成空间上包裹对象集合的最小外接矩形框来构建索引[17-18]。R树从诞生到现在,衍生出了R+树和R*树等变种。在这些R树变种中,R*树因其对于空间操作的优良性能得到了广泛应用[12, 19-20]

    R*树与标准R树一样,也采用最小外接矩形框来包裹空间对象。但是与标准R树对重叠叶节点的粗糙处理方式不同,R*树对于重叠以及溢出叶节点进行考虑平衡的重新插入,以达到减小外接矩形框的重叠空间范围的目的(图 1)。

    图  1  标准R树和R*树空间索引效果图

    Figure 1.  Diagram of Spatial Classification Results of Classic R Tree and R* Tree

    在使用空间索引的过程中,需要关注的一个关键技术细节是节点的遍历顺序问题。由于对节点的不同遍历方式往往会导致巨大的性能差异,相关研究人员提出了若干空间遍历曲线,以利用它们提高空间操作效率[19, 21]。其中, 以Peano曲线、Moore曲线和Hilbert曲线最为著名[1, 19, 22]。在这些曲线中,Hilbert曲线以其良好的局部相关性和位置编码接近真实坐标的特性被广泛关注(见图 2)[23-25]。局部相关性是指曲线上前后遍历的节点在空间操作中被同时使用的几率;位置编码是指特定空间位置在曲线上利用若干基本方向构成的相对坐标数值(见图 3)。局部相关性好是指在曲线上被顺序遍历的空间对象在空间操作中也有极大几率被同时调用;位置编码无限逼近真实坐标则是指空间遍历曲线上通过无限迭代最终和真实空间坐标拟合的特性。

    图  2  1次、2次、3次和4次迭代的二维Hilbert曲线

    Figure 2.  Graphic Illustration of One Iteration, Two Iterations, Three Iterations and Four Iterations of 2-Dimensional Hilbert Curve

    图  3  二维3次迭代Hilbert曲线遍历空间和编码映射原理

    Figure 3.  Graphic Demonstration of Traversing and Coding for Hilbert Curve in 2-Dimensional Space

    综上所述,本文将R*树对于空间对象聚类的特点和Hilbert曲线高效遍历邻近空间对象的特点融合,得到集成Hilbert曲线的R*树索引, 利用这种索引能够对室内疏散相关的应用进行优化,从而达到提高空间操作效率的目的。

    • 构建集成Hilbert曲线的R*树需要完成Hilbert码的生成、Hilbert码和R*树的集成这两个步骤。前者是为了利用Hilbert曲线对邻近空间对象的优良遍历特性打下基础;后者则是将Hilbert码和R*树进行融合以发挥各自特点的必要步骤。

    • 本文的Hilbert码生成方法的原理来自于文献[21]。该方法的特点是采用自下而上的方式生成Hilbert码,并且在生成编码的过程中不断复用若干基本模板基因,以达到快速生成特定位置对应Hilbert曲线编码的目的。本文的模板基因是指构成特定维度和迭代次数Hilbert曲线的基本空间走向单元。此过程的原理参见图 4图 5图 4中,C3代表最基本的三维Hilbert曲线模板基因,X1$\leftrightarrow $X3是指X1坐标轴和X3坐标轴互换之后的模板基因,X2$\leftrightarrow $X3是指X2坐标轴和X3坐标轴互换之后的模板基因,X1$\leftrightarrow $X3X'1, X'3是指X1坐标轴和X3坐标轴互换,且X1X3坐标各自求反的模板基因,X2$\leftrightarrow $X3X'2, X'3是指X2坐标轴和X3坐标轴互换,且X2X3坐标各自求反的模板基因。图 5则描述了使用1次迭代基因模板生成2次迭代三维Hilbert曲线的过程。表 1展示了1次迭代三维Hilbert曲线编码生成基本模板。

      图  4  三维Hilbert曲线编码生成模板基因展示

      Figure 4.  Diagram of Template for Generating Hilbert Curve Code Gene in 3-Dimensional Space

      图  5  使用1次迭代基因模板生成2次迭代三维Hilbert曲线展示

      Figure 5.  Diagram of Utilizing One Iteration Hilbert Curve to Encode Two Iterations in 3-Dimensional Space

      表 1  利用1次迭代三维Hilbert曲线编码生成基本模板列表

      Table 1.  Template for Generating Hilbert Curve Code in 3-Dimensional Space

      位置 0号点 1号点 2号点 3号点 4号点 5号点 6号点 7号点
      0 000 001 011 010 110 111 101 100
      1 000 100 101 001 011 111 110 010
      2 000 100 110 010 011 111 101 001
      3 101 100 110 111 011 010 000 001
      4 000 001 011 010 110 111 101 100
      5 000 100 110 010 011 111 101 001
      6 011 111 110 010 000 100 101 001
      7 101 100 110 111 011 010 000 001
    • Hilbert码需要和R*树进行深度整合,才能在空间相关操作中体现出引入Hilbert遍历曲线的优势。这就要求在R*树的插入和删除节点相关的操作中引入对于Hilbert码的生成和更新,涉及到插入节点、拆分节点和删除节点3个核心算法。其中,插入节点算法负责将当前空间对象插入合适的叶节点中;拆分节点则是当前节点所容纳的对象数量多于设置上限时,需要将当前节点拆分为多个节点的操作;删除节点则是将所需删除空间对象从R*树中删除。

      以上3个R*树的核心操作中,在引入Hilbert码之后都需要进行适当的修改,其中最为关键的是在插入空间对象时选择节点。该算法描述如下:

      输入:待插入空间对象,涉及的空间节点和内部包含对象。

      输出:插入后的空间节点。

      处理过程:

      1) 检索当前节点的子对象数目,如果该数目小于预设值上限,则继续检索,否则结束;

      2) 如果待插入对象的Hilbert码小于当前节点包含对象的最小Hilbert码,那么将待插入对象插入节点包含对象列表的最前端,结束;

      3) 如果待插入对象的Hilbert码大于当前节点包含对象的最大Hilbert码,那么将待插入对象插入节点包含对象列表的最后端,结束;

      4) 遍历当前节点包含的对象列表,如果发现待插入对象的Hilbert码位于列表里的两个对象的Hilbert码之间,那么将其插入此位置,结束。

    • 实验场景选择的是河南城建学院5号教学楼,该教学楼分为A座、B座和C座3个教学功能区,分别对应该教学楼的实验室区、办公区和教学区。这些功能区通过位于东西两侧的两个长风雨走廊相连。建筑的数据源是平面设计图纸(见图 6)。在图 6中使用1号图框标示的范围是B座东侧楼梯区域,针对该区域的空间对象查询操作模拟应急疏散情况下对于室内人员位置的查询;被3个2号图框所圈定的范围是B座二层的3间办公室,针对该区域的空间对象删除操作则是模拟火灾发生情况下,由于灾害阻挡作用导致的对室内通行空间的删除;被2个3号图框所圈定的范围是B座三层的两间办公室南侧窗户外的邻近空间,针对这两块通行空间的插入是模拟消防人员通过架设云梯的方式新增建筑物邻近通行空间的场景。

      图  6  实验建筑的平面设计图展示

      Figure 6.  Illustration of Experiment Building by 2D Floor Plan

      针对建筑物的空间对象操作实验, 除了以上提到的针对指定范围的空间对象查询、删除和插入,还包括对于完整索引树的遍历。这些空间操作由于单位耗时较短,所以本文展示的实验结果是将其重复10 000次所得的总时间耗费。

    • 图 7展示的是依照Hilbert编码升序遍历R*树的曲线,从中能够看出该树在遍历过程中优先经过邻近空间对象。这种依照Hilbert码组织空间索引的R*树在表 2的数据中将空间操作效能优势进行了充分发挥。从表 2中可以看出, 通过引入Hilbert遍历曲线,在全树遍历过程中,引入Hilbert曲线的R*树相比于普通R*树时间节省了43.34%;在查询特定空间对象的过程中, 时间节省了47.15%;而在删除操作中,时间更是节省了70.91%。但是,引入Hilbert曲线也有副作用:在插入操作中,由于需要进行较为庞杂的空间坐标向Hilbert码的转化,因此引入Hilbert曲线的R*树相比于普通R*树时间耗费增加了70倍。

      图  7  依照Hilbert码排序的实验建筑的R*树遍历曲线展示

      Figure 7.  Demonstration of Traversing Lines Sorted by Hilbert Code for Nodes in R* Tree for Experiment Building

      表 2  引入Hilbert曲线编码对于R*树的10 000次关键空间操作的效果展示表

      Table 2.  Time Cost for Introducing Hilbert Curve to R* Tree on Spatial Operations

      对比项目 Hilbert R*树索引/s R*树索引/s Hilbert引入效果/%
      全树遍历 4.236 207 7.477 665 -43.34
      查询 4.073 165 7.706 982 -47.15
      删除 0.049 924 0.171 622 -70.91
      插入 3.723 421 0.052 240 +7 027.53

      但是不能简单地认为由于引入Hilbert曲线的R*树在插入对象操作上的时间耗费过大,就不适用于室内位置相关的应用。由于在针对室内位置相关的空间应用中,绝大多数操作都是空间位置查询和删除操作,而插入操作一般都是在初始化室内场景的过程中或者是极少数的新增通行空间的场景中(如引入消防云梯这种较为罕见的场景), 所以引入Hilbert曲线的R*树在查询操作上的优势能够弥补其在插入操作上的劣势。此外,针对Hilbert码的生成优化算法也一直在进步,引入Hilbert曲线对于R*树插入操作的负面影响也会得到有效遏制。总体来看,引入Hilbert曲线对于R*树这类空间索引利大于弊。

    • 因为Hilbert曲线具有针对遍历空间对象的良好空间局部性的特点,所以引入该曲线能够提高R*树针对空间邻近对象的相关操作效率,即可以显著提升针对全树的对象遍历、查询和删除操作效率。虽然在引入Hilbert曲线后,由于生成Hilbert码的复杂运算的影响会导致对象插入效率的下降,但是在进行针对Hilbert码的生成优化之后,可以降低这种负面影响。未来的研究方向有两个:

      1) 针对多级索引的Hilbert码动态扩展,可以满足针对更加精确坐标和基本单元扩展的Hilbert编码扩展需求。

      2) 以降低运算复杂度为目的的Hilbert算法的精简和优化,能够在运算时间受限的情况下快速得到可接受精度的Hilbert编码。

参考文献 (25)

目录

    /

    返回文章
    返回