Dynamic load balancing in parallel KD-tree k-means

One among the most influential and popular data mining methods is the k-Means algorithm for cluster analysis. Techniques 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 geometrical constraints and an efficient data structure, notably a multidimensional binary search tree (KD-Tree). These techniques allow to reduce the number of distance computations the algorithm performs at each iteration. 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 variants in parallel computing environments. In this work, we provide a parallel formulation of the KD-Tree based k-Means algorithm for distributed memory systems and address its load balancing issue. Three solutions have been developed and tested. Two approaches are based on a static partitioning of the data set and a third solution incorporates a dynamic load balancing policy.

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.

Space partitioning for scalable K-means

K-Means is a popular clustering algorithm which adopts an iterative refinement procedure to determine data partitions and to compute their associated centres of mass, called centroids. The straightforward implementation of the algorithm is often referred to as `brute force' since it computes a proximity measure from each data point to each centroid at every iteration of the K-Means process. Efficient implementations of the K-Means algorithm have been predominantly based on multi-dimensional binary search trees (KD-Trees). A combination of an efficient data structure and geometrical constraints allow to reduce the number of distance computations required at each iteration. In this work we present a general space partitioning approach for improving the efficiency and the scalability of the K-Means algorithm. We propose to adopt approximate hierarchical clustering methods to generate binary space partitioning trees in contrast to KD-Trees. In the experimental analysis, we have tested the performance of the proposed Binary Space Partitioning K-Means (BSP-KM) when a divisive clustering algorithm is used. We have carried out extensive experimental tests to compare the proposed approach to the one based on KD-Trees (KD-KM) in a wide range of the parameters space. BSP-KM is more scalable than KDKM, while keeping the deterministic nature of the `brute force' algorithm. In particular, the proposed space partitioning approach has shown to overcome the well-known limitation of KD-Trees in high-dimensional spaces and can also be adopted to improve the efficiency of other algorithms in which KD-Trees have been used.

A lightweight supercomputing web portal for inferring phylogenetic trees

In this paper we describe a lightweight Web portal developed for running computational jobs on a IBM JS21 Bladecenter cluster, ThamesBlue, for inferring and analyzing evolutionary histories. We first discuss the need for leveraging HPC as a enabler for molecular phylogenetics research. We go on to describe how the portal is designed to interface with existing open-source software that is typical of a HPC resource configuration, and how by design this portal is generic enough to be portable to other similarly configured compute clusters, and for other applications.

The effectiveness of somatic embryogenesis in eliminating the cocoa swollen shoot virus from infected cocoa trees

Investigations were undertaken on the use of somatic embryogenesis to generate cocoa swollen shoot virus (CSSV) disease free clonal propagules, from infected trees. Polymerase chain reaction (PCR) capillary electrophoresis revealed the presence of CSSV in all the callus tissues induced from the CSSV-infected Amelonado cocoa trees (T1, T2 and T4). The virus was transmitted to primary somatic embryos induced from the infected callus tissues at the rate of 10 (19%), 18 (14%) and 16 (15%) for T1, T2 and T4, respectively. Virus free primary somatic embryos from the infected callus tissues converted into plantlets tested CSSV negative by PCR/capillary electrophoresis 2 years after weaning. Secondary somatic embryos induced from the CSSV-infected primary somatic embryos revealed the presence of viral fragments at the rate of 4 (4%) and 9 (9%) for T2 and T4, respectively. Real-time PCR revealed 23 of the 24 secondary somatic embryos contained no detectable virus. Based on these findings, it is proposed that progressive elimination of the CSSV in infected cocoa trees occurred from primary embryogenesis to secondary embryogenesis. (C) 2008 Elsevier B.V. All rights reserved.

Shoot dieback in clipped young Golden Leyland (Cupressocyparis leylandii) trees - a physiological mechanism?

Shoot dieback is a problem in frequently trimmed Leyland hedges and is increasingly affecting gardeners’ choice of hedge trees, having a negative effect on a conifer nursery industry. Some damage can be attributed to the feeding by aphids, but it is unclear if there are also underlying physiological causes. In this study, we tested the hypothesis that shoot-clipping of conifer trees during adverse growing conditions (i.e. high air temperature and low soil moisture) could be leading to shoot ‘dieback’. Three-year-old Golden Leyland Cypress (x Cupressocyparis leylandii ‘Excalibur Gold’) plants were subjected to either a well-watered or droughted irrigation regime and placed in either a ‘hot’ (average day temperature = 40°C) or a ‘cool’ (average day temperature = 27°C) glasshouse compartment. Half of the plants from each glasshouse were clipped on Day 14 and again on Day 50. Measurements of soil moisture content (SMC), net CO2 assimilation rate (A), stomatal conductance (gs), branchlet xylem water potential (XWP), plant height and foliage colour were made. Within the clipped and unclipped treatments of both glasshouse compartments, plants from the droughted regime had significantly lower values for A, gs and XWP than those from the well-watered regime. However, there was no difference in these parameters between the hot and cool glasshouse compartments. The trends seen for A, gs and XWP of all treatments generally mirrored changes in SMC indicating a direct effect of water supply on these parameters. By the end of the experiment the overall foliage colour of plants from the hot glasshouse was darker than that of plants from the cool glasshouse and the overall foliage colour was also darker following shoot clipping. In general, shoot clipping led to increases in A, gs XWP and SMC. This may be due to the reduction in total leaf area leading to a greater supply of water for the remaining leaves. No shoot ‘dieback’ was observed in any treatment in response to drought stress or shoot-clipping.

Control of cocoa swollen shoot disease by eradicating infected trees in Ghana: A survey of treated and replanted areas

Cocoa farms that had been treated and replanted in Ghana during the most recent phase of the cocoa swollen shoot virus (CSSV) eradication campaign were surveyed. Farms that were replanted close to adjoining old cocoa farms or which contained old trees were common in most (38) of the 41 cocoa farms surveyed. CSSV infections were apparent in 20 (53%) out of these 38 farms and they pose a serious risk of causing early infections of the re-planted farms. Control strategies that isolate the newly planted farms by a boundary of immune crops as barriers to reduce CSSV re-infection are discussed. (c) 2005 Elsevier Ltd. All rights reserved.

LVB: parsimony and simulated annealing in the search for phylogenetic trees

Summary: The program LVB seeks parsimonious phylogenies from nucleotide alignments, using the simulated annealing heuristic. LVB runs fast and gives high quality results.