  This paper presents an efficient parallel Adaptive Inverse Distance Weighting
(AIDW) interpolation algorithm on modern Graphics Processing Unit (GPU). The
presented algorithm is an improvement of our previous GPU-accelerated AIDW
algorithm by adopting fast k-Nearest Neighbors (kNN) search. In AIDW, it needs
to find several nearest neighboring data points for each interpolated point to
adaptively determine the power parameter; and then the desired prediction value
of the interpolated point is obtained by weighted interpolating using the power
parameter. In this work, we develop a fast kNN search approach based on the
space-partitioning data structure, even grid, to improve the previous
GPU-accelerated AIDW algorithm. The improved algorithm is composed of the
stages of kNN search and weighted interpolating. To evaluate the performance of
the improved algorithm, we perform five groups of experimental tests.
Experimental results show that: (1) the improved algorithm can achieve a
speedup of up to 1017 over the corresponding serial algorithm; (2) the improved
algorithm is at least two times faster than our previous GPU-accelerated AIDW
algorithm; and (3) the utilization of fast kNN search can significantly improve
the computational efficiency of the entire GPU-accelerated AIDW algorithm.
