Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.15 No.3, pp.441-449 (May 1999)
Load Balancing for the Parallel Map Overlay-Operation
in the Geographic Information System*

Yu-Tai Ching
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.

The map overlay-operation is one of the most important and most time consuming operations in the Geographic Information System. In general, a map consists of a huge number of line segments. The major cost for overlaying two maps is that of computing the intersection points between the line segments. Parallel processing is one of the ways to reduce the computing time. If one can partition the line segments into independent subsets, then these subsets can be processed in different processors simultaneously; thus, the computing time can be reduced. In this paper, we consider the problem of partitioning line segments into independent sets such that the load is balanced among the processors. An easy yet effective strategy is proposed to balance the load for a multi-processor computer which does not have many processors. The proposed algorithm can achieve good load balance when the average length of the line segments is short compared to the width of a map.

Keywords: geographic Information system, parallel algorithm, load balancing, computational geometry, line segments intersection

Full Text () Retrieve PDF document (199905_09.pdf : 50,031 bytes)

Received November 1997; revised May 15 & August 17, 1998; accepted September 1, 1998.
Communicated by Jhing-Fa Wang.
*This work was supported by the National Science Council, Taiwan, Republic of China under Grant No. NSC81-0408-E009-534 and NSC82-0408-E009-415.