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.

Displacement of Zn through acidic light-textured soils

In order to gain understanding of the movement of pollutant metals in soil. the chemical mechanisms involved in the transport of zinc were studied. The displacement of zinc through mixtures of sand and cation exchange resin was measured to validate the methods used for soil. With cation exchange capacities of 2.5 and 5.0 cmol(c) kg(-1). 5.6 and 8.4 pore volumes of 10 mM CaCl2, respectively, were required to displace a pulse of ZnCl2. A simple Burns-type model (Wineglass) using an adsorption coefficient (K-d) determined by fitting a straight line relationship to an adsorption isotherm gave a good fit to the data (K-d=0.73 and 1.29 ml g(-1), respectively). Surface and subsurface samples of an acidic sandy loam (organic matter 4.7 and 1.0%. cation exchange capacity (CEC) 11.8 and 6.1 cmol(c) kg(-1) respectively) were leached with 10 mM calcium chloride. nitrate and perchlorate. With chloride. the zinc pulse was displaced after 25 and 5 pore volumes, respectively. The Kd values were 6.1 and 2.0 ml g(-1). but are based on linear relationships fitted to isotherms which are both curved and show hysteresis. Thus. a simple model has limited value although it does give a general indication of rate of displacement. Leaching with chloride and perchlorate gave similar displacement and Kd values, but slower movement occurred with nitrate in both soil samples (35 and 7 pore volumes, respectively) which reflected higher Kd values when the isotherms were measured using this anion (7.7 and 2.8 ml g(-1) respectively). Although pH values were a little hi-her with nitrate in the leachates, the differences were insufficient to suggest that this increased the CEC enough to cause the delay. No increases in pH occurred with nitrate in the isotherm experiments. Geochem was used to calculate the proportions of Zn complexed with the three anions and with fulvic acid determined from measurements of dissolved organic matter. In all cases, more than 91% of the Zn was present as Zn2+ and there were only minor differences between the anions. Thus, there is an unexplained factor associated with the greater adsorption of Zn in the presence of nitrate. Because as little as five pore volumes of solution displaced Zn through the subsurface soil, contamination of ground waters may be a hazard where Zn is entering a light-textured soil, particularly where soil salinity is increased. Reductions in organic matter content due to cultivation will increase the hazard. (C) 2004 Elsevier B.V. All rights reserved.

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.

Inhibition of 125I-epidermal growth factor binding to murine fibroblasts and keratinocytes by irradiation with ultraviolet-B light

Treatment of murine Swiss 3T3 fibroblasts and XB/2 keratinocytes with UV-B light (302 nm) resulted in a dose-dependent inhibition of [125I] epidermal growth factor (EGF) binding. The light dose required to achieve 50% inhibition of binding in both cell types was 80–85 J/m2 Decreased [125I] platelet-derived growth factor binding was not evoked even by light doses of up to 280 J/m2 UV-B irradiation did not stimultate phosphorylation of the 80 kd protein substrate for protein kinase C. Furthermore, its effect on [125I]EGF binding was not altered as a consequence of protein kinase C down-regulation following prolonged exposure of cells to phorbol esters. These results indicate that UV-B-induced transmodulation of the epidermal growth factor receptor is a specific event mediated through a protein kinase C-indepen dent pathway. Transfer of culture medium from irradiated cells to untreated control cells showed this effect was not induced as a result of transforming growth factor α release and subsequent binding to the EGF receptor in these cells.

Both tumour-promoting and non-promoting phorbol esters inhibit 125I-EGF binding and stimulate the phosphorylation of a 80kd protein kinase C substrate protein in intact Swiss 3T3 cells

