PDM 2006: Proceedings of the International Workshop on Data Mining

Recently major processor manufacturers have announced a dramatic shift in their paradigm to increase computing power over the coming years. Instead of focusing on faster clock speeds and more powerful single core CPUs, the trend clearly goes towards multi core systems. This will also result in a paradigm shift for the development of algorithms for computationally expensive tasks, such as data mining applications. Obviously, work on parallel algorithms is not new per se but concentrated efforts in the many application domains are still missing. Multi-core systems, but also clusters of workstations and even large-scale distributed computing infrastructures provide new opportunities and pose new challenges for the design of parallel and distributed algorithms. Since data mining and machine learning systems rely on high performance computing systems, research on the corresponding algorithms must be on the forefront of parallel algorithm research in order to keep pushing data mining and machine learning applications to be more powerful and, especially for the former, interactive. To bring together researchers and practitioners working in this exciting field, a workshop on parallel data mining was organized as part of PKDD/ECML 2006 (Berlin, Germany). The six contributions selected for the program describe various aspects of data mining and machine learning approaches featuring low to high degrees of parallelism: The first contribution focuses the classic problem of distributed association rule mining and focuses on communication efficiency to improve the state of the art. After this a parallelization technique for speeding up decision tree construction by means of thread-level parallelism for shared memory systems is presented. The next paper discusses the design of a parallel approach for dis- tributed memory systems of the frequent subgraphs mining problem. This approach is based on a hierarchical communication topology to solve issues related to multi-domain computational envi- ronments. The forth paper describes the combined use and the customization of software packages to facilitate a top down parallelism in the tuning of Support Vector Machines (SVM) and the next contribution presents an interesting idea concerning parallel training of Conditional Random Fields (CRFs) and motivates their use in labeling sequential data. The last contribution finally focuses on very efficient feature selection. It describes a parallel algorithm for feature selection from random subsets. Selecting the papers included in this volume would not have been possible without the help of an international Program Committee that has provided detailed reviews for each paper. We would like to also thank Matthew Otey who helped with publicity for the workshop.

The Genomic Threading Database: a comprehensive resource for structural annotations of the genomes from key organisms

Currently, the Genomic Threading Database (GTD) contains structural assignments for the proteins encoded within the genomes of nine eukaryotes and 101 prokaryotes. Structural annotations are carried out using a modified version of GenTHREADER, a reliable fold recognition method. The Gen THREADER annotation jobs are distributed across multiple clusters of processors using grid technology and the predictions are deposited in a relational database accessible via a web interface at http://bioinf.cs.ucl.ac.uk/GTD. Using this system, up to 84% of proteins encoded within a genome can be confidently assigned to known folds with 72% of the residues aligned. On average in the GTD, 64% of proteins encoded within a genome are confidently assigned to known folds and 58% of the residues are aligned to structures.

Evolutionary dynamics of Staphylococcus aureus during progression from carriage to disease

Whole-genome sequencing offers new insights into the evolution of bacterial pathogens and the etiology of bacterial disease. Staph- ylococcus aureus is a major cause of bacteria-associated mortality and invasive disease and is carried asymptomatically by 27% of adults. Eighty percent of bacteremias match the carried strain. How- ever, the role of evolutionary change in the pathogen during the progression from carriage to disease is incompletely understood. Here we use high-throughput genome sequencing to discover the genetic changes that accompany the transition from nasal carriage to fatal bloodstream infection in an individual colonized with meth- icillin-sensitive S. aureus. We found a single, cohesive population exhibiting a repertoire of 30 single-nucleotide polymorphisms and four insertion/deletion variants. Mutations accumulated at a steady rate over a 13-mo period, except for a cluster of mutations preceding the transition to disease. Although bloodstream bacteria differed by just eight mutations from the original nasally carried bacteria, half of those mutations caused truncation of proteins, including a prema- ture stop codon in an AraC-family transcriptional regulator that has been implicated in pathogenicity. Comparison with evolution in two asymptomatic carriers supported the conclusion that clusters of pro- tein-truncating mutations are highly unusual. Our results demon- strate that bacterial diversity in vivo is limited but nonetheless detectable by whole-genome sequencing, enabling the study of evolutionary dynamics within the host. Regulatory or structural changes that occur during carriage may be functionally important for pathogenesis; therefore identifying those changes is a crucial step in understanding the biological causes of invasive bacterial disease.

Success and failure of grassroots innovations for addressing climate change: the case of the Transition Movement

