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.

Artificial ants for active routing

Ant colonies in nature provide a good model for a distributed, robust and adaptive routing algorithm. This paper proposes the adoption of the same strategy for the routing of packets in an Active Network. Traditional store-and-forward routers are replaced by active intermediate systems, which are able to perform computations on transient packets, in a way that results very helpful for developing and dynamically deploying new protocols. The adoption of the Active Networks paradigm associated with a cooperative learning environment produces a robust, decentralized routing algorithm capable of adapting to network traffic conditions.

Adaptive routing in active networks

New conceptual ideas on network architectures have been proposed in the recent past. Current store-andforward routers are replaced by active intermediate systems, which are able to perform computations on transient packets, in a way that results very helpful for developing and deploying new protocols in a short time. This paper introduces a new routing algorithm, based on a congestion metric, and inspired by the behavior of ants in nature. The use of the Active Networks paradigm associated with a cooperative learning environment produces a robust, decentralized algorithm capable of adapting quickly to changing conditions.

The changing structure of diets in the European Union in relation to healthy eating guidelines

Objective: Our objective in this paper is to assess diets in the European Union (EU) in relation to the recommendations of the recent World Health Organization/Food and Agriculture Organization expert consultation and to show how diets have changed between 1961 and 2001. Data and methods: Computations make use of FAOSTAT data on food availability at country level linked to a food composition database to convert foods to nutrients. We further explore the growing similarity of diets in the EU by making use of a consumption similarity index. The index provides a single number measure of dietary overlap between countries. Results: The data confirm the excessive consumption by almost all countries of saturated fats, cholesterol and sugars, and the convergence of nutrient intakes across the EU. Whereas in 1961 diets in several European countries were more similar to US diets than to those of other European countries, this is no longer the case; moreover, while EU diets have become more homogeneous, the EU as a whole and the USA have become less similar over time. Conclusions: Although the dominant cause of greater similarity in EU diets over the period studied is increased intakes in Mediterranean countries of saturated fats, cholesterol and sugar, also important are reductions in saturated fat and sugar in some Northern European countries. This suggests that healthy eating messages are finally having an impact on diets; a distinctly European diet may also be emerging.

Production risk, pesticide use and GM crop technology in South Africa

Technology involving genetic modification of crops has the potential to make a contribution to rural poverty reduction in many developing countries. Thus far, pesticide-producing Bacillus thuringensis (Bt) varieties of cotton have been the main GM crops under cultivation in developing nations. Several studies have evaluated the farm-level performance of Bt varieties in comparison to conventional ones by estimating production technology, and have mostly found Bt technology to be very successful in raising output and/or reducing pesticide input. However, the production risk properties of this technology have not been studied, although they are likely to be important to risk-averse smallholders. This study investigates the output risk aspects of Bt technology by estimating two 'flexible risk' production function models allowing technology to independently affect the mean and higher moments of output. The first is the popular Just-Pope model and the second is a more general 'damage control' flexible risk model. The models are applied to cross-sectional data on South African smallholders, some of whom used Bt varieties. The results show no evidence that a 'risk-reduction' claim can be made for Bt technology. Indeed, there is some evidence to support the notion that the technology increases output risk, implying that simple (expected) profit computations used in past evaluations may overstate true benefits.

CAMCR: Computer assisted mixture model analysis for capture-recapture count data

Population size estimation with discrete or nonparametric mixture models is considered, and reliable ways of construction of the nonparametric mixture model estimator are reviewed and set into perspective. Construction of the maximum likelihood estimator of the mixing distribution is done for any number of components up to the global nonparametric maximum likelihood bound using the EM algorithm. In addition, the estimators of Chao and Zelterman are considered with some generalisations of Zelterman’s estimator. All computations are done with CAMCR, a special software developed for population size estimation with mixture models. Several examples and data sets are discussed and the estimators illustrated. Problems using the mixture model-based estimators are highlighted.

Redox chemistry and electronic properties of 2,3,5,6-tetrakis(2-pyridyl)pyrazine-bridged diruthenium complexes controlled by N,C,N '-biscyclometalated ligands

