An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

An O(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn).All the algorithms currently known for constructing a Gomory-Hu tree [8,9] use n-1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest Õ(n20/9) max flow algorithm due to Karger and Levine [11] yields the current best running time of Õ(n20/9n) for Gomory-Hu tree construction on simpleunweighted graphs with m edges and n vertices. Thus we present the first Õ(mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs.We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S ⊆ V can be reused for computing a minimum Steiner cut for certain Steiner sets S' ⊆ S.

Unsupervised intra-lingual and cross-lingual speaker adaptation for HMM-based speech synthesis using two-pass decision tree construction

Hidden Markov model (HMM)-based speech synthesis systems possess several advantages over concatenative synthesis systems. One such advantage is the relative ease with which HMM-based systems are adapted to speakers not present in the training dataset. Speaker adaptation methods used in the field of HMM-based automatic speech recognition (ASR) are adopted for this task. In the case of unsupervised speaker adaptation, previous work has used a supplementary set of acoustic models to estimate the transcription of the adaptation data. This paper first presents an approach to the unsupervised speaker adaptation task for HMM-based speech synthesis models which avoids the need for such supplementary acoustic models. This is achieved by defining a mapping between HMM-based synthesis models and ASR-style models, via a two-pass decision tree construction process. Second, it is shown that this mapping also enables unsupervised adaptation of HMM-based speech synthesis models without the need to perform linguistic analysis of the estimated transcription of the adaptation data. Third, this paper demonstrates how this technique lends itself to the task of unsupervised cross-lingual adaptation of HMM-based speech synthesis models, and explains the advantages of such an approach. Finally, listener evaluations reveal that the proposed unsupervised adaptation methods deliver performance approaching that of supervised adaptation.

Scalable Overlay Multicast Tree Construction for QoS-Constrained Media Streaming

Overlay networks have become popular in recent times for content distribution and end-system multicasting of media streams. In the latter case, the motivation is based on the lack of widespread deployment of IP multicast and the ability to perform end-host processing. However, constructing routes between various end-hosts, so that data can be streamed from content publishers to many thousands of subscribers, each having their own QoS constraints, is still a challenging problem. First, any routes between end-hosts using trees built on top of overlay networks can increase stress on the underlying physical network, due to multiple instances of the same data traversing a given physical link. Second, because overlay routes between end-hosts may traverse physical network links more than once, they increase the end-to-end latency compared to IP-level routing. Third, algorithms for constructing efficient, large-scale trees that reduce link stress and latency are typically more complex. This paper therefore compares various methods to construct multicast trees between end-systems, that vary in terms of implementation costs and their ability to support per-subscriber QoS constraints. We describe several algorithms that make trade-offs between algorithmic complexity, physical link stress and latency. While no algorithm is best in all three cases we show how it is possible to efficiently build trees for several thousand subscribers with latencies within a factor of two of the optimal, and link stresses comparable to, or better than, existing technologies.

Efficient tree construction for the multicast problem

A new heuristic for the Steiner Minimal Tree problem is presented here. The method described is based on the detection of particular sets of nodes in networks, the “Hot Spot” sets, which are used to obtain better approximations of the optimal solutions. An algorithm is also proposed which is capable of improving the solutions obtained by classical heuristics, by means of a stirring process of the nodes in solution trees. Classical heuristics and an enumerative method are used CIS comparison terms in the experimental analysis which demonstrates the goodness of the heuristic discussed in this paper.

Efficient tree construction for the multicast problem

A new heuristic for the Steiner minimal tree problem is presented. The method described is based on the detection of particular sets of nodes in networks, the “hot spot” sets, which are used to obtain better approximations of the optimal solutions. An algorithm is also proposed which is capable of improving the solutions obtained by classical heuristics, by means of a stirring process of the nodes in solution trees. Classical heuristics and an enumerative method are used as comparison terms in the experimental analysis which demonstrates the capability of the heuristic discussed

Extension of the Huffman tree construction algorithm /

Bibliography: p. 42-43.

Comparison of two construction algorithms for local model networks

The divide-and-conquer approach of local model (LM) networks is a common engineering approach to the identification of a complex nonlinear dynamical system. The global representation is obtained from the weighted sum of locally valid, simpler sub-models defined over small regions of the operating space. Constructing such networks requires the determination of appropriate partitioning and the parameters of the LMs. This paper focuses on the structural aspect of LM networks. It compares the computational requirements and performances of the Johansen and Foss (J&F) and LOLIMOT tree-construction algorithms. Several useful and important modifications to each algorithm are proposed. The modelling performances are evaluated using real data from a pilot plant of a pH neutralization process. Results show that while J&F achieves a more accurate nonlinear representation of the pH process, LOLIMOT requires significantly less computational effort.

Vectorized algorithms for quadtree construction and descent

This paper presents vectorized methods of construction and descent of quadtrees that can be easily adapted to message passing parallel computing. A time complexity analysis for the present approach is also discussed. The proposed method of tree construction requires a hash table to index nodes of a linear quadtree in the breadth-first order. The hash is performed in two steps: an internal hash to index child nodes and an external hash to index nodes in the same level (depth). The quadtree descent is performed by considering each level as a vector segment of a linear quadtree, so that nodes of the same level can be processed concurrently. © 2012 Springer-Verlag.

A provably tight delay-driven concurrently congestion mitigating global routing algorithm

Routing is a very important step in VLSI physical design. A set of nets are routed under delay and resource constraints in multi-net global routing. In this paper a delay-driven congestion-aware global routing algorithm is developed, which is a heuristic based method to solve a multi-objective NP-hard optimization problem. The proposed delay-driven Steiner tree construction method is of O(n(2) log n) complexity, where n is the number of terminal points and it provides n-approximation solution of the critical time minimization problem for a certain class of grid graphs. The existing timing-driven method (Hu and Sapatnekar, 2002) has a complexity O(n(4)) and is implemented on nets with small number of sinks. Next we propose a FPTAS Gradient algorithm for minimizing the total overflow. This is a concurrent approach considering all the nets simultaneously contrary to the existing approaches of sequential rip-up and reroute. The algorithms are implemented on ISPD98 derived benchmarks and the drastic reduction of overflow is observed. (C) 2014 Elsevier Inc. All rights reserved.

J48Consolidated: an implementation of CTC algorithm for WEKA

The CTC algorithm, Consolidated Tree Construction algorithm, is a machine learning paradigm that was designed to solve a class imbalance problem, a fraud detection problem in the area of car insurance [1] where, besides, an explanation about the classification made was required. The algorithm is based on a decision tree construction algorithm, in this case the well-known C4.5, but it extracts knowledge from data using a set of samples instead of a single one as C4.5 does. In contrast to other methodologies based on several samples to build a classifier, such as bagging, the CTC builds a single tree and as a consequence, it obtains comprehensible classifiers. The main motivation of this implementation is to make public and available an implementation of the CTC algorithm. With this purpose we have implemented the algorithm within the well-known WEKA data mining environment http://www.cs.waikato.ac.nz/ml/weka/). WEKA is an open source project that contains a collection of machine learning algorithms written in Java for data mining tasks. J48 is the implementation of C4.5 algorithm within the WEKA package. We called J48Consolidated to the implementation of CTC algorithm based on the J48 Java class.

Systematics and evolution of the genus Deuterocohnia Mez (Bromeliaceae)

The present study investigates the systematics and evolution of the Neotropical genus Deuterocohnia Mez (Bromeliaceae). It provides a comprehensive taxonomic revision as well as phylogenetic analyses based on chloroplast and nuclear DNA sequences and presents a hypothesis on the evolution of the genus. A broad morphological, anatomical, biogeographical and ecological overview of the genus is given in the first part of the study. For morphological character assessment more than 700 herbarium specimens from 39 herbaria as well as living plant material in the field and in the living collections of botanical gardens were carefully examined. The arid habitats, in which the species of Deuterocohnia grow, are reflected by the morphological and anatomical characters of the species. Important characters for species delimitation were identified, like the length of the inflorescence, the branching order, the density of flowers on partial inflorescences, the relation of the length of the primary bracts to that of the partial inflorescence, the sizes of floral bracts, sepals and petals, flower colour, the presence or absence of a pedicel, the curvature of the stamina and the petals during anthesis. After scrutinizing the nomenclatural history of the taxa belonging to Deuterocohnia – including the 1992 syonymized genus Abromeitiella – 17 species, 4 subspecies and 4 varieties are accepted in the present revision. Taxonomic changes were made in the following cases: (I) New combinations: A. abstrusa (A. Cast.) N. Schütz is re-established – as defined by Castellanos (1931) – and transfered to D. abstrusa; D. brevifolia (Griseb.) M.A. Spencer & L.B. Sm. includes accessions of the former D. lorentziana (Mez) M.A. Spencer & L.B. Sm., which are not assigned to D. abstrusa; D. bracteosa W. Till is synonymized to D. strobilifera Mez; D. meziana Kuntze ex Mez var. carmineo-viridiflora Rauh is classified as a subspecies of D. meziana (ssp. carmineo-viridiflora (Rauh) N. Schütz); D. pedicellata W. Till is classified as a subspecies of D. meziana (ssp. pedicellata (W. Till) N. Schütz); D. scapigera (Rauh & L. Hrom.) M.A. Spencer & L.B. Sm ssp. sanctae-crucis R. Vásquez & Ibisch is classified as a species (D. sanctae-crucis (R. Vásquez & Ibisch) N. Schütz); (II) New taxa: a new subspecies of D. meziana Kuntze ex Mez is established; a new variety of D. scapigera is established; (the new taxa will be validly published elsewhere); (III) New type: an epitype for D. longipetala was chosen. All other species were kept according to Spencer and Smith (1992) or – in the case of more recently described species – according to the protologue. Beside the nomenclatural notes and the detailed descriptions, information on distribution, habitat and ecology, etymology and taxonomic delimitation is provided for the genus and for each of its species. An key was constructed for the identification of currently accepted species, subspecies and varieties. The key is based on easily detectable morphological characters. The former synonymization of the genus Abromeitiella into Deuterocohnia (Spencer and Smith 1992) is re-evalutated in the present study. Morphological as well as molecular investigations revealed Deuterocohnia incl. Abromeitiella as being monophyletic, with some indications that a monophyletic Abromeitiella lineage arose from within Deuterocohnia. Thus the union of both genera is confirmed. The second part of the present thesis describes and discusses the molecular phylogenies and networks. Molecular analyses of three chloroplast intergenic spacers (rpl32-trnL, rps16-trnK, trnS-ycf3) were conducted with a sample set of 119 taxa. This set included 103 Deuterocohnia accessions from all 17 described species of the genus and 16 outgroup taxa from the remainder of Pitcairnioideae s.str. (Dyckia (8 sp.), Encholirium (2 sp.), Fosterella (4 sp.) and Pitcairnia (2 sp.)). With its high sampling density, the present investigation by far represents the most comprehensive molecular study of Deuterocohnia up till now. All data sets were analyzed separately as well as in combination, and various optimality criteria for phylogenetic tree construction were applied (Maximum Parsimony, Maximum Likelihood, Bayesian inferences and the distance method Neighbour Joining). Congruent topologies were generally obtained with different algorithms and optimality criteria, but individual clades received different degrees of statistical support in some analyses. The rps16-trnK locus was the most informative among the three spacer regions examined. The results of the chloroplast DNA analyses revealed a highly supported paraphyly of Deuterocohnia. Thus, the cpDNA trees divide the genus into two subclades (A and B), of which Deuterocohnia subclade B is sister to the included Dyckia and Encholirium accessions, and both together are sister to Deuterocohnia subclade A. To further examine the relationship between Deuterocohnia and Dyckia/Encholirium at the generic level, two nuclear low copy markers (PRK exon2-5 and PHYC exon1) were analysed with a reduced taxon set. This set included 22 Deuterocohnia accessions (including members of both cpDNA subclades), 2 Dyckia, 2 Encholirium and 2 Fosterella species. Phylogenetic trees were constructed as described above, and for comparison the same reduced taxon set was also analysed at the three cpDNA data loci. In contrast to the cpDNA results, the nuclear DNA data strongly supported the monophyly of Deuterocohnia, which takes a sister position to a clade of Dyckia and Encholirium samples. As morphology as well as nuclear DNA data generated in the present study and in a former AFLP analysis (Horres 2003) all corroborate the monophyly of Deuterocohnia, the apparent paraphyly displayed in cpDNA analyses is interpreted to be the consequence of a chloroplast capture event. This involves the introgression of the chloroplast genome from the common ancestor of the Dyckia/ Encholirium lineage into the ancestor of Deuterocohnia subclade B species. The chloroplast haplotypes are not species-specific in Deuterocohnia. Thus, one haplotype was sometimes shared by several species, where the same species may harbour different haplotypes. The arrangement of haplotypes followed geographical patterns rather than taxonomic boundaries, which may indicate some residual gene flow among populations from different Deuteroccohnia species. Phenotypic species coherence on the background of ongoing gene flow may then be maintained by sets of co-adapted alleles, as was suggested by the porous genome concept (Wu 2001, Palma-Silva et al. 2011). The results of the present study suggest the following scenario for the evolution of Deuterocohnia and its species. Deuterocohnia longipetala may be envisaged as a representative of the ancestral state within the genus. This is supported by (1) the wide distribution of this species; (2) the overlap in distribution area with species of Dyckia; (3) the laxly flowered inflorescences, which are also typical for Dyckia; (4) the yellow petals with a greenish tip, present in most other Deuterocohnia species. The following six extant lineages within Deuterocohnia might have independently been derived from this ancestral state with a few changes each: (I) D. meziana, D. brevispicata and D. seramisiana (Bolivia, lowland to montane areas, mostly reddish-greenish coloured, very laxly to very densely flowered); (II) D. strobilifera (Bolivia, high Andean mountains, yellow flowers, densely flowered); (III) D. glandulosa (Bolivia, montane areas, yellow-greenish flowers, densely flowered); (IV) D. haumanii, D. schreiteri, D. digitata, and D. chrysantha (Argentina, Chile, E Andean mountains and Atacama desert, yellow-greenish flowers, densely flowered); (V) D. recurvipetala (Argentina, foothills of the Andes, recurved yellow flowers, laxly flowered); (VI) D. gableana, D. scapigera, D. sanctae-crucis, D. abstrusa, D. brevifolia, D. lotteae (former Abromeitiella species, Bolivia, Argentina, higher Andean mountains, greenish-yellow flowers, inflorescence usually simple). Originating from the lower montane Andean regions, at least four lineages of the genus (I, II, IV, VI) adapted in part to higher altitudes by developing densely flowered partial inflorescences, shorter flowers and – in at least three lineages (II, IV, VI) – smaller rosettes, whereas species spreading into the lowlands (I, V) developed larger plants, laxly flowered, amply branched inflorescences and in part larger flowers (I).

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.