Grassroots innovations emerge as networks generating innovative solutions for climate change adaptation and mitigation. However, it is unclear if grassroots innovations can be successful in responding to climate change. Little evidence exists on replication, international comparisons are rare, and research tends to overlook discontinued responses in favour of successful ones. We take the Transition Movement as a case study of a rapidly spreading transnational grassroots network, and include both active and non-active local transition initiatives. We investigate the replication of grassroots innovations in different contexts with the aim to uncover general patterns of success and failure, and identify questions for future research. An online survey was carried out in 23 countries (N=276). The data analysis entailed testing the effect of internal and contextual factors of success as drawn from the existing literature, and the identification of clusters of transition initiatives with similar internal and contextual factor configurations. Most transition initiatives consider themselves successful. Success is defined along the lines of social connectivity and empowerment, and external environmental impact. We find that less successful transition initiatives might underestimate the importance of contextual factors and material resources in influencing success. We also find that their diffusion is linked to the combination of local-global learning processes, and that there is an incubation period during which a transition initiative is consolidated. Transition initiatives seem capable of generalising organisational principles derived from unique local experiences that seem to be effective in other local contexts. However, the geographical locations matter with regard to where transition initiatives take root and the extent of their success, and ‘place attachment’ may have a role in the diffusion of successful initatives. We suggest that longitudinal comparative studies can advance our understanding in this regard, as well as inform the changing nature of the definition of success at different stages of grassroots innovation development, and the dynamic nature of local and global linkages.

Simple method for sub-diffraction resolution imaging of cellular structures on standard confocal microscopes by three-photon absorption of quantum dots

This study describes a simple technique that improves a recently developed 3D sub-diffraction imaging method based on three-photon absorption of commercially available quantum dots. The method combines imaging of biological samples via tri-exciton generation in quantum dots with deconvolution and spectral multiplexing, resulting in a novel approach for multi-color imaging of even thick biological samples at a 1.4 to 1.9-fold better spatial resolution. This approach is realized on a conventional confocal microscope equipped with standard continuous-wave lasers. We demonstrate the potential of multi-color tri-exciton imaging of quantum dots combined with deconvolution on viral vesicles in lentivirally transduced cells as well as intermediate filaments in three-dimensional clusters of mouse-derived neural stem cells (neurospheres) and dense microtubuli arrays in myotubes formed by stacks of differentiated C2C12 myoblasts.

Typographic meaning: readers’ impressions of patterns of typographic differentiation

This research explores whether patterns of typographic differentiation influence readers’ impressions of documents. It develops a systematic approach to typographic investigation that considers relationships between different kinds of typographic attributes, rather than testing the influence of isolated variables. An exploratory study using multiple sort tasks and semantic differential scales identifies that readers form a variety of impressions in relation to how typographic elements are differentiated in document design. Building on the findings of the exploratory study and analysis of a sample of magazines, the research describes three patterns of typographic differentiation: high, moderate, and low. Each pattern comprises clusters of typographic attributes and organisational principles that are articulated in relation to a specified level of typographic differentiation (amplified, medium, or subtle). The patterns are applied to two sets of controlled test material. Using this purposely-designed material, the influence of patterns of typographic differentiation on readers’ impressions of documents is explored in a repertory grid analysis and a paired comparison procedure. The results of these studies indicate that patterns of typographic differentiation consistently shape readers’ impressions of documents, influencing judgments of credibility, document address, and intended readership; and suggesting particular kinds of engagement and genre associations. For example, high differentiation documents are likely to be considered casual, sensationalist, and young; moderate differentiation documents are most likely to be seen as formal and serious; and low differentiation examples are considered calm. Typographic meaning is shown to be created through complex, yet systematic, interrelationships rather than reduced to a linear model of increasing or decreasing variation. The research provides a way of describing typographic articulation that has application across a variety of disciplines and design practice. In particular, it illuminates the ways in which typographic presentation is meaningful to readers, providing knowledge that document producers can use to communicate more effectively.

Typographic layout and first impressions: testing how changes in text layout influence reader's judgments of documents

This study explores how the typographic layout of information influences readers' impressions of magazine contents pages. Thirteen descriptors were used in a paired comparison procedure that assessed whether participants' rhetorical impressions of a set of six controlled documents change in relation to variations in layout. The combinations of layout attributes tested were derived from the structural attributes associated with three patterns of typographic differentiation (high, moderate, and low) described in a previous study (see Moys, 2014). The content and the range of stylistic attributes applied to the test material were controlled in order to focus on layout attributes. Triangulation of the quantitative and qualitative data indicates that, even within the experimental confines of limited stylistic differentiation, the layout attributes associated with patterns of high, moderate, and low typographic differentiation do influence readers' rhetorical judgments. In addition, the findings emphasize the importance of considering inter-relationships between clusters of typographic attributes rather than testing isolated variables.

