DECLUSTERING AND LOAD-BALANCING METHODS FOR PARALLELIZING GEOGRAPHIC INFORMATION-SYSTEMS

Declustering and load-balancing are important issues in designing a hi gh-performance geographic information system (HPGIS), which is a centr al component of many interactive applications-such as real-time terrai n 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 ex tended objects, like chains of line-segments and polygons. In this pap er, we focus on the data-partitioning approach to parallelizing GIS op erations. We provide a framework for declustering collections of exten ded spatial objects by identifying the following key issues: 1)the wor k-load metric, 2) the spatial-extent of the work-load, 3) the distribu tion 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 dynamic ally balancing the load between different processors. We experimentall y evaluate the proposed declustering and load-balancing methods on a d istributed memory MIMD machine (Cray T3D). Experimental results show t hat the spatial-extent and the work-load metric are important issues i n developing a declustering method. Experiments also show that the rep lication of data is usually needed to facilitate dynamic load-balancin g, since the cost of local processing is often less than the cost of d ata transfer for extended spatial objects. In addition, we also show t hat the effectiveness of dynamic load-balancing techniques can be impr oved by using declustering methods to determine the subsets of spatial objects to be transferred during runtime.