A quadtree approach to domain decomposition for spatial interpolation in Grid computing environments

Shaowen Wang, Marc P. Armstrong

Research output: Contribution to journalArticlepeer-review


Spatial interpolation is widely used in geographical information systems to create continuous surfaces from discrete data points. The creation of such surfaces, however, can involve considerable computation, especially when large problems are addressed, because of the need to search for neighbors on which to base interpolation calculations. Computational Grids provide the computing resources to tackle spatial interpolation in a timely way. The objective of this paper is to investigate the use of domain decomposition for a distributed inverse-distance-weighted spatial interpolation algorithm; the algorithm runs using the Globus Toolkit (GT) in a heterogeneous Grid computing environment. The interpolation algorithm is modified for implementation in the Grid by using a quadtree to spatially index and adaptively decompose the interpolation problem to balance processing loads. In addition, the GT allows the distributed algorithm to couple multiple machines, potentially of different architectures, to dynamically schedule the decomposed sub-problems through Globus services and protocols (e.g., resource management, data transfer). Experiments are conducted to test how well this distributed IDW interpolation algorithm scales to heterogeneous grid computing environments using irregularly distributed geographical data sets.

Original languageEnglish (US)
Pages (from-to)1481-1504
Number of pages24
JournalParallel Computing
Issue number10
StatePublished - Oct 2003
Externally publishedYes


  • Computational Grid
  • Domain decomposition
  • Globus toolkit
  • Quadtree
  • Spatial interpolation

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence


Dive into the research topics of 'A quadtree approach to domain decomposition for spatial interpolation in Grid computing environments'. Together they form a unique fingerprint.

Cite this