Syk and Src family kinases regulate C-type lectin receptor 2 (CLEC-2)-mediated clustering of podoplanin and platelet adhesion to lymphatic endothelial cells

The interaction of C-type lectin receptor 2 (CLEC-2) on platelets with Podoplanin on lymphatic endothelial cells initiates platelet signaling events that are necessary for prevention of blood-lymph mixing during development. In the present study, we show that CLEC-2 signaling via Src family and Syk tyrosine kinases promotes platelet adhesion to primary mouse lymphatic endothelial cells at low shear. Using supported lipid bilayers containing mobile Podoplanin, we further show that activation of Src and Syk in platelets promotes clustering of CLEC-2 and Podoplanin. Clusters of CLEC-2-bound Podoplanin migrate rapidly to the center of the platelet to form a single structure. Fluorescence lifetime imaging demonstrates that molecules within these clusters are within 10 nm of one another and that the clusters are disrupted by inhibition of Src and Syk family kinases. CLEC-2 clusters are also seen in platelets adhered to immobilized Podoplanin using direct stochastic optical reconstruction microscopy. These findings provide mechanistic insight by which CLEC-2 signaling promotes adhesion to Podoplanin and regulation of Podoplanin signaling, thereby contributing to lymphatic vasculature development.

Conservation strategy maps: a tool to facilitate biodiversity action planning illustrated using the heath fritillary butterfly

1. The UK Biodiversity Action Plan (UKBAP) identifies invertebrate species in danger of national extinction. For many of these species, targets for recovery specify the number of populations that should exist by a specific future date but offer no procedure to plan strategically to achieve the target for any species. 2. Here we describe techniques based upon geographic information systems (GIS) that produce conservation strategy maps (CSM) to assist with achieving recovery targets based on all available and relevant information. 3. The heath fritillary Mellicta athalia is a UKBAP species used here to illustrate the use of CSM. A phase 1 habitat survey was used to identify habitat polygons across the county of Kent, UK. These were systematically filtered using relevant habitat, botanical and autecological data to identify seven types of polygon, including those with extant colonies or in the vicinity of extant colonies, areas managed for conservation but without colonies, and polygons that had the appropriate habitat structure and may therefore be suitable for reintroduction. 4. Five clusters of polygons of interest were found across the study area. The CSM of two of them are illustrated here: the Blean Wood complex, which contains the existing colonies of heath fritillary in Kent, and the Orlestone Forest complex, which offers opportunities for reintroduction. 5. Synthesis and applications. Although the CSM concept is illustrated here for the UK, we suggest that CSM could be part of species conservation programmes throughout the world. CSM are dynamic and should be stored in electronic format, preferably on the world-wide web, so that they can be easily viewed and updated. CSM can be used to illustrate opportunities and to develop strategies with scientists and non-scientists, enabling the engagement of all communities in a conservation programme. CSM for different years can be presented to illustrate the progress of a plan or to provide continuous feedback on how a field scenario develops.

Conservation strategy maps: a tool to facilitate biodiversity action planning illustrated using the heath fritillary butterfly

1. The UK Biodiversity Action Plan (UKBAP) identifies invertebrate species in danger of national extinction. For many of these species, targets for recovery specify the number of populations that should exist by a specific future date but offer no procedure to plan strategically to achieve the target for any species. 2. Here we describe techniques based upon geographic information systems (GIS) that produce conservation strategy maps (CSM) to assist with achieving recovery targets based on all available and relevant information. 3. The heath fritillary Mellicta athalia is a UKBAP species used here to illustrate the use of CSM. A phase 1 habitat survey was used to identify habitat polygons across the county of Kent, UK. These were systematically filtered using relevant habitat, botanical and autecological data to identify seven types of polygon, including those with extant colonies or in the vicinity of extant colonies, areas managed for conservation but without colonies, and polygons that had the appropriate habitat structure and may therefore be suitable for reintroduction. 4. Five clusters of polygons of interest were found across the study area. The CSM of two of them are illustrated here: the Blean Wood complex, which contains the existing colonies of heath fritillary in Kent, and the Orlestone Forest complex, which offers opportunities for reintroduction. 5. Synthesis and applications. Although the CSM concept is illustrated here for the UK, we suggest that CSM could be part of species conservation programmes throughout the world. CSM are dynamic and should be stored in electronic format, preferably on the world-wide web, so that they can be easily viewed and updated. CSM can be used to illustrate opportunities and to develop strategies with scientists and non-scientists, enabling the engagement of all communities in a conservation programme. CSM for different years can be presented to illustrate the progress of a plan or to provide continuous feedback on how a field scenario develops.

