[1]熊 伟,李瑞清,陈 荦,等.一种基于空间划分树裁剪外包框的空间索引方法[J].郑州大学学报(工学版),2022,43(03):1-7.[doi:10.13705/j.issn.1671-6833.2022.03.016]
　XIONG Wei,LI Ruiqing,CHEN Luo,et al.A Spatial Index Based on Clipping Bounding Box of Space Partitioning Tree[J].Journal of Zhengzhou University (Engineering Science),2022,43(03):1-7.[doi:10.13705/j.issn.1671-6833.2022.03.016]

点击复制

一种基于空间划分树裁剪外包框的空间索引方法()

分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:

43

期数:

2022年03期

页码:

1-7

栏目:

出版日期:

2022-04-10

文章信息/Info

Title:

A Spatial Index Based on Clipping Bounding Box of Space Partitioning Tree

作者:

熊 伟; 李瑞清; 陈 荦; 曹竞之; 资文杰

国防科技大学电子科学学院；

Author(s):

XIONG Wei;  LI Ruiqing;  CHEN Luo;  CAO Jingzhi;  ZI Wenjie

School of Electronic Science, National University of Defense Technology, Changsha 410073, China

关键词:

地理信息; 空间查询; 时空索引; R树; 裁剪外包框

Keywords:

geographic information;  spatial query;  spatial index;  R tree;  clipping bounding box

分类号:

TP392

DOI:

10.13705/j.issn.1671-6833.2022.03.016

文献标志码:

A

摘要:

空间数据库中,基于 R 树的时空索引使用最小外包框对时空数据进行近似以提高查询效率,通过裁剪外包框的冗余空间可以进一步提高索引的效率。 针对这一问题,提出了一种基于 CBB 的改进的时空索引方法。 首先,将优化方法从平面二维拓展到了时空维度中,计算可能的裁剪点,在空间索引中记录外包框中的冗余空间范围,对索引节点外包框的裁剪空间进行优化,减少查询过程中不必要的子节点的计算然后,分析时空维度中查询框与索引节点外包框的相交情况,对查询中后续判断的算法进行研究,避免裁剪过程中冗余的裁剪点比较,优化了基于时空索引进行范围查询的计算过程。 实验结果表明:所提空间索引方法裁剪索引节点外包框大小是 CBB 方法的 3 倍,且减少了 40%的节点计算量,查询耗时降低 了 20%,进 一步提升了 基于空间 划分树 的时空索引的查询性能。

Abstract:

In spatial databases, spatio-temporal indexes based on R tree use minimum bounding box(MBB)to approximate spatio-temporal data to improve query efficiency, and the efficiency of indexing can be further improved by by clipping the bounding box.To address this problem, an improved spatio-temporal indexing method based on CBB was proposed, which firstly extended the method from two dimensions to the spatio-temporal dimension and obtained the possible clipping points by calculation, and recorded these points in the index for optimizing the clipping space of the bounding box of the index nodes, which could reduce the unnecessary child-node search in the query process.Then, the intersection of query box and the MBB of index node was analyzed, and the range query processing algorithm was further optimized, thus avoiding redundant comparison of clipping points in the query process.The experimental results showed that the indexing method could clip the space of the MBB of index nodes three times more than the original method, and could reduce the node computation by 40%, and could reduce the query time by 20%, which further could improve the query performance of spatial division tree-based spatio-temporal index.

常用功能