Declustering and load-balancing methods for parallelizing geographic information systems

Shashi Shekhar, Sivakumar Ravada, Vipin Kumar, Douglas Chubb, Greg Turner

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

Declustering and load-balancing are important issues in designing a high-performance geographic information system (HPGIS), which is a central component of many interactive applications• such as real-time terrain visualization. The current literature provides efficient methods for declustering spatial point-data. However, there has been little work toward developing efficient declustering methods for collections of extended objects, like chains of line-segments and polygons. In this paper, we focus on the data-partitioning approach to parallelizing GIS operations. We provide a framework for declustering collections of extended spatial objects by identifying the following key issues: 1) the work-load metric, 2) the spatial-extent of the work-load, 3) the distribution of the work-load over the spatial-extent, and 4) the declustering method. We identify and experimentally evaluate alternatives for each of these issues. In addition, we also provide a framework for dynamically balancing the load between different processors. We experimentally evaluate the proposed declustering and load-balancing methods on a distributed memory MIMD machine (Cray T3D). Experimental results show that the spatial-extent and the work-load metric are important issues in developing a declustering method. Experiments also show that the replication of data is usually needed to facilitate dynamic load-balancing, since the cost of local processing is often less than the cost of data transfer for extended spatial objects. In addition, we also show that the effectiveness of dynamic load-balancing techniques can be improved by using declustering methods to determine the subsets of spatial objects to be transferred during runtime.

Original languageEnglish (US)
Pages (from-to)632-655
Number of pages24
JournalIEEE Transactions on Knowledge and Data Engineering
Volume10
Issue number4
DOIs
StatePublished - 1998

Bibliographical note

Funding Information:
This project is sponsored, in part, by the Army High-Performance Computing Research Center under the auspices of the Department of the Army, the Army Research Laboratory cooperative agreement No. DAAH04-95-2-0003, Contract No. DAAH04-95-C-0008, the content of which does not necessarily reflect the position or the policy of the government of the United States of America, and no official endorsement should be inferred.

Keywords

  • Declustering methods
  • Geographic information systems
  • High performance
  • Load-balancing
  • Polygon clipping
  • Range query

Fingerprint Dive into the research topics of 'Declustering and load-balancing methods for parallelizing geographic information systems'. Together they form a unique fingerprint.

Cite this