Proceedings Article | 29 December 2008
KEYWORDS: Databases, Geographic information systems, Distributed computing, Computer networks, Parallel processing, Parallel computing, Data processing, Computing systems, Binary data, Data storage servers
Computation Grids enable the coordinated sharing of large-scale distributed heterogeneous computing resources that can
be used to solve computationally intensive problems in science, engineering, and commerce. Grid spatial applications are
made possible by high-speed networks and a new generation of Grid middleware that resides between networks and
traditional GIS applications. The integration of the multi-sources and heterogeneous spatial information and the
management of the distributed spatial resources and the sharing and cooperative of the spatial data and Grid services are
the key problems to resolve in the development of the Grid GIS. The performance of the spatial index mechanism is the
key technology of the Grid GIS and spatial database affects the holistic performance of the GIS 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 in the
parallel spatial indexing mechanism. Based on the hash table and dynamic spatial slot, this paper has 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. This paper has constructed a new parallel spatial index that can meet the needs of parallel grid
computing about the magnanimous spatial data in the distributed network. This arithmetic splits space in to multi-slots
by multiplying and reverting and maps these slots to sites in distributed and parallel system. Each sites constructs the
spatial objects in its spatial slot into an R tree. On the basis of this tree structure, the index data was distributed among
multiple nodes in the grid networks by using large node R-tree method. The unbalance during process can be quickly
adjusted by means of a dynamical adjusting algorithm. This tree structure has considered the distributed operation,
reduplication operation transfer operation of spatial index in the grid environment. The design of GSHR-Tree has
ensured the performance of the load balance in the parallel computation. This tree structure is fit for the parallel process
of the spatial information in the distributed network environments. 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 extended dynamic hash code for bit comparison. In GSHR-Tree, a new server is
assigned to the network whenever a split of a full node is required. We describe a more flexible allocation protocol
which copes with a temporary shortage of storage resources. It uses a distributed balanced binary spatial tree that scales
with insertions to potentially any number of storage servers through splits of the overloaded ones. The application
manipulates the GSHR-Tree structure from a node in the grid environment. The node addresses the tree through its
image that the splits can make outdated. This may generate addressing errors, solved by the forwarding among the
servers. In this paper, a spatial index data distribution algorithm that limits the number of servers has been proposed. We
improve the storage utilization at the cost of additional messages. The structure of GSHR-Tree is believed that the
scheme of this grid spatial index should fit the needs of new applications using endlessly larger sets of spatial data. Our
proposal constitutes a flexible storage allocation method for a distributed spatial index. The insertion policy can be tuned
dynamically to cope with periods of storage shortage. In such cases storage balancing should be favored for better space
utilization, at the price of extra message exchanges between servers. This structure makes a compromise in the updating
of the duplicated index and the transformation of the spatial index data. Meeting the needs of the grid computing, GSHRTree
has a flexible structure in order to satisfy new needs in the future. The GSHR-Tree provides the R-tree capabilities
for large spatial datasets stored over interconnected servers. The analysis, including the experiments, confirmed the
efficiency of our design choices. The scheme should fit the needs of new applications of spatial data, using endlessly
larger datasets. Using the system response time of the parallel processing of spatial scope query algorithm as the
performance evaluation factor, According to the result of the simulated the experiments, GSHR-Tree is performed to
prove the reasonable design and the high performance of the indexing structure that the paper presented.
