Dynamic load balancing for the distributed mining of molecular structures

In molecular biology, it is often desirable to find common properties in large numbers of drug candidates. One family of methods stems from the data mining community, where algorithms to find frequent graphs have received increasing attention over the past years. However, the computational complexity of the underlying problem and the large amount of data to be explored essentially render sequential algorithms useless. In this paper, we present a distributed approach to the frequent subgraph mining problem to discover interesting patterns in molecular compounds. This problem is characterized by a highly irregular search tree, whereby no reliable workload prediction is available. We describe the three main aspects of the proposed distributed algorithm, namely, a dynamic partitioning of the search space, a distribution process based on a peer-to-peer communication framework, and a novel receiverinitiated load balancing algorithm. The effectiveness of the distributed method has been evaluated on the well-known National Cancer Institute’s HIV-screening data set, where we were able to show close-to linear speedup in a network of workstations. The proposed approach also allows for dynamic resource aggregation in a non dedicated computational environment. These features make it suitable for large-scale, multi-domain, heterogeneous environments, such as computational grids.

Database Engines for Geographical Information Systems

Our ability to identify, acquire, store, enquire on and analyse data is increasing as never before, especially in the GIS field. Technologies are becoming available to manage a wider variety of data and to make intelligent inferences on that data. The mainstream arrival of large-scale database engines is not far away. The experience of using the first such products tells us that they will radically change data management in the GIS field.

Object displays and control of dynamic systems

Recent work has suggested that for some tasks, graphical displays which visually integrate information from more than one source offer an advantage over more traditional displays which present the same information in a separated format. Three experiments are described which investigate this claim using a task which requires subjects to control a dynamic system. In the first experiment, the integrated display is compared to two separated displays, one an animated mimic diagram, the other an alphanumeric display. The integrated display is shown to support better performance in a control task, but experiment 2 shows that part of this advantage may be due to its analogue nature. Experiment 3 considers performance on a fault detection task, and shows no difference between the integrated and separated displays. The paper concludes that previous claims made for integrated displays may not generalize from monitoring to control tasks.

Dynamic scaling of bred vectors in spatially extended chaotic systems

We unfold a profound relationship between the dynamics of finite-size perturbations in spatially extended chaotic systems and the universality class of Kardar-Parisi-Zhang (KPZ). We show how this relationship can be exploited to obtain a complete theoretical description of the bred vectors dynamics. The existence of characteristic length/time scales, the spatial extent of spatial correlations and how to time it, and the role of the breeding amplitude are all analyzed in the light of our theory. Implications to weather forecasting based on ensembles of initial conditions are also discussed.

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.

Stages of organizational transformation in transition economies: A dynamic capabilities approach

How do organizations previously dominated by the state develop dynamic capabilities that would support their growth in a competitive market economy? We develop a theoretical framework of organizational transformation that explains the processes by which organizations learn and develop dynamic capabilities in transition economies. Specifically, the framework theorizes about the importance of, and inter-relationships between, leadership, organizational learning, dynamic capabilities, and performance over three stages of transformation. Propositions derived from this framework explain the pre-conditions enabling organizational learning, the linkages between types of learning and functions of dynamic capabilities, and the feedback from dynamic capabilities to organizational learning that allows firms in transition economies to regain their footing and build long-term competitive advantage. We focus on transition contexts, where these processes have been magnified and thus offer new insights into strategizing in radically altered environments.