Abstract: To improve query efficiency of multidimensional spatial database， a new index structure named spatial hypercube grid tree （SHG-Tree） is proposed. By decreasing the occurrence of node split and recombination during insert/delete operations， and avoiding range comparison between query range and candidate entities during query operations， SHG-Tree based index method can efficiently support the common operations over spatial database containing objects with dynamic region. The main contributions include： （1） Proposes two type of SHG-Tree for n-dimensional space. The hierarchical structure of SHG-Tree reflects the region overlapping relationship of hypercube grid units with different granularity. （2） Proposes three linearization strategies to present the bounding rectangle of spatial object as a union of variant granularity hypercube grids. （3） Gives the realization of different spatial query operations based on SHG-Tree. （4） Demonstrates the efficiency of SHG-Tree by extensive experiments. Experiments result shows query operation can be limited into ten milliseconds to ensure the real-time of query.

Key words: spatial index, spatial hypercube grid tree （SHG-Tree）, linearization of spatial object

摘要： R-Tree及其变种的多维索引结构在数据的操作过程中通过对空间的分隔和不断调整将整个空间划分为大小不等的子空间以容纳足够的空间对象，这种方法能有效地实现多维空间对象的索引，但不能避免频繁的节点分裂与重组操作所造成的计算开销，也不能避免对叶子节点中的候选对象进行空间匹配所带来的计算开销。提出了一种能有效解决上述问题的索引结构：SHG-Tree。基于SHG-Tree的索引方法将多维空间划分为不同粒度的格子单元并将这些格子单元通过SHG-Tree按空间包含关系组织为层次树结构，同一层的格子互不相交且空间范围固定。空间对象通过文中提出的线性化方法转换为一系列不同粒度的互不相交的空间格子，进而将对象在其覆盖的格子中注册以实现空间对象至SHG-Tree的映射。查询操作只需将查询条件映射为相应的格子并取出这些格子中的对象作为查询结果。这种索引结构能有效减少节点的分裂和组合带来的计算开销，也解决了传统R-Tree索引中对于叶子节点中的候选对象进行区域匹配的计算开销。基于SHG-Tree的索引结构支持包括相交查询、区域查询、包含查询、top-N查询、k-NN查询等常用的多维查询，实验表明SHG-Tree能在毫秒级实现各种空间查询。

关键词: 空间索引, 空间超立方格子树, 对象线性化