RESEARCH ON THE DISTRIBUTED PARALLEL SPATIAL INDEXING SCHEMA BASED ON R-TREE
Zhao Yuan-chun, Chengming Li · 2008
As one of the key technologies for improving the efficiency of parallel processing of a huge volume spatial data under the distributed parallel computing environment, the parallel spatial indexing mechanism is discussed in this paper. On the viewpoint of the existing research results, the classical R-tree indexing structure and its variations have the well characteristic for parallel organizing and processing of spatial data, therefore, a new multi-tiers parallel spatial indexing structure based on R-tree (HCMPR-tree, multi-tiers parallel R-tree based on Hilbert spatial filling curve) is presented. Differing from the present parallel spatial indexing structures, the attributes of the parallel computing pattern has been considered adequately, and a high performance parallel spatial data partitioning algorithm (HCSDP, spatial data partitioning algorithm based on the Hilbert spatial filling curve) has been applied in the HCMPR-tree. Based on the theoretical and technical issues of classical methodology of parallel algorithm design, HCMPR-tree has not only a well indexing structure for parallel computing, but it also obtains the high efficiency for load-balance between the different nodes under the distributed parallel computing environment. In the paper, using the system response time of the parallel processing of spatial scope query algorithm as the performance evaluation factor, the availability and the efficiency of HCMPR-tree has been sufficiently proved by implementing parallel processing on the testing spatial datasets.