Parallel Buffer Generation Algorithm for GIS

Xiaomeng HuangJournal of Geology & Geosciences 2012 · DOI

TL;DR

This paper tackles the growing inefficiency of buffer generation in Geographic Information Systems (GIS) due to massive datasets. They introduce a novel parallel algorithm combining a "points-based load balancing" approach with a "binary union tree" to significantly speed up this crucial GIS function, achieving a 21-fold speedup with 32 processes.

What Problem Does This Paper Address?

Geographic Information Systems (GIS) are increasingly vital for analyzing vast amounts of spatial data. A fundamental operation in GIS is "buffer generation," which creates zones around geographic features (like roads or rivers) at a specified distance. As the scale and precision of geographic data grow, traditional, single-processor methods for buffer generation become a significant bottleneck, leading to unacceptably long processing times. This paper addresses the need for a more efficient, parallelized approach to buffer generation that can handle large-scale datasets without sacrificing precision.

Methods

The authors propose a novel, integrated parallel algorithm for buffer generation. Their approach combines two key innovations:

  • Points-Based Load Balancing: Instead of dividing data by features or geographic regions (which can lead to uneven workloads or redundant computations), they propose distributing tasks based on the number of points within features. This finer-grained approach aims to achieve a more even distribution of computational work across parallel processes. To implement this, they first iterate through the data to map the number of points per feature, then group features to balance the point count across processes.
  • Binary Union Tree: The second critical component addresses the "union operation," where individual buffer zones are merged into a final output. Traditional methods often involve a master process collecting all results and performing a sequential union, which becomes a bottleneck. Their "binary union tree" method allows all processes to participate in the union operation in a hierarchical, parallel manner. This effectively reduces the time complexity of the union operation from O(N) to O(logN), where N is the number of features.

Datasets

The paper describes experiments conducted using a dataset of over 200,000 river features, provided by the Institute of Geographic Sciences and Natural Resources Research (IGSNRR) of the Chinese Academy of Sciences. This dataset was used to evaluate the performance of their proposed algorithm against existing parallel approaches. No new benchmark datasets were introduced.

Key Insights and Ideas

  • The Union Operation is the Real Bottleneck: The experimental analysis clearly shows that the union of buffer zones consumes a disproportionately large amount of time (around 75%) in traditional sequential GIS processing, far more than the buffer generation itself. This insight justifies the focus on optimizing the union step.
  • Fine-Grained Parallelism is Key: Dividing work based on the number of points, rather than coarser units like features or geographic areas, proves to be a more effective strategy for achieving good load balancing in parallel buffer generation.
  • Hierarchical Union for Scalability: The binary union tree elegantly solves the master-process bottleneck in the union phase, enabling better scalability as the number of processes increases.
  • Trade-offs in Load Balancing: The points-based load balancing method introduces a small overhead for initial data iteration, which can make it slightly less efficient than feature-based methods when the number of processes is very low. However, this is quickly overcome as the number of processes grows.

Key Results

The authors compared their proposed algorithm (Algorithm3) against two other parallel approaches (Algorithm1: feature-based load balance with sequential union; Algorithm2: feature-based load balance with binary union tree).

  • Significant Speedup: Algorithm3 achieved a maximum speedup of 21.41 times when using 32 processes, compared to a single-process execution.
  • Improved Efficiency: The efficiency of Algorithm3 was notably higher than the other algorithms, reaching 0.67 with 32 processes.
  • Reduced Execution Time: The execution time for Algorithm3 was reduced from 395.51 seconds (single process) to 18.47 seconds (32 processes).
  • Scalability: The algorithm demonstrated good scalability, with efficiency generally maintained or even improving as the number of processes increased.

Limitations and Future Work

  • Experimental Environment: The authors note that their experimental environment (a two-node cluster where 16 processes share resources within each node) might introduce competition for computing and storage resources. They predict that the algorithm's efficiency would likely be even better on a larger commodity cluster where each node has its own database.
  • Data Structure Support: The paper mentions that existing geodata structures don't fully support parallel computing, and MPI has limitations in serializing and sending complex geographic objects. This suggests that improvements in underlying data structures could further enhance performance.
  • Future Directions: While not explicitly detailed, the success of their integrated approach suggests that applying similar points-based load balancing and hierarchical union strategies to other computationally intensive GIS operations could yield significant performance gains.

Summary updated

Abstract

A buffer generation algorithm that identifies areas of a given distance surrounding geographic features is one of the most frequently used functions in GIS. With the increase of scale and precision in geographic data, the efficiency of the buffer generation algorithm has been of great concern. This study presents a novel integrated solution consisting of a points-based, load-balanced method and a binary union tree method to accelerate the buffer generation. By comparing several parallel candidates, the experimental results show that our new parallel algorithm achieves greater performance and scalability, and its speed increases by 21 times with 32 processes.
BibTeX
@article{huang2012parallel,
  author = {Xiaomeng Huang},
  title = {{Parallel Buffer Generation Algorithm for GIS}},
  journal = {Journal of Geology \& Geosciences},
  year = {2012},
  doi = {10.4172/2329-6755.1000115},
}
Figure