Finding Tropical Cyclones on a Cloud Computing Cluster: Using Parallel Virtualization for Large-Scale Climate Simulation Analysis

Daren Hasenkamp, Alexander Sim, Michael Wehner, Kesheng Wu


This paper presents two new strategies to speed up connected component labeling algorithms. The first strategy employs a decision tree to minimize the work performed in the scanning phase of connected component labeling algorithms. The second strategy uses a simplified union-find data structure to represent the equivalence information among the labels. For 8-connected components in a two-dimensional (2D) image, the first strategy reduces the number of neighboring pixels visited from 4 to 7/3 on average. In various tests, using a decision tree decreases the scanning time by a factor of about 2. The second strategy uses a compact representation of the union-find data structure. This strategy significantly speeds up the labeling algorithms. We prove analytically that a labeling algorithm with our simplified union-find structure has the same optimal theoretical time complexity as do the best labeling algorithms. By extensive experimental measurements, we confirm the expected performance characteristics of the new labeling algorithms and demonstrate that they are faster than other optimal labeling algorithms.

full text of LBNL-4218E (PDF)

Daren won 3rd place as SC10 ACM Student Research Competition for his part in this work.

More research work by John Wu
Bitmap Index
Connected Component Labeling
Eigenvalue Computation
Inforamtion available elsewhere on the web
Google Scholar
Contact us

John Wu