GSHR-Tree: A Spatial Index Tree Based on Dynamic Spatial Slot and Hash Table in Grid Environments

In order to improve the efficiency of parallel processing of a spatial mass data under the distributed parallel computing grid environment, this paper presents a new grid slot hash parallel spatial index GSHR-Tree structure established with the parallel spatial indexing mechanism. Based on the hash table and dynamic spatial slot, we have improved the structure of the classical parallel R-tree index. The GSHR-Tree index makes full use of the good qualities of R-Tree and hash data structure. A new parallel spatial index is constructed to meet the needs of parallel grid computing about the magnanimous spatial data in the distributed network. This arithmetic splits space into multi-slots by multiplying and reverting and maps these slots to sites in distributed and parallel system. Each site constructs the spatial objects in its spatial slot into an R-tree. On the basis of this tree structure, the index data is distributed among multiple nodes in the grid networks by using large node R-tree method. Instead of spatial object's recursive comparison where original R-tree has been used, the algorithm builds the spatial index by applying binary code operation in which computer runs more efficiently, and extends dynamic hash code for bit comparison, using the system response time of the parallel processing of spatial scope query algorithm as the performance evaluation factor. The result of the simulated the experiments shows GSHR-Tree is performed to prove the reasonable design and the high performance of the indexing structure presented in the paper.