Affordable Access

deepdyve-link
Publisher Website

Improving GPU-accelerated adaptive IDW interpolation algorithm using fast kNN search.

Authors
  • Mei, Gang1
  • Xu, Nengxiong2
  • Xu, Liangliang3
  • 1 Department of Geological Engineering, Qinghai University, No.251 Ningda Road, Xining, 810016 China ; School of Engineering and Technolgy, China University of Geosciences, No.29 Xueyuan Road, Beijing, 100083 China ; Institute of Earth and Environmental Science, University of Freiburg, Albertstr.23B, 79104 Freiburg im Breisgau, Germany. , (China)
  • 2 Department of Geological Engineering, Qinghai University, No.251 Ningda Road, Xining, 810016 China ; School of Engineering and Technolgy, China University of Geosciences, No.29 Xueyuan Road, Beijing, 100083 China. , (China)
  • 3 School of Engineering and Technolgy, China University of Geosciences, No.29 Xueyuan Road, Beijing, 100083 China. , (China)
Type
Published Article
Journal
SpringerPlus
Publisher
Springer (Biomed Central Ltd.)
Publication Date
Jan 01, 2016
Volume
5
Issue
1
Pages
1389–1389
Identifiers
DOI: 10.1186/s40064-016-3035-2
PMID: 27610308
Source
Medline
Keywords
License
Unknown

Abstract

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. The experimental results indicate: (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.

Report this publication

Statistics

Seen <100 times