多维空间索引结构SHG-Tree(英文)  

SHG-Tree: An Efficient Index Structure of Spatial Database

作　　者：刘胤田[1,2] 刘应明[1] 徐开阔[3] 曾涛[4] 唐常杰[3] 

机构地区：[1]四川大学数学学院,成都610065 [2]成都信息工程学院数据库与知识工程实验室,成都610225 [3]四川大学计算机学院,成都610065 [4]天津师范大学计算机与信息工程学院,天津300074

出　　处：《计算机科学与探索》2009年第1期68-90,共23页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金;成都大学信息技术发展基金~~

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]