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.

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.

A tractable means of correcting sector level TFP calculations in the face of biased technological change.

The measurement of the impact of technical change has received significant attention within the economics literature. One popular method of quantifying the impact of technical change is the use of growth accounting index numbers. However, in a recent article Nelson and Pack (1999) criticise the use of such index numbers in situations where technical change is likely to be biased in favour of one or other inputs. In particular they criticise the common approach of applying observed cost shares, as proxies for partial output elasticities, to weight the change in quantities which they claim is only valid under Hicks neutrality. Recent advances in the measurement of product and factor biases of technical change developed by Balcombe et al (2000) provide a relatively straight-forward means of correcting product and factor shares in the face of biased technical progress. This paper demonstrates the correction of both revenue and cost shares used in the construction of a TFP index for UK agriculture over the period 1953 to 2000 using both revenue and cost function share equations appended with stochastic latent variables to capture the bias effect. Technical progress is shown to be biased between both individual input and output groups. Output and input quantity aggregates are then constructed using both observed and corrected share weights and the resulting TFPs are compared. There does appear to be some significant bias in TFP if the effect of biased technical progress is not taken into account when constructing the weights

Estimation following selection of the largest of two normal means

This paper considers the problem of estimation when one of a number of populations, assumed normal with known common variance, is selected on the basis of it having the largest observed mean. Conditional on selection of the population, the observed mean is a biased estimate of the true mean. This problem arises in the analysis of clinical trials in which selection is made between a number of experimental treatments that are compared with each other either with or without an additional control treatment. Attempts to obtain approximately unbiased estimates in this setting have been proposed by Shen [2001. An improved method of evaluating drug effect in a multiple dose clinical trial. Statist. Medicine 20, 1913–1929] and Stallard and Todd [2005. Point estimates and confidence regions for sequential trials involving selection. J. Statist. Plann. Inference 135, 402–419]. This paper explores the problem in the simple setting in which two experimental treatments are compared in a single analysis. It is shown that in this case the estimate of Stallard and Todd is the maximum-likelihood estimate (m.l.e.), and this is compared with the estimate proposed by Shen. In particular, it is shown that the m.l.e. has infinite expectation whatever the true value of the mean being estimated. We show that there is no conditionally unbiased estimator, and propose a new family of approximately conditionally unbiased estimators, comparing these with the estimators suggested by Shen.

Root pruning as a means to encourage root growth in two ornamental shrubs, Buddleja davidii ‘Summer Beauty’ and Cistus ‘Snow Fire'

The inability of a plant to grow roots rapidly upon transplanting is one of the main factors contributing to poor establishment. In bare-rooted trees, treatments such as root pruning or application of the plant hormone auxin [e.g., indole butyric acid (IBA)] can promote root growth and aid long-term establishment. There is little information on ornamental containerised plants, however, other than the anecdotal notion that 'teasing' the roots out of the rootsoil mass before transplanting can be beneficial. In the present study we tested the ability of various root-pruning treatments and application of IBA to encourage new root and shoot growth in two shrub species, commonly produced in containers - Buddleja davidii 'Summer Beauty' and Cistus 'Snow Fire'. In a number of experiments, young plants were exposed to root manipulation (teasing, light pruning, or two types of heavy pruning) and/or treatment with IBA (at 500 or 1,000 mg l-1) before being transplanted into larger containers containing a medium of 1:1:1 (v/v/v) fine bark, sand and loam. Leaf stomatal conductance (gl) was measured 20 min, and 1, 2, 4 and 6 h after root manipulation. Net leaf CO2 assimilation (A) was measured frequently during the first week after transplanting, then at regular intervals up to 8 weeks after transplanting. Plants were harvested 8 weeks after transplanting, and root and shoot weights were measured. In both species, light root pruning alone, or in combination with 500 mg l-1 IBA, was most effective in stimulating root growth. In contrast, teasing, which is commonly used, showed no positive effect on root growth in Buddleja, and decreased new root growth in Cistus. The requirement for exogenous auxin to encourage new root growth varied between experiments and appeared to be influenced by the age and developmental stage of the plants. There were no consistent responses between root treatments and net CO2 assimilation rates, and changes in root weight were not closely correlated with changes in assimilation. The mechanisms whereby new root growth is sustained are discussed.

Regulated deficit irrigation - a means to control growth in woody ornamentals

Improving plant quality and the uniformity of a crop are major objectives for growers of ornamental nursery stock. The potential to control excess vigour and to improve quality through regulated deficit irrigation (RDI) was investigated using a range of woody ornamental species. RDI regimes reduced vegetative growth consistently across different species and growing seasons. Plants adapted to reduced water supplies primarily via stomatal control, but also by osmotic adjustment when grown under the most severe RDI regimes. Only plants exposed to <= 25% of potential evapo-transpiration demonstrated any evidence of leaf injury, and the extent was slight. Growth inhibition increased as the severity of RDI increased. Improvements in quality were attained through a combination of shorter internodes and final shoot lengths, yet the number of 'formative' primary shoots remained unaffected. Compact, well-branched plants could be formed without a requirement for mid-season pruning. In addition to severity, the timing of RDI also influenced growth responses. Applying 50% ETp for 8 weeks during July-August resulted in the formation of good quality plants, which retained their shape until the following Spring. Re-positioning irrigation drippers within the pots of well-watered plants, in an attempt to induce a partial root drying (PRD) treatment, reduced growth, but not significantly. The adoption of irrigation scheduling, based on 50-100% ETp, has the potential to improve commercial crop quality across a range of ornamental species.

Enhancing dominant modes in nonstationary time series by means of the symbolic resonance analysis

We present the symbolic resonance analysis (SRA) as a viable method for addressing the problem of enhancing a weakly dominant mode in a mixture of impulse responses obtained from a nonlinear dynamical system. We demonstrate this using results from a numerical simulation with Duffing oscillators in different domains of their parameter space, and by analyzing event-related brain potentials (ERPs) from a language processing experiment in German as a representative application. In this paradigm, the averaged ERPs exhibit an N400 followed by a sentence final negativity. Contemporary sentence processing models predict a late positivity (P600) as well. We show that the SRA is able to unveil the P600 evoked by the critical stimuli as a weakly dominant mode from the covering sentence final negativity. (c) 2007 American Institute of Physics. (c) 2007 American Institute of Physics.

Improvement of link failure restoration utilising MPLS as a means to maintain QoS

The availability of a network strongly depends on the frequency of service outages and the recovery time for each outage. The loss of network resources includes complete or partial failure of hardware and software components, power outages, scheduled maintenance such as software and hardware, operational errors such as configuration errors and acts of nature such as floods, tornadoes and earthquakes. This paper proposes a practical approach to the enhancement of QoS routing by means of providing alternative or repair paths in the event of a breakage of a working path. The proposed scheme guarantees that every Protected Node (PN) is connected to a multi-repair path such that no further failure or breakage of single or double repair paths can cause any simultaneous loss of connectivity between an ingress node and an egress node. Links to be protected in an MPLS network are predefined and an LSP request involves the establishment of a working path. The use of multi-protection paths permits the formation of numerous protection paths allowing greater flexibility. Our analysis will examine several methods including single, double and multi-repair routes and the prioritization of signals along the protected paths to improve the Quality of Service (QoS), throughput, reduce the cost of the protection path placement, delay, congestion and collision.