Design and implementation of a parallel geographically weighted k-nearest neighbor classifier.

Area of Science:

• Remote Sensing
• Computer Science
• Geographic Information Systems (GIS)

Background:

• High-performance classifiers are crucial for timely remote sensing classification with high spatial resolution data.
• Geographically weighted k-nearest neighbors (gwk-NN) improves upon traditional k-NN by incorporating spatial information, reducing noise and misclassification.
• The computational intensity of integrating spatial and spectral information in gwk-NN hinders its practical application.

Purpose of the Study:

• To improve the computing performance of the gwk-NN classifier for remote sensing image analysis.
• To investigate the effectiveness of data and task parallelism strategies in parallelizing the gwk-NN algorithm.
• To evaluate the potential of dual parallelism (combining data and task parallelism) for enhanced image classification efficiency.

Main Methods:

• Implementation of parallel gwk-NN using MPI and GDAL in C++ on an eight-core computer.
• Application of data parallelism and task parallelism strategies to model training and classification stages.
• Investigation of dual parallelism approaches, prioritizing data decomposition in one variant.

Main Results:

• Parallel gwk-NN significantly improves efficiency for high-resolution, multi-class remote sensing images.
• Data parallelism outperforms task parallelism due to lower parallel overhead in both training and classification.
• Dual parallelism achieves the highest speedups (up to 5.73×), with dual parallelism II (data-priority) being most effective by overlapping computation and data transmission.

Conclusions:

• Parallelization strategies, particularly dual parallelism, are effective in accelerating gwk-NN for remote sensing image classification.
• Data parallelism is generally more efficient than task parallelism for gwk-NN due to overhead considerations.
• Dual parallelism II offers optimal performance by leveraging data decomposition and overlapping computation with data transmission, aligning with multicore architecture trends.