Research On Parallel Methods Of Spatial Analysis In Distributed Environment

High Performance Computing (HPC) impacts on research, business and production seriously in the past years as a result of repadly development in Web. Geographic Information System (GIS), as a interdiscipline of geoscience and computer science, is motivated by HPC from its capacity of mass data processing. Nevertheless, applying HPC in GIS is confined to spatial data managements and spatial queries. Spatial analysis, the core function of GIS, is seldom studied in HPC plantform with parallel computing. Owing to the variety and complicacy, establishing a spatial analysis platform in distributed environment with parallel computing becomes an important research direction.This thesis focus on parallel methods of spatial analysis in distributed environment. The parallel algorithms of spatial buffer analysis, k-means clustering analysis and shortest path analysis are promoted. And then the improvement method of the three kinds of spatial analysis operations based on MPI+OpenMP parallel programming environment is discussed. Finally, a experiment of spatial analysis platform is revealed. This thesis includes:1) The related theory of parallel computing, parallel programming and distributed spatial database are studied. Parallel computing theory in the aspects of model, classification, algorithm design and evaluation is intrudeced. And the parallel programming environment based on MPI+OpenMP technology is revealed, which both benefits form message passing and shared storage. According to expound distributed spatial indexing technology, spatial data sharding and database cluster technology, a distributed spatial database technique is studies. Then proposes a distributed computing integration model (DSDB/DSDP model) is proposed.2) Three types of parallel spatial analysis algorithms, spatial buffer analysis, shortest path searching and k-means clustering are promoted base on the parallel programming environment and DSDB/DSDP model. A message passing model applies in spatial buffer analysis and shortest path searching, owing to the feasibility of data partitioning. Towards the problem of parallelization in Dijkstra algorithm, a improved shortest path searching method is presented, which assumed queues instead of stacks to record pending searching. The experimental results reveal the high efficiency the algorithms in speedup rate of parallel spatial analysis.3) Data access, load balancing and memory management impact on the efficiency of parallel computing seriously. To improve the efficiency of parallel spatial analysis, three types of optimization method for these aspects are studied. In order to accelerate the spatial data access and reduce the repeat ratio, a novel spatial index, VoMR-tree, is promoted. Based on the traverse with the information of nearest neighbors, the process of spatial buffer analysis and k-means clustering get better results. During a load balancing improvements, k-means clustering process benefits from static load balancing method, and the spatial buffer analysis from dynamic one. Then, two memory management methods, medium-sized method and contention-free method, is applied in the three types of spatial analysis, so as to solve the limited memory problems. The experimental results show that the three types of optimization methods improve the efficiency obviously.4) According to the optimization methods for distributed spatial database environment and the parallel algorithms, a demo system for distributed parallel spatial analysis is designed and implemented. By increasing the number of distributed nodes, the speedup, throughput and parallel efficiency is surveyed. Experimental results show that a distributed process and multi-thread processing efficiently process the different particle size tasks, and make full use of the advantages of both MPI and OpenMP environments.