To investigate the consequences of cyclometalation for electronic communication in dinuclear ruthenium complexes, a series of 2,3,5,6-tetrakis(2-pyridyl)pyrazine (tppz) bridged diruthenium complexes was prepared and studied. These complexes have a central tppz ligand bridging via nitrogen-to-ruthenium coordination bonds, while each ruthenium atom also binds either a monoanionic, N,C,N'-terdentate 2,6-bis(2'-pyridyl)phenyl (R-N boolean AND C boolean AND N) ligand or a 2,2':6',2 ''-terpyridine (tpy) ligand. The N,C,N'-, that is, biscyclometalation, instead of the latter N,N', N ''-bonding motif significantly changes the electronic properties of the resulting complexes. Starting from well-known [{Ru(tpy)}(2)(mu-tppz)](4+) (tpy = 2,2':2 '',6-terpyridine) ([3](4+)) as a model compound, the complexes [{Ru(R-N boolean AND C boolean AND N)}(mu-tppz){Ru(tpy)}](3+) (R-N boolean AND C(H)boolean AND N = 4-R-1,3-dipyridylbenzene, R = H ([4a](3+)), CO2Me ([4b](3+))), and [{Ru(R-N boolean AND C boolean AND N)}(2)(mu-tppz)](2+), (R = H ([5a](2+)), CO2Me ([5b](2+))) were prepared with one or two N,C,N'-cyclometalated terminal ligands. The oxidation and reduction potentials of cyclometalated [4](3+) and [5](2+) are shifted negatively compared to non-cyclometalated [3](4+), the oxidation processes being affected more significantly. Compared to [3](4+), the electronic spectra of [5](2+) display large bathochromic shifts of the main MLCT transitions in the visible spectral region with low-energy absorptions tailing down to the NIR region. One-electron oxidation of [3](4+) and [5](2+) gives rise to low-energy absorption bands. The comproportionation constants and NIR band shape correspond to delocalized Robin-Day class III compounds. Complexes [4a](3+) (R = H) and [4b](3+) (R = CO2Me) also exhibit strong electronic communication, and notwithstanding the large redox-asymmetry the visible metal-to-ligand charge-transfer absorption is assigned to originate from both metal centers. The potential of the first, ruthenium-based, reversible oxidation process is strongly negatively shifted. On the contrary, the second oxidation is irreversible and cyclometalated ligand-based. Upon one-electron oxidation, a weak and low-energy absorption arises.

Interceptive timing: prior knowledge matters

Fast interceptive actions, such as catching a ball, rely upon accurate and precise information from vision. Recent models rely on flexible combinations of visual angle and its rate of expansion of which the tau parameter is a specific case. When an object approaches an observer, however, its trajectory may introduce bias into tau-like parameters that render these computations unacceptable as the sole source of information for actions. Here we show that observer knowledge of object size influences their action timing, and known size combined with image expansion simplifies the computations required to make interceptive actions and provides a route for experience to influence interceptive action.

Inverse problems in dynamic cognitive modeling

Inverse problems for dynamical system models of cognitive processes comprise the determination of synaptic weight matrices or kernel functions for neural networks or neural/dynamic field models, respectively. We introduce dynamic cognitive modeling as a three tier top-down approach where cognitive processes are first described as algorithms that operate on complex symbolic data structures. Second, symbolic expressions and operations are represented by states and transformations in abstract vector spaces. Third, prescribed trajectories through representation space are implemented in neurodynamical systems. We discuss the Amari equation for a neural/dynamic field theory as a special case and show that the kernel construction problem is particularly ill-posed. We suggest a Tikhonov-Hebbian learning method as regularization technique and demonstrate its validity and robustness for basic examples of cognitive computations.

Towards dynamical system models of language-related brain potentials

Event-related brain potentials (ERP) are important neural correlates of cognitive processes. In the domain of language processing, the N400 and P600 reflect lexical-semantic integration and syntactic processing problems, respectively. We suggest an interpretation of these markers in terms of dynamical system theory and present two nonlinear dynamical models for syntactic computations where different processing strategies correspond to functionally different regions in the system's phase space.

Finding the smallest eigenvalue by the inverse Monte Carlo method with refinement

Finding the smallest eigenvalue of a given square matrix A of order n is computationally very intensive problem. The most popular method for this problem is the Inverse Power Method which uses LU-decomposition and forward and backward solving of the factored system at every iteration step. An alternative to this method is the Resolvent Monte Carlo method which uses representation of the resolvent matrix [I -qA](-m) as a series and then performs Monte Carlo iterations (random walks) on the elements of the matrix. This leads to great savings in computations, but the method has many restrictions and a very slow convergence. In this paper we propose a method that includes fast Monte Carlo procedure for finding the inverse matrix, refinement procedure to improve approximation of the inverse if necessary, and Monte Carlo power iterations to compute the smallest eigenvalue. We provide not only theoretical estimations about accuracy and convergence but also results from numerical tests performed on a number of test matrices.

Exact error estimates and optimal randomized algorithms for integration

Exact error estimates for evaluating multi-dimensional integrals are considered. An estimate is called exact if the rates of convergence for the low- and upper-bound estimate coincide. The algorithm with such an exact rate is called optimal. Such an algorithm has an unimprovable rate of convergence. The problem of existing exact estimates and optimal algorithms is discussed for some functional spaces that define the regularity of the integrand. Important for practical computations data classes are considered: classes of functions with bounded derivatives and Holder type conditions. The aim of the paper is to analyze the performance of two optimal classes of algorithms: deterministic and randomized for computing multidimensional integrals. It is also shown how the smoothness of the integrand can be exploited to construct better randomized algorithms.

Modeling of carrier transport in nanowires

We consider a physical model of ultrafast evolution of an initial electron distribution in a quantum wire. The electron evolution is described by a quantum-kinetic equation accounting for the interaction with phonons. A Monte Carlo approach has been developed for solving the equation. The corresponding Monte Carlo algorithm is NP-hard problem concerning the evolution time. To obtain solutions for long evolution times with small stochastic error we combine both variance reduction techniques and distributed computations. Grid technologies are implemented due to the large computational efforts imposed by the quantum character of the model.

What Monte Carlo models can do and cannot do efficiently?

The question "what Monte Carlo models can do and cannot do efficiently" is discussed for some functional spaces that define the regularity of the input data. Data classes important for practical computations are considered: classes of functions with bounded derivatives and Holder type conditions, as well as Korobov-like spaces. Theoretical performance analysis of some algorithms with unimprovable rate of convergence is given. Estimates of computational complexity of two classes of algorithms - deterministic and randomized for both problems - numerical multidimensional integration and calculation of linear functionals of the solution of a class of integral equations are presented. (c) 2007 Elsevier Inc. All rights reserved.

Application of neural network to hybrid systems with binary inputs

Boolean input systems are in common used in the electric industry. Power supplies include such systems and the power converter represents these. For instance, in power electronics, the control variable are the switching ON and OFF of components as thyristors or transistors. The purpose of this paper is to use neural network (NN) to control continuous systems with Boolean inputs. This method is based on classification of system variations associated with input configurations. The classical supervised backpropagation algorithm is used to train the networks. The training of the artificial neural network and the control of Boolean input systems are presented. The design procedure of control systems is implemented on a nonlinear system. We apply those results to control an electrical system composed of an induction machine and its power converter.