SHG-Tree: An Efficient Index Structure of Spatial Database
Changjie Tang · Jisuanji kexue yu tansuo · 2009
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 ndimensional 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.