Linear predicted two-pass hexagonal algorithm with parallel implementation for motion estimation

This paper presents a paralleled Two-Pass Hexagonal (TPA) algorithm constituted by Linear Hashtable Motion Estimation Algorithm (LHMEA) and Hexagonal Search (HEXBS) for motion estimation. In the TPA., Motion Vectors (MV) are generated from the first-pass LHMEA and are used as predictors for second-pass HEXBS motion estimation, which only searches a small number of Macroblocks (MBs). We introduced hashtable into video processing and completed parallel implementation. We propose and evaluate parallel implementations of the LHMEA of TPA on clusters of workstations for real time video compression. It discusses how parallel video coding on load balanced multiprocessor systems can help, especially on motion estimation. The effect of load balancing for improved performance is discussed. The performance or the algorithm is evaluated by using standard video sequences and the results are compared to current algorithms.

Paralelled Two-Pass Hexagonal algorithm for motion estimation

This paper presents a paralleled Two-Pass Hexagonal (TPA) algorithm constituted by Linear Hashtable Motion Estimation Algorithm (LHMEA) and Hexagonal Search (HEXBS) for motion estimation. In the TPA, Motion Vectors (MV) are generated from the first-pass LHMEA and are used as predictors for second-pass HEXBS motion estimation, which only searches a small number of Macroblocks (MBs). We introduced hashtable into video processing and completed parallel implementation. We propose and evaluate parallel implementations of the LHMEA of TPA on clusters of workstations for real time video compression. It discusses how parallel video coding on load balanced multiprocessor systems can help, especially on motion estimation. The effect of load balancing for improved performance is discussed. The performance of the algorithm is evaluated by using standard video sequences and the results are compared to current algorithms.

Two-pass hexagonal algorithm with parallel implementation for video coding

This paper presents a paralleled Two-Pass Hexagonal (TPA) algorithm constituted by Linear Hashtable Motion Estimation Algorithm (LHMEA) and Hexagonal Search (HEXBS) for motion estimation. In the TPA, Motion Vectors (MV) are generated from the first-pass LHMEA and are used as predictors for second-pass HEXBS motion estimation, which only searches a small number of Macroblocks (MBs). We introduced hashtable into video processing and completed parallel implementation. We propose and evaluate parallel implementations of the LHMEA of TPA on clusters of workstations for real time video compression. It discusses how parallel video coding on load balanced multiprocessor systems can help, especially on motion estimation. The effect of load balancing for improved performance is discussed. The performance of the algorithm is evaluated by using standard video sequences and the results are compared to current algorithms.

Improved two-pass hexagonal algorithm with parallel implementation for video coding - art. no. 60630J

This paper presents an improved parallel Two-Pass Hexagonal (TPA) algorithm constituted by Linear Hashtable Motion Estimation Algorithm (LHMEA) and Hexagonal Search (HEXBS) for motion estimation. Motion Vectors (MV) are generated from the first-pass LHMEA and used as predictors for second-pass HEXBS motion estimation, which only searches a small number of Macroblocks (MBs). We used bashtable into video processing and completed parallel implementation. The hashtable structure of LHMEA is improved compared to the original TPA and LHMEA. We propose and evaluate parallel implementations of the LHMEA of TPA on clusters of workstations for real time video compression. The implementation contains spatial and temporal approaches. The performance of the algorithm is evaluated by using standard video sequences and the results are compared to current algorithms.

Video activity extraction and reporting with incremental unsupervised learning

The present work presents a new method for activity extraction and reporting from video based on the aggregation of fuzzy relations. Trajectory clustering is first employed mainly to discover the points of entry and exit of mobiles appearing in the scene. In a second step, proximity relations between resulting clusters of detected mobiles and contextual elements from the scene are modeled employing fuzzy relations. These can then be aggregated employing typical soft-computing algebra. A clustering algorithm based on the transitive closure calculation of the fuzzy relations allows building the structure of the scene and characterises the ongoing different activities of the scene. Discovered activity zones can be reported as activity maps with different granularities thanks to the analysis of the transitive closure matrix. Taking advantage of the soft relation properties, activity zones and related activities can be labeled in a more human-like language. We present results obtained on real videos corresponding to apron monitoring in the Toulouse airport in France.