Effects of spatial decomposition on the efficiency of kNN search in spatial interpolations. Issue 1 (2nd January 2022)

• Record Type: Journal Article
• Authors: Fan, Naijie; Mei, Gang; Ding, Zengyu; Cuomo, Salvatore; Xu, Nengxiong
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 37:Issue 1(2022)
• Page Start: 103
• Page End: 121
• Publication Date: 2022-01-02
• Subjects: Spatial interpolation -- k nearest neighbours (kNN) search -- uniform grid -- spatial distribution -- standard deviation; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2020.1758102
• Languages: English
• ISSNs: 1744-5760

Abstract

ABSTRACT: Spatial interpolations are commonly used in geometric modelling in life science applications such as medical image processing. In large-scale spatial interpolations, it is always needed to find a local set of data points for each interpolated point using the k Nearest Neighbor ( k NN) search. To improve the efficiency of k NN, the uniform grid is commonly employed to fastly locate neighbours, and the size of grid cell could strongly affect the efficiency of k NN search. In this paper, we evaluate effects of the size of uniform grid cell on the efficiency of kNN search which is implemented on the CPU and GPU. We employ the Standard Deviation of points' coordinates to measure the spatial distribution of scattered points. For irregularly distributed scattered points, we perform several series of kNN search in two- and three-dimensions. Benchmark results indicate that: for both the sequential version implemented on the CPU and the parallel version implemented on the GPU, with the increase of the Standard Deviation of points' coordinates, the relatively optimal size of the grid cell decreases and eventually converges. Moreover, relationships between the Standard Deviation of scattered points' coordinates and the relatively optimal size of grid cell are fitted. GRAPHICAL ABSTRACT: UF0001