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

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

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

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.