Load balancing for the parallel map overlay-operation in the geographic information system

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)441-449
Number of pages9
JournalJournal of Information Science and Engineering
Volume15
Issue number3
DOIs
StatePublished - 1 May 1999

Fingerprint Dive into the research topics of 'Load balancing for the parallel map overlay-operation in the geographic information system'. Together they form a unique fingerprint.

Cite this