Sapintoxin A (SAP A) and 12-deoxyphorbol 13-phenylacetate (DOPP), are two biologically active but non-turnour-promoting phorbol esters that potently bind to and activate the phorbol ester receptor, protein kinase C (PKC). SAP A and DOPP cause a dose-dependent increase in the phosphorylation of an 80 kd (80K) substrate protein for PKC in Swiss 3T3 cells. A similar dose—response effect was seen with sapintoxin D (SAP D), the stage 2 promoting analogue of 12-O-tetradecanoylphorbol-13-acetate and the complete promoter phorbol 12,13-dibutyrate (PDB). The doses resulting in a half maximal phosphorylation of this protein (Ka were 20 nM (SAP A), 45 nM (DOPP), 23 nM (SAP D) and 37 nM (PDB). Both non-promoting and phorbol esters induced a dose-dependent inhibition of [125I]epidermal growth factor (EGF) binding to its receptor in Swiss 3T3 cells. The doses required for 50% inhibition of binding (Ki) were: 8 nM (SAP A), 16 nM (DOPP), 14 nM (SAP D) and 17 nM (PDB). The results clearly demonstrate that induction of phosphorylation of the Pu 80K phosphoprotein and inhibition of [125I]EGF binding in Swiss 3T3 cells following exposure to phorbol esters is independent of the tumour-promoting activity of these compounds. The fact that SAP A, DOPP, SAP D and PDB are mitogenic for a variety of cell types and that exposure to these compounds leads to 80K phosphorylation and inhibition of [125I]EGF binding, suggests that these early biological events may play a role in the mitogenic response induced by these compounds.

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.

Fast regridding of large, complex geospatial datasets

In the earth sciences, data are commonly cast on complex grids in order to model irregular domains such as coastlines, or to evenly distribute grid points over the globe. It is common for a scientist to wish to re-cast such data onto a grid that is more amenable to manipulation, visualization, or comparison with other data sources. The complexity of the grids presents a significant technical difficulty to the regridding process. In particular, the regridding of complex grids may suffer from severe performance issues, in the worst case scaling with the product of the sizes of the source and destination grids. We present a mechanism for the fast regridding of such datasets, based upon the construction of a spatial index that allows fast searching of the source grid. We discover that the most efficient spatial index under test (in terms of memory usage and query time) is a simple look-up table. A kd-tree implementation was found to be faster to build and to give similar query performance at the expense of a larger memory footprint. Using our approach, we demonstrate that regridding of complex data may proceed at speeds sufficient to permit regridding on-the-fly in an interactive visualization application, or in a Web Map Service implementation. For large datasets with complex grids the new mechanism is shown to significantly outperform algorithms used in many scientific visualization packages.

Platelet endothelial cell adhesion molecule-1 signaling inhibits the activation of human platelets

Platelet endothelial cell adhesion molecule-1 (PECAM-1/CD31) is a 130-kd transmembrane glycoprotein and a member of the growing family of receptors with immunoreceptor tyrosine-based inhibitory motifs (ITIMs). PECAM-1 is expressed on platelets, certain T cells, monocytes, neutrophils, and vascular endothelial cells and is involved in a range of cellular processes, though the role of PECAM-1 in platelets is unclear. Cross-linking of PECAM-1 results in phosphorylation of the ITIM allowing the recruitment of signaling proteins that bind by way of Src-homology domain 2 interactions. Proteins that have been implicated in the negative regulation of cellular activation by ITIM-bearing receptors include the tyrosine phosphatases SHP-1 and SHP-2. Tyrosine phosphorylation of immunoreceptor tyrosine-based activatory motif (ITAM)-bearing receptors such as the collagen receptor GPVI-Fc receptor gamma-chain complex on platelets leads to activation. Increasing evidence suggests that ITIM- and ITAM-containing receptors may act antagonistically when expressed on the same cell. In this study it is demonstrated that cross-linking PECAM-1 inhibits the aggregation and secretion of platelets in response to collagen and the GPVI-selective agonist convulxin. In these experiments thrombin-mediated platelet aggregation and secretion were also reduced, albeit to a lesser degree than for collagen, suggesting that PECAM-1 function may not be restricted to the inhibition of ITAM-containing receptor pathways. PECAM-1 activation also inhibited platelet protein tyrosine phosphorylation stimulated by convulxin and thrombin; this was accompanied by inhibition of the mobilization of calcium from intracellular stores. These data suggest that PECAM-1 may play a role in the regulation of platelet function in vivo.

Characterization of Grb2-binding proteins in human platelets activated by Fc gamma RIIA cross-linking.

Glutathione-S-transferase (GST)-Grb2 fusion proteins have been used to identify the potential role of Grb2-binding proteins in platelet activation by the platelet low-affinity IgG receptor, Fc gamma RIIA. Two tyrosine phosphoproteins of 38 and 63 kD bind to the SH2 domain of Grb2 following Fc gamma RIIA stimulation of platelets. Both are located in the particulate fraction following platelet activation and are also able to bind to a GST-construct containing the SH2 and SH3 domains of phospholipase C gamma 1. p38 also forms a complex with the tyrosine kinase csk in stimulated cells and is a substrate for the kinase. The SH3 domains of Grb2 form a stable complex with SOS1 and two proteins of 75 kD and 120 kD, which undergo tyrosine phosphorylation in Fc gamma RIIA stimulated cells. The 75-kD protein is recognized by antibodies to SLP-76, which has recently been isolated from T cells and sequenced. Tyrosine phosphorylation of p38 and p63 is also observed in platelets stimulated by the tyrosine kinase-linked receptor agonist collagen and by the G protein-coupled receptor agonist thrombin, although phosphorylation of SLP-76 is only observed in collagen-stimulated platelets. p38 and p63 may provide a docking site for Grb2, thereby linking Grb2 SH3-binding proteins SOS1, SLP-76, and p120 to downstream signalling events.

Unusual isotope effect in the reaction of chlorosilylene with trimethylsilane-1-d: Absolute rate studies and quantum chemical and Rice–Ramsperger–Kassel–Marcus calculations provide strong evidence for the involvement of an intermediate complex

Time-resolved studies of chlorosilylene, ClSiH, generated by the 193 nm laser flash photolysis of 1-chloro-1- silacyclopent-3-ene, have been carried out to obtain rate constants for its bimolecular reaction with trimethylsilane-1-d, Me3SiD, in the gas phase. The reaction was studied at total pressures up to 100 Torr (with and without added SF6) over the temperature range of 295−407 K. The rate constants were found to be pressure independent and gave the following Arrhenius equation: log[(k/(cm3 molecule−1 s−1)] = (−13.22 ± 0.15) + [(13.20 ± 1.00) kJ mol−1]/(RT ln 10). When compared with previously published kinetic data for the reaction of ClSiH with Me3SiH, kinetic isotope effects, kD/kH, in the range from 7.4 (297 K) to 6.4 (407 K) were obtained. These far exceed values of 0.4−0.5 estimated for a single-step insertion process. Quantum chemical calculations (G3MP2B3 level) confirm not only the involvement of an intermediate complex, but also the existence of a low-energy internal isomerization pathway which can scramble the D and H atom labels. By means of Rice−Ramsperger−Kassel−Marcus modeling and a necessary (but small) refinement of the energy surface, we have shown that this mechanism can reproduce closely the experimental isotope effects. These findings provide the first experimental evidence for the isomerization pathway and thereby offer the most concrete evidence to date for the existence of intermediate complexes in the insertion reactions of silylenes.

A dramatic isotope effect in the reaction of ClSiH with trimethylsilane-1-d: experimental evidence for intermediate complexes in silylene Si-H(D) insertion reactions

A kinetic isotope effect (kD/kH) of 7.4 has been found for the reaction of chlorosilylene with trimethysilane (Me3SiD vs Me3SiH). Such a value can be accounted for by theoretical modelling, but only if an internal rearrangement of the initially form complex is included in the mechanism. This provides the first concrete evidence for such complexes.

Modeling the photo-oxidation of dissolved organic matter by ultraviolet radiation in freshwater lakes: implications for mercury bioavailability

Uncertainties in projected ultraviolet (UV) radiation may lead to future increases in UV irradiation of freshwater lakes. Because dissolved organic carbon (DOC) is the main binding phase for mercury (Hg) in freshwater lakes, an increase in DOC photo-oxidation may affect Hg speciation and bioavailability. We quantified the effect of DOC concentration on the rate of abiotic DOC photo-oxidation for five lakes (DOC = 3.27–12.3 mg L−1) in Kejimkujik National Park, Canada. Samples were irradiated with UV-A or UV-B radiation over a 72-h period. UV-B radiation was found to be 2.36 times more efficient at photo-oxidizing DOC than UV-A, with energy-normalized rates of dissolved inorganic carbon (DIC) production ranging from 3.8 × 10−5 to 1.1 × 10−4 mg L−1 J−1 for UV-A, and from 6.0 × 10−5 to 3.1 × 10−4 mg L−1 J−1 for UV-B. Energy normalized rates of DIC production were positively correlated with DOC concentrations. Diffuse integrated attenuation coefficients were quantified in situ (UV-A Kd = 0.056–0.180 J cm−1; UV-B Kd = 0.015–0.165 J cm−1) and a quantitative depth-integrated model for yearly DIC photo-production in each lake was developed. The model predicts that, UV-A produces between 3.2 and 100 times more DIC (1521–2851 mg m−2 year−1) than UV-B radiation (29.17–746.7 mg m−2 year−1). Future increases in UV radiation may increase DIC production and increase Hg bioavailability in low DOC lakes to a greater extent than in high DOC lakes.