Enabling point pattern analysis on spatial big data using cloud computing: optimizing and accelerating Ripley’s K function

ABSTRACT

Performing point pattern analysis using Ripley’s K function on point events of large size is computationally intensive as it involves massive point-wise comparisons, time-consuming edge effect correction weights calculation, and a large number of simulations. This article presented two strategies to optimize the algorithm for point pattern analysis using Ripley’s K function and utilized cloud computing to further accelerate the optimized algorithm. The first optimization sorted the points on their x and y coordinates and thus narrowed the scope of searching for neighboring points down to a rectangular area around each point in estimating K function. Using the actual study area in computing edge effect correction weights is essential to estimate an unbiased K function, but is very computationally intensive if the study area is of complex shape. The second optimization reused the previously computed weights to avoid repeating expensive weights calculation. The optimized algorithm was then parallelized using Open Multi-Processing (OpenMP) and hybrid Message Passing Interface (MPI)/OpenMP on the cloud computing platform. Performance testing showed that the optimizations effectively accelerated point pattern analysis using K function by a factor of 8 using both the sequential version and the OpenMP-parallel version of the optimized algorithm. While the OpenMP-based parallelization achieved good scalability with respect to the number of CPU cores utilized and the problem size, the hybrid MPI/OpenMP-based parallelization significantly shortened the time for estimating K function and performing simulations by utilizing computing resources on multiple computing nodes. Computational challenge imposed by point pattern analysis tasks on point events of large size involving a large number of simulations can be addressed by utilizing elastic, distributed cloud resources.

KEYWORDS:

• Point pattern analysis
• Ripley’s K function
• optimization
• MPI/OpenMP
• geospatial cloud computing

Acknowledgements

The work reported here was supported by grants from National Natural Science Foundation of China (Project No.: 41431177), National Basic Research Program of China (Project No.: 2015CB954102), Natural Science Research Program of Jiangsu (14KJA170001), PAPD, and National Key Technology Innovation Project for Water Pollution Control and Remediation (Project No.: 2013ZX07103006). Supports to A-Xing Zhu through the Vilas Associate Award, the Hammel Faculty Fellow Award, the Manasse Chair Professorship from the University of Wisconsin-Madison, and the ‘One-Thousand Talents’ Program of China are greatly appreciated. The comments from Professor James E. Burt and other members in the GIS group in the Department of Geography, University of Wisconsin-Madison are much appreciated.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by grants from National Natural Science Foundation of China (Project No.: 41431177), National Basic Research Program of China (Project No.: 2015CB954102), Natural Science Research Program of Jiangsu (14KJA170001), PAPD, and National Key Technology Innovation Project for Water Pollution Control and Remediation (Project No.: 2013ZX07103006). Supports to A-Xing Zhu through the Vilas Associate Award, the Hammel Faculty Fellow Award, the Manasse Chair Professorship from the University of Wisconsin-Madison, and the ‘One-Thousand Talents’ Program of China are greatly appreciated.