Loading...
Please wait, while we are loading the content...
Similar Documents
Parallel Algorithms for Hierarchical Clustering (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Olson, Clark F. |
| Abstract | Hierarchical clustering is a common method used to determine clusters of similar data points in multidimensional spaces. O(n 2 ) algorithms are known for this problem [3, 4, 10, 18]. This paper reviews important results for sequential algorithms and describes previous work on parallel algorithms for hierarchical clustering. Parallel algorithms to perform hierarchical clustering using several distance metrics are then described. Optimal PRAM algorithms using n log n processors are given for the average link, complete link, centroid, median, and minimum variance metrics. Optimal butterfly and tree algorithms using n log n processors are given for the centroid, median, and minimum variance metrics. Optimal asymptotic speedups are achieved for the best practical algorithm to perform clustering using the single link metric on a n log n processor PRAM, butterfly, or tree. Keywords. Hierarchical clustering, pattern analysis, parallel algorithm, butterfly network, PRAM algorithm. 1 In... |
| File Format | |
| Volume Number | 21 |
| Journal | Parallel Computing |
| Language | English |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Hierarchical Clustering Parallel Algorithm Log Processor Minimum Variance Metric Sequential Algorithm Butterfly Network Optimal Asymptotic Speedup Pattern Analysis Tree Algorithm Previous Work Pram Algorithm Multidimensional Space Similar Data Point Important Result Several Distance Metric Practical Algorithm Common Method Log Processor Pram Complete Link Optimal Pram Algorithm Single Link Optimal Butterfly Average Link |
| Content Type | Text |
| Resource Type | Article |
