next up previous
Next: Algorithm Verification Up: Performance Methodology Previous: Performance Methodology

2.2.1 Algorithm Selection

In Comiskey (1993), the Hoshen-Kopelman (HK) algorithm was shown to be the most efficient sequential cluster identification algorithm. The algorithm's one-pass aggregate mechanism does not require access to an entire input map at any given time, which makes it well suited for a divide-and-conquer approach for cluster identification on large maps. A map can be partitioned along row boundaries allowing the algorithm to operate on a map iteratively - as if viewing the map through a sliding window. As the algorithm reaches the end of a partition, the sliding window reveals the next partition and allows the algorithm to continue as though it had access to the entire map. Furthermore, cluster identification on a partitioned map alters neither the performance nor the result of the algorithm when compared to cluster identification on a non-partitioned map. This inherent aggregate mechanism can be exploited to accommodate sequential cluster identification on large maps or cluster identification using a coarse-grained, parallel approach on the CM-5. Thus, the inherent aggregate mechanism was the determining factor in the selection of the HK algorithm.

Michael W. Berry (
Sat Mar 30 23:40:13 EST 1996