A parallel approach to searching for nearest neighbors with minimal interprocess communication
Shepard, William Erik
MetadataShow full item record
This research exploited a classic sequential method for nearest neighbor searching in order to develop a parallel search approach. This approach was implemented in an inverse distance weighting routine in order to demonstrate efficacy. A set of 100 sample point datasets was developed and interpolated using the sequential implementation of inverse distance weighting present in ARC/INFO and the parallel implementation developed in the course of this work. Run times were captured for each run in both sets of 100 and compared to absolutely and proportionally in order to assess improvement using the parallel methodology over the sequential methodology. Experimental results showed that, while sequential processing times increase exponentially, parallel processing times increase linearly. The mean proportion of parallel time to sequential time for the 100 runs was 17% with a 5% standard deviation (maximum of 27% and minimum of 8%), increasing exponentially as input and output sizes increased linearly.