基于十六叉树-多尺度表达Ｒ 树的TGIS 时空数据索引算法

[KTurnura]

本文基于四维十六叉树-多尺度表达R树的时空数据索引算法（4DHMSR），分别实现了对遥感时空影像多属性的索引（多维、多分辨率、时空位置关系、多尺度时空目标）。构建4DHMSR 树时空索引创建算以及动态插入和分裂算法，该方法通过改进MongoDB实现的实例化。

场景需求

多维、多分辨率及多尺度时空数据存储表达与索引处理问题复杂、技术难度大、研究范围广，但从当前研究成果来看，主要从三个方面展开：

1. 第一个方面是如何利用分块或扩展八叉树存储方法对多分辨率空间数据进行组织管理，其中从八叉树存储空间大小角度考虑多分辨率空间数据的表达问题较为普遍“-”，且表达空间数据的结构主要以指针或线性八叉树数据结构为主，但这会造成内存资源消耗大、对地理信息系统的硬件资源要求高，特别是三维八叉树数据结构只能对空间数据进行有效表达，而对于时间上动态变化的增量数据表达问题却无法表达和存储；
2. 第二个方面是如何实现多维空间数据索引方法，其中主要从三维空间R树或扩展 R树来表达多维空间数据K-90，但这类索引方法对于多维时空数据时索引效率较低；
3. 第三个方面是如何实现多尺度空间数据表达、处理与索引问题，其中主要从制图理论、综合算法模型和四叉树索引结构等方法进行研究！-14，但这些方法解决多尺度空间数据时效率较低，无法满足多用户多视角下时态地理数据信息增量索引的需求。因此，如何同时将多维度、多尺度和多分辨率的空间数据与时态数据进行有效融合、统一存储和整体表达，达到 TGIS 中的时空数据动态索引和按需访问，解决当前 TGIS 应用环境中的多源时空数据的动态管控问题具有重要的研究意义。

十六叉树构建方法

十六叉树的编码原理：

十六叉树的编码原理：首先，将重要的目标节点用7为基数来编码，称为定位码，定位码的位数表达了分辨率的大小或目标的划分程度，并且根据定位码来确定搜索目标的坐标位置，称为编码；其次，根据目标对象的坐标位置来确定定位码，称为解码；最后，利用定位码的编解码解算规则，计算出定位码的具体数值。其定

十六叉树的定位码计算规则

1. 给定分辨率，确定坐标系统大小和体元编码的位数
2. 对于整个原始体元编码按照乙字型方向进行编码，其方向与选取的四维坐标有关

原理

十六叉树是在原始八叉树的基础上演化而来的 每个正方体区域，包含固定时间段内所有空间目标的最小边界（纬度，经度，分辨率） 然后时间线为时间戳内容

多尺度表达的R树

多尺度表达的R树（Multi Scale represented RTree, MSR 树）是R树的一种改进形式，MSR 树是N+维（N是空间维数，1是分辦率维度）的R树，基本思想：首先利用R树表达实体对象的重要度因子19将实体对象进行等级划分，并将分辨率较低的视图对象数据删除，且在对象表达过程中引入显示分辨率维，利用MSR 树的深度遍历层次的树型来表达多尺度空间数据的变化分辨率；其次使用 MSR 树的上层树形结构来表达空间实体对象；最后为了使实际地理空间特征与所表达的树形分支结果相符合，需考虑地理空间对象间的关联性，这样采用综合算法来实现多尺度空间数据索引问题130

十六叉树 + 多尺度表达的融合

为了满足时空对象增量数据索引的要求，采用4DHMSR 树构建时空数据多尺度索引和查询方法。4DHIMSR 树数据结构采用嵌套的二级索引组织形式，其中 MR 树为一级索引结构，四维十六叉树为二级数据结构。该嵌套树形结构既可充分利用十六叉树快速收敛和划分特性，也具有 MSR 树在多维空间中的高效检索特性。图3是4DHMSR 树数据结构的组织结构图。

评价指标

测试环境

单节点：windows7 + mongoDB