Hierarchical Clustering on SIMD Machines with Alignment Network

Li, Xiaobo

doi:10.1109/CVPR.1989.37916

Hierarchical Clustering on SIMD Machines with Alignment Network

Xiaobo Li

CVPR 1989 pp. 660-665

doi:10.1109/CVPR.1989.37916 /cvpr/1989/li1989cvpr-hierarchical/

Abstract

Several parallel algorithms and parallel architectures have been developed for partitional clustering. Hierarchical clustering algorithms are also widely used in exploratory pattern analysis and unsupervised learning. The author proposes parallel algorithms on single-instruction/multiple-data (SIMD) machines for hierarchical clustering, which require intensive computation and large memory storage. The machine model includes a parallel memory system and an alignment network, to facilitate parallel access of both pattern matrix and proximity matrix. Since clustering algorithms tend to generate clusters even when applied to random data, clustering-tendency and cluster-validity studies are usually performed. The author proposes a parallel algorithm to compute one type of cluster validity measure global fit of hierarchy for quantitative data. For a problem with N patterns, considering validity study as well as clustering, the number of memory accesses is reduced from O(/sup 3/) on a sequential machine to O(N/sup 2/) on a SIMD machine with N processing elements (PEs). More general algorithms for different numbers of PEs are also given.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>

CVPR Semantic Scholar

Cite

Text

Li. "Hierarchical Clustering on SIMD Machines with Alignment Network." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1989. doi:10.1109/CVPR.1989.37916

Markdown

[Li. "Hierarchical Clustering on SIMD Machines with Alignment Network." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1989.](https://mlanthology.org/cvpr/1989/li1989cvpr-hierarchical/) doi:10.1109/CVPR.1989.37916

BibTeX

@inproceedings{li1989cvpr-hierarchical,
  title     = {{Hierarchical Clustering on SIMD Machines with Alignment Network}},
  author    = {Li, Xiaobo},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year      = {1989},
  pages     = {660-665},
  doi       = {10.1109/CVPR.1989.37916},
  url       = {https://mlanthology.org/cvpr/1989/li1989cvpr-hierarchical/}
}