Spatial interpolation, a commonly used GIS operation, is a key element in the toolboxes provided by commercial GIS software environments, and is also described in most GIS textbooks. Researchers can choose from a variety of algorithms to calculate an interpolated surface from a number of control points. In general, each approach uses either the entire data set to make an estimate for a grid cell location (global methods) or restricts, after searching, calculations to include only those observations that fall in some neighborhood of the location from which the grid cell estimate is being made (local methods).

Local approaches to interpolation are based on an underlying assumption of positive spatial autocorrelation. The crux of local interpolation algorithms is to reduce the amount of computation required to perform 2-dimensional *k*-nearest (however defined) neighbor search, a noxiously computationally intensive problem. Our research focuses on developing and evaluating 2-dimensional *k*-nearest neighbor search algorithms to support high performance spatial interpolation. We are currently developing a novel mechanism to reduce *k*-nearest neighbor search cost.

**Project Team**: Marc Armstrong, Yan Liu, Eric Shook, Shaowen Wang