  The discrete distribution clustering algorithm, namely D2-clustering, has
demonstrated its usefulness in image classification and annotation where each
object is represented by a bag of weighed vectors. The high computational
complexity of the algorithm, however, limits its applications to large-scale
problems. We present a parallel D2-clustering algorithm with substantially
improved scalability. A hierarchical structure for parallel computing is
devised to achieve a balance between the individual-node computation and the
integration process of the algorithm. Additionally, it is shown that even with
a single CPU, the hierarchical structure results in significant speed-up.
Experiments on real-world large-scale image data, Youtube video data, and
protein sequence data demonstrate the efficiency and wide applicability of the
parallel D2-clustering algorithm. The loss in clustering accuracy is minor in
comparison with the original sequential algorithm.
