Scalability of efficient parallel K-Means

Clustering is defined as the grouping of similar items in a set, and is an important process within the field of data mining. As the amount of data for various applications continues to increase, in terms of its size and dimensionality, it is necessary to have efficient clustering methods. A popular clustering algorithm is K-Means, which adopts a greedy approach to produce a set of K-clusters with associated centres of mass, and uses a squared error distortion measure to determine convergence. Methods for improving the efficiency of K-Means have been largely explored in two main directions. The amount of computation can be significantly reduced by adopting a more efficient data structure, notably a multi-dimensional binary search tree (KD-Tree) to store either centroids or data points. A second direction is parallel processing, where data and computation loads are distributed over many processing nodes. However, little work has been done to provide a parallel formulation of the efficient sequential techniques based on KD-Trees. Such approaches are expected to have an irregular distribution of computation load and can suffer from load imbalance. This issue has so far limited the adoption of these efficient K-Means techniques in parallel computational environments. In this work, we provide a parallel formulation for the KD-Tree based K-Means algorithm and address its load balancing issues.

Non-uniform data distribution for communication-efficient parallel clustering

Global communicationrequirements andloadimbalanceof someparalleldataminingalgorithms arethe major obstacles to exploitthe computational power of large-scale systems. This work investigates how non-uniform data distributions can be exploited to remove the global communication requirement and to reduce the communication costin parallel data mining algorithms and, in particular, in the k-means algorithm for cluster analysis. In the straightforward parallel formulation of the k-means algorithm, data and computation loads are uniformly distributed over the processing nodes. This approach has excellent load balancing characteristics that may suggest it could scale up to large and extreme-scale parallel computing systems. However, at each iteration step the algorithm requires a global reduction operationwhichhinders thescalabilityoftheapproach.Thisworkstudiesadifferentparallelformulation of the algorithm where the requirement of global communication is removed, while maintaining the same deterministic nature ofthe centralised algorithm. The proposed approach exploits a non-uniform data distribution which can be either found in real-world distributed applications or can be induced by means ofmulti-dimensional binary searchtrees. The approachcanalso be extended to accommodate an approximation error which allows a further reduction ofthe communication costs. The effectiveness of the exact and approximate methods has been tested in a parallel computing system with 64 processors and in simulations with 1024 processing element

Efficient group communication for large-scale parallel clustering

Global communication requirements and load imbalance of some parallel data mining algorithms are the major obstacles to exploit the computational power of large-scale systems. This work investigates how non-uniform data distributions can be exploited to remove the global communication requirement and to reduce the communication cost in iterative parallel data mining algorithms. In particular, the analysis focuses on one of the most influential and popular data mining methods, the k-means algorithm for cluster analysis. The straightforward parallel formulation of the k-means algorithm requires a global reduction operation at each iteration step, which hinders its scalability. This work studies a different parallel formulation of the algorithm where the requirement of global communication can be relaxed while still providing the exact solution of the centralised k-means algorithm. The proposed approach exploits a non-uniform data distribution which can be either found in real world distributed applications or can be induced by means of multi-dimensional binary search trees. The approach can also be extended to accommodate an approximation error which allows a further reduction of the communication costs.

The synthesis and properties of [Fe3(CO)11(RCN)] derivatives, and a high-yield general route to mono- and di-substituted derivatives of [Fe3(CO)12]; the crystal and molecular structure of [Fe3(CO)11(NCC6H4-2-Me)]

The clusters [Fe3(CO)11(RCN)] (1: R = Me, C3H5, C6H5, or C6H4-2-Me) have been prepared at low temperature from [Fe3(CO)12] and RCN in the presence of Me3NO. Compounds 1 react essentially quantitatively with a wide range of two-electron donors, L, (viz.: CO, PPh3, P(OMe)3, PPh2H, PPh2Me, PF3, CyNC (Cy = cyclohexyl), P(OEt)3, SbPh3, PBu3, AsPh3, or SnR2 (R = CH(SiMe3)2)) to give [Fe3(CO)11L] (2). In some cases (2), on treatment with Me3NO and then L′ (L′ = a second two-electron donor) yields [Fe3(CO)10LL′] in high yield. The crystal and molecular structures of 1 (L = NCC6H4Me-2) have been determined by a full single crystal structure analysis, and shown to have an axial nitrile coordinated at the unique iron atom, with two CO groups bridging the other two metal atoms.