Graph-Based Divide and Conquer Method for Parallelizing Spatial Operations on Vector Data

Abstract

In computer science, dependence analysis determines whether or not it is safe to parallelize statements in programs. In dealing with the data-intensive and computationally intensive spatial operations in processing massive volumes of geometric features, this dependence can be well utilized for exploiting the parallelism. In this paper, we propose a graph-based divide and conquer method for parallelizing spatial operations (GDCMPSO) on vector data. It can represent spatial data dependences in spatial operations through representing the vector features as graph vertices, and their computational dependences as graph edges. By this way, spatial operations can be parallelized in three steps: partitioning the graph into graph components with inter-component edges firstly, simultaneously processing multiple subtasks indicated by the graph components secondly and finally handling remainder tasks denoted by the inter-component edges. To demonstrate how it works, buffer operation and intersection operation under this paradigm are conducted. In a 12-core environment, the two spatial operations both gain obvious performance improvements, and the speedups are more than eight. The testing results suggest that GDCMPSO contributes to a method for parallelizing spatial operations and can greatly improve the computing efficiency on multi-core architectures.

Keywords

• spatial operations
• spatial data dependence
• graph
• divide and conquer method
• computing efficiency