A Coarse Grained Parallel Algorithm for Closest Larger Ancestors In Trees with Applications to Single Link Clustering.

Albert Chan,   Chunmei Gao, Andrew Rau-Chaplin

Abstract: Hierarchical clustering methods are important in many data mining and pattern recognition tasks. In this paper we present an efficient coarse grained parallel algorithm for Single Link Clustering; a standard inter-cluster linkage metric. Our approach is to first describe algorithms for the Prefix Larger Integer Set and the Closest Larger Ancestor problems and then to show how these can be applied to solve the Single Link Clustering problem. In an extensive
performance analysis on a Linux-based cluster an implementation of these algorithms has shows proven to scale well, exhibiting near linear relative speedup on up to twenty-four processors.