Search

We introduce the random exponential binary tree (EBT) and study its profile. As customary, the tree is extended by padding each leaf node (considered internal), with the appropriate number of external nodes, so that the outdegree of every internal node is made equal to 2. In a random EBT, at every step, each external node is promoted to an internal node with probability p, stays unchanged with probability 1 - p, and the resulting tree is extended. We study the internal and external profiles of a random EBT and get exact expectations for the numbers of internal and external nodes at each level. Asymptotic analysis shows that the average external profile is richest at level $\frac {2p}{p+1}n$ , and it experiences phase transitions at levels a n, where the a’s are the solutions to an algebraic equation. The rates of convergence themselves go through an infinite number of phase changes in the sublinear range, and then again at the nearly linear levels.

Half a century ago, Chow and Liu proved that the distribution of the first-order dependence tree that optimally approximates an arbitrary joint distribution in terms of Kullback–Leibler cross entropy is the distribution of the maximum-weight dependence tree (MWDT). In a $p$ -dimensional space, this is a tree with $p-1$ branches between pairs of variables with each branch having a weight equal to the mutual information between variables at both ends. Today, MWDTs have applications that are more important in classification than only being used to model first-order dependence structure among variables. Nevertheless, whether the MWDT is the optimal first-order tree in classification has been left unexplored so far. In this letter, we study the optimality of the MWDT structure from the stand-point of classification.

For the performance and maintenance cost of the existing index methods, this paper presents a distributed multi access entrance B+ tree index method, which has some features that are important in practice, namely (1) achieve efficient parallel interval queries, and (2) and low maintenance cost for index structure. Our scheme relies on four key techniques to achieve efficient parallel interval queries and low maintenance cost for index structure: (1) It gives a routing table to each leaf node of distributed B+ tree, so as to interval search can be completed from any leaf node of any storage node and break through the Bottleneck caused by the root node in the distributed B+ tree; (2) It construction of balanced binary tree in different levels of a node, and choose select the relevant nodes for its routing table; (3) It uses the layer-by-layer transitivity of B+ tree node splitting information to sense node split position so as to only update routing information within subtree of corresponding particle at the time of node splitting; (4) it uses balanced structure of B+ trees to realize only update the single route information of relevant nodes at the time of node splitting, without adjusting the route tables in a large area. Our scheme has been implemented and evaluated, and the performance results are encouraging.

Sensor nodes observing events, occurring in close proximity, gather data that are highly co-related. This work uses a polynomial regression technique to exploit the spatial correlation of the data in a three dimensional sensor network. The sensing nodes, sense the physical attribute and report their position coordinates (x, y, z) and the sensed value to the nearest tree node. Another set of nodes, categorized as the tree nodes, are responsible for generating a polynomial function of the received data and transmit the coefficients of regression to the parent tree node. The approach proceeds from the bottom to the top. The query from the sink, receives a polynomial function which is generated by the root node of the tree in each cluster to compute the attribute value at any location within the boundary. The proposed approach aims to save a lot of energy in the sensor network. Simulations, performed for different tree heights, indicate that a tree with a depth of four gives the best results.

Some apparently different VLSI circuit design optimization problems can be mapped to the problem of allocating weights (hardware circuits) to the nodes of a tree, such that their total sum (delay) along root-to-leaf paths, or their total product (amplification) along root-to-leaf paths, satisfy given demands (delays or amplifications, respectively) at the tree's leaves. Node's weight is shared by all the leaves of its emanating sub-tree. For both the sum and product constraints cases, $$O(n)$$O(n) weights allocation algorithms are presented, supplying the demands at the leaves, while the total sum of nodes' weights (hardware cost) is minimized. When the assignment of the demands to leaves is not predetermined, it is shown that monotonic order of the demands at leaves is optimal for both cases.

We describe a general technique for obtaining provably correct, non-blocking implementations of a large class of tree data structures where pointers are directed from parents to children. Updates are permitted to modify any contiguous portion of the tree atomically. Our non-blocking algorithms make use of the LLX, SCX and VLX primitives, which are multi-word generalizations of the standard LL, SC and VL primitives and have been implemented from single-word CAS. To illustrate our technique, we describe how it can be used in a fairly straightforward way to obtain a non-blocking implementation of a chromatic tree, which is a relaxed variant of a red-black tree. The height of the tree at any time is O(c + log n), where n is the number of keys and c is the number of updates in progress. We provide an experimental performance analysis which demonstrates that our Java implementation of a chromatic tree rivals, and often significantly outperforms, other leading concurrent dictionaries.

Tree data structure works great in representing computations unambiguously. In this study, the researchers enhanced the existing insert algorithm in B*Tree by introducing an expanded algorithm for inserting key values in B*Tree. This would further delay, if not reduce redistribution and frequency of splitting nodes in B*Tree. The idea of the expanded algorithm is to check for a cousin node within the same level that can accommodate a key value from its nearest sibling. A cascading effect is expected until the nearest sibling of the overflowing node can accommodate a key value with the premise that the nearest siblings of the overflowing node are full. Exploring the potential of this algorithm can really simplify a complex problem. The expanded insert algorithm would ensure that all leaf nodes in the B*Tree would be full and not just 2/3 full before a redistribution process is to be performed. Thus, reducing the nodes used in a B*Tree that would result to a far more favorable priori and posteriori estimates.

HighlightsI proposed an oblique survival tree that is able to cope with right-censored data.The induction algorithm is based on the minimization of the CPL criterion functions.A split-complexity measure with a 10-fold cross-validation was used to prune a tree.The predictive ability of the method was evaluated using synthetic and real data.The outcomes were compared with two existing univariate tree models.The obtained survival trees are small and offer a good predictive ability. ObjectiveRecursive partitioning is a common, assumption-free method of survival data analysis. It focuses mainly on univariate trees, which use splits based on a single variable in each internal node. In this paper, I provide an extension of an oblique survival tree induction technique, in which axis-parallel splits are replaced by hyperplanes, dividing the feature space into areas with a homogeneous survival experience. Method and materialsThe proposed tree induction algorithm consists of two steps. The first covers the induction of a large tree with internal nodes represented by hyperplanes, whose positions are calculated by the minimization of a piecewise-linear criterion function, the dipolar criterion. The other phase uses a split-complexity algorithm to prune unnecessary tree branches and a 10-fold cross-validation technique to choose the best tree. The terminal nodes of the final tree are characterised by KaplanMeier survival functions. A synthetic data set was used to test the performance, while seven real data sets were exploited to validate the proposed method. ResultsThe evaluation of the method was focused on two features: predictive ability and tree size. These were compared with two univariate tree models: the conditional inference tree and recursive partitioning for survival trees, respectively. The comparison of the predictive ability, expressed as an integrated Brier score, showed no statistically significant differences (p=0.486) among the three methods. Similar results were obtained for the tree size (p=0.11), which was calculated as a median value over 20 runs of a 10-fold cross-validation. ConclusionsThe predictive ability of trees generated using piecewise-linear criterion functions is comparable to that of univariate tree-based models. Although a similar conclusion may be drawn from the analysis of the tree size, in the majority of the studied cases, the number of nodes of the dipolar tree is one of the smallest among all the methods.

Given a tree with n nodes, we consider the problem of finding the most profitable subtree of that tree with at most K nodes which is known as the Cardinality Subtree of a Tree Problem. We present a new exact linear extended formulation with O(nK) two-indexed variables and O(nK) constraints.

Determining the optimal location of a switching center in a tree network of users is accurately modeled by the median problem. A real-time approach is used in this paper to investigate the dynamics of such a communication network in two cases: (1) a growing tree of nodes associated with equal demand rates, and (2) a stream of corrections that arbitrarily change the demand rates at the nodes. The worst-case analysis performed in both situations clearly demonstrates the importance of parallelism in such real-time paradigms. It is shown that the error generated by the best sequential algorithm in the first case can be arbitrarily large. A synergistic behavior is revealed when the quality-up is investigated in the second case.

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of: the generalized Bethe tree B, a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B, a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices, a graph obtained from the cycle Cr by attaching B, by its root, to each vertex of the cycle, and a tree obtained from the path Pr by attaching B, by its root, to each vertex of the path, is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.

The Quality of Service Multicast Tree Problem is a generalization of the Steiner tree problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the source to non-zero rate nodes is l · re, where re is the maximum node rate in the component of T-{e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.212 for the case of an unbounded number of rates. In this paper we give improved approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for an unbounded number of rates are reduced to 2.414 and 4.311, respectively.

A multiple bus network (MBN) connects a set of processors via set of buses. Two important parameters of an MBN are its loading (largest number of connections on a bus) and its degree (largest number of connections to a processor). These parameters determine the cost, speed, and implementability of the MBN. The smallest degree that any useful MBN can have is 2. In this paper, we study the relationship between running time, degree, and loading of degree-2 MBNs running a fundamental class of algorithms called binary tree algorithms. (A binary tree algorithm reduces 2/sup n/ inputs at the leaves of a balanced-binary tree to a single result at the root of the tree.) Specifically, we establish a nontrivial /spl Omega/(n/logn) loading lower bound for any degree-2 MBN running a 2/sup n/ input binary tree algorithm optimally in n steps. We show that this bound does not hold if the restriction on the degree or the running time is relaxed. That is, optimal-time, degree-3, constant loading MBNs and suboptimal-time, degree-2, constant loading MBNs exist for binary tree algorithms. We also derive a lower bound on the additional time (beyond the optimal) needed to run binary tree algorithms on a degree-2, loading-L MBN, for any L>3.

In many tree-structured parallel computations, the size and structure of a tree that represents a parallel computation is unpredictable at compile-time; the tree evolves gradually during the course of the computation. When such a computation is performed on a static network, the dynamic tree embedding problem is to distribute the tree nodes to the processors of the network such that all the processors receive roughly the same amount of load and that communicating nodes are assigned to neighboring processors. Furthermore, when a new tree node is generated, it should be immediately assigned to a processor for execution without any information on the further evolving of the tree; and load distribution is performed by all processors in a totally distributed fashion. We study the problem of embedding dynamically evolving trees in hypercubic networks, including shuffle-exchange, de Bruijn, cube-connected cycles, wrapped butterfly, and hypercube networks. The performance of a random-walk-based randomized tree embedding algorithm is evaluated. Several random tree models are considered. We develop recurrence relations for analyzing the performance of embedding of complete-tree-based random trees and randomized complete trees, and linear systems of equations for reproduction trees. We present more efficient recurrence relations and linear systems of equations for symmetric networks. We also demonstrate extensive numerical data of the performance ratio and make a number of interesting observations of randomized tree embedding in the five hypercubic networks. Copyright © 2004 John Wiley & Sons, Ltd.

We consider a problem of cost-constrained minimum-delay multicasting in a network, which is to find a Steiner tree spanning the source and destination nodes such that the maximum total delay along a path from the source node to a destination node is minimized, while the sum of link costs in the tree is bounded by a constant. The problem is $\mathcal{NP}$-hard even if the network is series-parallel. We present a fully polynomial time approximation scheme for the problem if the network is series-parallel.

A new neural tree model, called adaptive high-order neural tree (AHNT), is proposed for classifying large sets of multidimensional patterns. The AHNT is built by recursively dividing the training set into subsets and by assigning each subset to a different child node. Each node is composed of a high-order perceptron (HOP) whose order is automatically tuned taking into account the complexity of the pattern set reaching that node. First-order nodes divide the input space with hyperplanes, while HOPs divide the input space arbitrarily, but at the expense of increased complexity. Experimental results demonstrate that the AHNT generalizes better than trees with homogeneous nodes, produces small trees and avoids the use of complex comparative statistical tests and/or a priori selection of large parameter sets.

A path reversal is performed in a rooted tree when a node becomes the root of all the nodes along the path from it to the former root. This algorithm on trees is presented as a transition system specified by induction over a convenient view of the tree structure. When each tree node is assigned a fixed weight representing its relative probability to move to the root, the transition system defines a finite Markov chain. This paper presents some of its asymptotic properties. A closed formula for the stationary distribution and a tight upper bound for the average computational complexity of path reversal are also given as new results.

Let ? d be a homogeneous tree in which every vertex has d + 1 neighbours, where d≥ 2. The contact process on such a tree is known to have three distinct phases. We consider the process on a finite subtree, namely the rooted tree of depth h and branching factor d, and relate the behaviour of the process on the infinite tree to its behaviour on the finite tree for large h. In the phase of strong survival, we show that with probability ɛ independent of h, the process on the subtree starting from a single infection survives for a time which is doubly exponential in h and almost exponential in the number of vertices of the finite tree. In the phase of weak survival on the infinite tree, the survival time on the finite tree is approximately linear in h. In the phase of no survival, the survival time on the finite tree is linear in h if one starts with all vertices initially infected, and bounded by a random variable (independent of h) with an exponential tail if one starts from a single infection.

We consider the problem of placing copies of objects in a tree network in order to minimize the cost of servicing read and write requests to objects when the tree nodes have limited storage and the number of copies permitted is limited. The set of nodes that have a copy of the object is the residence set of the object. A node wishing to read the object will read the object from the closest node in the residence set. A node wishing to update the object will update the copy of the object at all the nodes in the residence set. Updates are propagated over a certain minimum spanning tree. The cost associated with a residence set equals the cost of servicing all the read and write requests and the storage costs for those copies. We describe an O(n/sup 3/p/sup 2/)-time algorithm for finding an optimal residence set of size p for an object in a tree with n nodes, taking into consideration the read, write, and storage costs. Furthermore, we describe a O(n/sup 3/p/sup 2//spl Lambda//sub max//sup 2/)-time algorithm for finding a minimum cost normal p-residence set for an object in a tree, this time also taking into account the load imposed by the nodes of the tree on the nodes in a residence set and their capacity constraints, where /spl Lambda//sub max/ is an upper bound on the capacity of each node of the tree.

There are many parallel computations that are tree structured. The structure of a tree is usually unpredictable at compiler-time; the tree grows gradually during the course of a computation. The dynamic tree embedding problem is to distribute the processes of a parallel computation over processors in a parallel computer such that processors perform roughly the same amount of computation, and that communicating processes are assigned to processors that are close to each other. In this paper, we establish lower bounds for the performance ratio of dynamic tree embedding in bipartite static networks, including numerous important networks such asn-dimensional meshes,n-dimensional tori,k-aryn-cubes, cube-connected cycles, and butterflies. Our lower bounds are obtained from both tree and network properties and are applicable to a general class of dynamic tree embedding algorithms.

The tree-layout problem is to compute the coordinates of nodes of a tree so that the tree, when drawn on a piece of paper, appeals to human understanding. The tree-layout problem, which seems inherently sequential at the first glance, can be solved with a data-parallel algorithm. It takes O( height × log width ) time on width processors when proper communication links between processors are available, where height and width are the height and width of the tree, respectively. The layout calculated by the algorithm has the minimum width.

In this work we introduce and study various generalizations of the notion of increasingly labelled trees, where the label of a child node is always larger than the label of its parent node, to multilabelled tree families, where the nodes in the tree can get multiple labels. For all tree classes we show characterizations of suitable generating functions for the tree enumeration sequence via differential equations. Furthermore, for several combinatorial classes of multilabelled increasing tree families we present explicit enumeration results. We also present multilabelled increasing tree families of an elliptic nature, where the exponential generating function can be expressed in terms of the Weierstrass-p function or the lemniscate sine function. Furthermore, we show how to translate enumeration formulas for multilabelled increasing trees into hook-length formulas for trees and present a general "reverse engineering" method to discover hook-length formulas associated to such tree families., Comment: 37 pages

In this paper, we propose and analyze a simple localized algorithm to balance a tree. The motivation comes from live distributed streaming systems in which a source diffuses a content to peers via a tree, a node forwarding the data to its children. Such systems are subject to a high churn, peers frequently joining and leaving the system. It is thus crucial to be able to repair the diffusion tree to allow an efficient data distribution. In particular, due to bandwidth limitations, an efficient diffusion tree must ensure that node degrees are bounded. Moreover, to minimize the delay of the streaming, the depth of the diffusion tree must also be controlled. We propose here a simple distributed repair algorithm in which each node carries out local operations based on its degree and on the subtree sizes of its children. In a synchronous setting, we first prove that starting from any n-node tree our process converges to a balanced tree in O(n2) turns. We then describe a more restrictive model, adding a small extra information to each node, for which the convergence is reached in O(n log n) turns and this bound is tight. We then exhibit by simulation that the convergence is much faster (logarithmic number of turns in average) for a random tree.; Dans cet article, nous proposons et analysons un algorithme local simple pour ́equilibrer un arbre. La motivation vient des syst'emes distribu ́es de diffusion en temps r ́eel, dans lesquels une source diffuse un contenu vers des r ́ecepteurs via un arbre, un noeud transmettant les donn ́ees 'a ses enfants. Ces syst'emes sont soumis 'a un niveau ́elev ́e d'arriv ́ees et de d ́eparts (churn). Il est donc crucial d'ˆetre en mesure de r ́eparer efficacement l'arbre de diffusion afin de permettre une distribution efficace des donn ́ees. En particulier, en raison de limitations de bande passante, un arbre de diffusion efficace doit veiller 'a ce que les degr ́es des noeuds soient born ́es. Par ailleurs, pour minimiser le d ́elai de la diffusion en continu, la profondeur de l'arbre de diffusion doit ́egalement ˆetre contrˆol ́ee. Nous proposons ici un algorithme de r ́eparation distribu ́e simple dans lequel chaque nœud ex ́ecute des op ́erations locales en fonction de son degr ́e et de la taille des sous-arbres de ses enfants. Dans un cadre synchrone, nous montrons tout d'abord, qu''a partir de n'importe quel arbre avec n nœuds, notre processus converge vers un arbre ́equilibr ́e en O(n2) tours. Nous d ́ecrivons ensuite un mod'ele plus restrictif, en ajoutant une petite information suppl ́ementaire pour chaque nœud, pour lequel la convergence est atteinte en O(n log n) tours, cette borne ́etant serr ́ee. Nous mettons ensuite en ́evidence par simulation que la con- vergence est beaucoup plus rapide (nombre logarithmique de tours en moyenne) pour un arbre al ́eatoire.

We consider the distributed detection problem in trees with unbounded height. The first configuration we studied in this report is a balanced binary relay tree, where the leaves of the tree correspond to N identical and independent sensors. Only the leaves are sensors. The root of the tree represents a fusion center that makes the overall detection decision. Each of the other nodes in the tree are relay nodes that combine two binary messages to form a single output binary message. In this way, the information from the sensors is aggregated into the fusion center via the relay nodes. In Chapter II, we assume that the fusion rules are the unit-threshold likelihood-ratio test which are locally optimal in the sense of minimizing the total error probability after fusion. We describe the evolution of the Type I and Type II error probabilities of the binary data as it propagates from the leaves towards the root. Tight upper and lower bounds for the total error probability at the fusion center as functions of N are derived. These characterize how fast the total error probability converges to 0 with respect to N, even if the individual sensors have error probabilities that converge to 1/2.

Tree compression can be applied to the table of the index space that is used for the index method (image inspection method). The author presents a method of compressing a one-dimensional string of quantized data that contains significant sequences of blocks. The data are equally divided into small areas and, if significant data exists, “1” is used to show its existence and division is performed for lower layers. Significant data are copied to the lowest layers. First, an equation to decide a two-layer tree construction is obtained by considering the probability of the existence of significant data. Then by expanding the equation to a multilayer tree construction, equations are obtained that decide the optimal construction (number of layers and divisions) that minimizes memory. Examples for optimal tree construction are calculated for various data sizes. The relationship between the optimal tree and e is shown. Finally, variations of methods for applying the tree construction to the index space are shown using a sample image data and the validity of the method is confirmed.

We study the distributed detection problem in the context of a balanced binary relay tree, where the leaves of the tree correspond to $N$ identical and independent sensors generating binary messages. The root of the tree is a fusion center making an overall decision. Every other node is a relay node that aggregates the messages received from its child nodes into a new message and sends it up toward the fusion center. We derive upper and lower bounds for the total error probability $P_N$ as explicit functions of $N$ in the case where nodes and links fail with certain probabilities. These characterize the asymptotic decay rate of the total error probability as $N$ goes to infinity. Naturally, this decay rate is not larger than that in the non-failure case, which is $\sqrt N$. However, we derive an explicit necessary and sufficient condition on the decay rate of the local failure probabilities $p_k$ (combination of node and link failure probabilities at each level) such that the decay rate of the total error probability in the failure case is the same as that of the non-failure case. More precisely, we show that $\log P_N^{-1}=\Theta(\sqrt N)$ if and only if $\log p_k^{-1}=\Omega(2^{k/2})$.

The paper presents a simple and effective method for the concurrent manipulation of linearly ordered data structures on hypercube systems. The method Is based on the existence of an augmented binomial search tree, called the pruned binomial tree, rooted at any arbitrary processor node of the hypercube such that; every edge of the tree corresponds to a direct link between a pair of hypercube nodes; and the tree spans any arbitrary sequence of n consecutive nodes containing the root, using a fanout of at most [log/sub 2/ n] and a depth of at most [log/sub 2/ n]+1. Search trees spanning nonoverlapping processor lists are formed using only local information, and can be used concurrently without contention problems. Thus, they can be used for performing operations such as broadcast and merge simultaneously on sets with nonuniform sizes. Extensions of the tree to k-ary n-cubes and faulty hypercubes are presented. Applications of this concurrent data structure to low- and intermediate-level image processing algorithms, and for dictionary operations involving multiple keys, are also outlined. >

We study the detection error probability associated with a balanced binary relay tree, where the leaves of the tree correspond to N identical and independent sensors. The root of the tree represents a fusion center that makes the overall detection decision. Each of the other nodes in the tree is a relay node that combines two binary messages to form a single output binary message. Only the leaves are sensors. In this way, the information from the sensors is aggregated into the fusion center via the relay nodes. In this context, we describe the evolution of the Type I and Type II error probabilities of the binary data as it propagates from the leaves toward the root. Tight upper and lower bounds for the total error probability at the fusion center as functions of N are derived. These characterize how fast the total error probability converges to 0 with respect to N , even if the individual sensors have error probabilities that converge to 1/2.

International audience; In this paper, we propose a new construction of constantdegree expanders motivated by their application in P2P overlay networks and in particular in the design of robust trees overlay. Our key result can be stated as follows. Consider a complete binary tree T and construct a random pairing Π between leaf nodes and internal nodes. We prove that the graph GΠ obtained from T by contracting all pairs (leaf-internal nodes) achieves a constant node expansion with high probability. The use of our result in improving the robustness of tree overlays is straightforward. That is, if each physical node participating to the overlay manages a random pair that couples one virtual internal node and one virtual leaf node then the physical-node layer exhibits a constant expansion with high probability. We encompass the difficulty of obtaining this random tree virtualization by proposing a local, selforganizing and churn resilient uniformly-random pairing algorithm with O(log2 n) running time. Our algorithm has the merit to not modify the original tree virtual overlay (we just control the mapping between physical nodes and virtual nodes). Therefore, our scheme is general and can be applied to a large number of tree overlay implementations. We validate its performances in dynamic environments via extensive simulations.

An algorithm that computes the best matching of two trees is described. The degree of mismatch, i.e., the distance, is measured in terms of the number of node splitting and merging operations required. The proposed tree distance is a more appropriate measurement of structural defonnation than the tree distance measure in terms of the number of insertions, deletions, and substitutions of tree nodes, as defined in previous studies. An algorithm that uses a divide-and-conquer strategy is presented. The analysis shows that the time complexity is O(NM2) where N and Al are the number of nodes of the two trees, respectively. The algorithm has been implemented on a VAX 11/780.

Tree reconstruction methods are often judged by their accuracy, measured by how close they get to the true tree. Yet most reconstruction methods like ML do not explicitly maximize this accuracy. To address this problem, we propose a Bayesian solution. Given tree samples, we propose finding the tree estimate which is closest on average to the samples. This ``median'' tree is known as the Bayes estimator (BE). The BE literally maximizes posterior expected accuracy, measured in terms of closeness (distance) to the true tree. We discuss a unified framework of BE trees, focusing especially on tree distances which are expressible as squared euclidean distances. Notable examples include Robinson--Foulds distance, quartet distance, and squared path difference. Using simulated data, we show Bayes estimators can be efficiently computed in practice by hill climbing. We also show that Bayes estimators achieve higher accuracy, compared to maximum likelihood and neighbor joining., 31 pages, 4 figures, and 3 tables

It has been shown that every tree automatic structure admits an injective tree automatic presentation, but no good size or time bounds are known. From an arbitrary tree automatic presentation, we construct an equivalent injective one in polynomial space that consequently has exponential size. Furthermore we also prove an exponential lower bound for the size of injective tree automatic presentations.

Seismic first-break times can be computed by treating each node of a given model as a secondary source and applying Huygens' Principle from the source to its surrounding nodes and successively from inner nodes to outer nodes of the source. At each node, different travel times are possible from the source via different secondary sources (virtually all the other nodes) and only the least (minimum) time is kept as the first-break time for this particular node. As the number of nodes increases, the selection of the least time for each node can be a huge computational task. However, for the first-break time only a small number of secondary sources, i.e. the immediate neighbouring nodes, need to be considered. An efficient first-break wavefront tracking algorithm is used to maintain the causality of the process. This efficient tracking algorithm arranges the nodes of the model into a directed graph. Only neighbouring nodes are connected by edges. The weight of each edge is denoted by the travel time difference between the two connecting nodes. The local gradient of the first-break time field determines the direction of the edges. With this directed graph, a minimum travel time tree is constructed by taking the source node as its root. At any stage of this wavefront tracking, the nodes of the model can be thought of as divided into three (disjoint) categories: tree nodes in the tree constructed so far; fringe nodes which are not in the tree but adjacent to some nodes in the tree; and unseen (other) nodes. The fringe nodes roughly represent and keep track of the current first-break wavefront. Thus the key point in the construction of the minimum travel time tree is how to evolve the first-break wavefront outward from the source. To maintain causality, the fringe node of least travel time is always selected as a secondary source to illuminate (forward) nodes along the local wave propagation direction. Once the travel times for forward neighbouring nodes are updated, the current node of least travel time is converted to a tree node and the first-break wavefront advances one node away from the source. This updating process is repeated until all the nodes are converted into tree nodes. An efficient sorting method, the heap sort method, is employed to find the least travel time node from the current fringe. A special data structure is adopted for the implementation of an intelligent indirect heap sort. At any stage of the wavefront tracking, only the fringe nodes are in this special data structure and thus only local sorting is required.

We show that the complete binary tree with n > 8 leaves can be embedded in the hypercube with n nodes such that: paths of the tree are mapped onto edge-disjoint paths of the hypercube, at most two tree nodes (one of which is a leaf) are mapped onto each hypercube node, and the maximum distance from a leaf to the root of the tree is log2n + 1 hypercube edges (which is optimally short). This embedding facilitates efficient implementation of many P-RAM algorithms on the hypercube.

Given two ordered, labeled trees β and α, to find the distance from tree β to tree α is an important problem in many fields, for example, the pattern recognition field. In this paper, a VLSI algorithm for calculating the tree to tree distance is presented. The computation structure of the algorithm is a 2-D Mesh with the sizem*n and the time isO(m+n), wherem,n are the numbers of nodes of the tree β and tree α, respectively.

In this paper, an efficient tree generation algorithm based on prefix code is proposed. The algorithm utilizes the sequence consistency of the database record set and the preorder traversal tree. It only need to query on the database and traversal the tree nodes one time respectively, then all nodes can be added to the tree one by one. There is only one cycle that is the traverse of the tree nodes collection, so the time complexity of the algorithm is O (n). Experimental results show that the tree nodes and their child nodes can be queried and stated rapidly.

In this paper, we characterize the capacity of a class of single-source single-destination discrete memoryless relay networks with an arbitrary number of nodes. In this class, the network is assumed to have a tree topology where the root node is the source, each parent node in the graph has at most one noisy child node and any number of noiseless child nodes, and the set of leaf nodes is the destination. A combination of decode-and-forward (DF) and compress-and-forward (CF) at noisy relay nodes is shown to be optimal. Our result is the first to show that the combination of DF and CF is capacity achieving for a non-trivial class of noisy networks with an arbitrary number of nodes.

The problem of learning tree-structured Gaussian graphical models from independent and identically distributed (i.i.d.) samples is considered. The influence of the tree structure and the parameters of the Gaussian distribution on the learning rate as the number of samples increases is discussed. Specifically, the error exponent corresponding to the event that the estimated tree structure differs from the actual unknown tree structure of the distribution is analyzed. Finding the error exponent reduces to a least-squares problem in the very noisy learning regime. In this regime, it is shown that the extremal tree structure that minimizes the error exponent is the star for any fixed set of correlation coefficients on the edges of the tree. If the magnitudes of all the correlation coefficients are less than 0.63, it is also shown that the tree structure that maximizes the error exponent is the Markov chain. In other words, the star and the chain graphs represent the hardest and the easiest structures to learn in the class of tree-structured Gaussian graphical models. This result can also be intuitively explained by correlation decay: pairs of nodes which are far apart, in terms of graph distance, are unlikely to be mistaken as edges by the maximum-likelihood estimator in the asymptotic regime., Comment: Submitted to Transactions on Signal Processing

A novel planar IPPCT tree (PIPPCT) that holds higher data rate is presented based on analysis of main topologies characteristics of current dynamic graph watermarking system (DGW). Multiple dimensional IPPCT tree (MIPPCT) model and three ident ity vectors concerning it are constructed and presented, then the effect of these vectors on MIPPCT model is discussed in detail . The results proved that the data rate of MIPPCT tree will increase to a limit with its dimension number n increasing based on equal number of leaves and this limit is also computed. Moreover, it proved that there exists a two dimensional area HArea, when datarate is in this area, dynamic graph watermarking system will take on greater performance.

The problem of placing a number t of identical resources at nodes of a tree so as to minimize the total expected cost of servicing a set of t requests arriving randomly at nodes is considered. The cost of servicing a particular set of requests is the total distance in the tree between each request and its assigned resource. Distance is measured by the number of edges along the unique path from the request to the resource. Optimal placements can be found in time O(mt), where m is the number of edges in the tree. Allowing resources to be split into fractional-sized pieces which can be placed separately neither reduces the cost of an optimal placement nor provides an obvious way to find optimal placements significantly faster. Simple, natural “fair” placements whose cost differs from optimality by at most the number of edges in the tree are described. For any fixed tree T, the cost of these placements grows as O( t ) , where the constant implicit in the “O” notation depends on the size and shape of T. In the case of balanced trees with k leaves, that constant is at most 2k φ . The placement problem becomes somewhat simpler for a complete (rooted) d-ary tree with a symmetric probability density function for request arrivals, and in that case slightly stronger results are possible. For example, an optimal placement can be found in time O(min{l, logdt} + t), where l is the height of the tree, and the placement is symmetric and fair.

Given a set of weighted source nodes and a set of sink nodes, the Multiple Center Capacitated Minimum Spanning Tree (MCMST) problem can be defined as forming one or more trees that collectively span all the source nodes and at least one of the sink nodes. Each tree is rooted in one of the sink nodes and is composed of one or more subtrees. A subtree is defined as a component of a tree that is disconnected from the rest of the tree when an arc incident to the root node is removed. The objective is to minimize total arc costs subject to a limit on the total weight of the nodes forming a subtree. This is one of the fundamental problems faced in designing computer communication networks. It also has potential applications in design of other hierarchical networks. In this paper we show that MCMST problem is NP-complete and concentrate on developing heuristics with worst case error bounds to solve this problem. A heuristic which has a worst case error bound of 3–2/K is presented for the special case of...

In many tree-structured parallel computations, the size and shape of a tree that represents a parallel computation is unpredictable at compile-time. The tree evolves gradually during the course of the computation. When such an application is executed on a static network, the dynamic tree evolution problem is to distribute the tree nodes to the processors of the network such that all the processors receive roughly the same amount of load and that communicating nodes are assigned to neighboring processors. The main contributions of the paper are to describe a simple random-walk-based asymptotically optimal dynamic tree evolution algorithm on regular networks and to analyze the exponential speed at which the performance ratio converges to the optimal. Our strategy is to prove that the Markov chain of a random walk on a regular network is rapidly mixing.

The problem of learning tree-structured Gaussian graphical models from i.i.d. samples is considered. The influence of the tree structure and the parameters of the Gaussian distribution on the learning rate as the number of samples increases is discussed. Specifically, the error exponent corresponding to the event that the estimated tree structure differs from the actual unknown tree structure of the distribution is analyzed. Finding the error exponent reduces to a least-squares problem in the very noisy learning regime. In this regime, it is shown that universally, the extremal tree structures which maximize and minimize the error exponent are the star and the Markov chain for any fixed set of correlation coefficients on the edges of the tree. In other words, the star and the chain graphs represent the hardest and the easiest structures to learn in the class of tree-structured Gaussian graphical models. This result can also be intuitively explained by correlation decay: pairs of nodes which are far apart, in terms of graph distance, are unlikely to be mistaken as edges by the maximum-likelihood estimator in the asymptotic regime.

Multicast communication in a wireless ad-hoc network can be established using a tree that spans the multicast sender and receivers as well as other intermediate nodes. If the network is modelled as a graph, the multicast tree is a Steiner tree, the multicast sender and receivers correspond to terminals, and other nodes participating in the tree are Steiner nodes. As Steiner nodes are nodes that participate in the multicast tree by forwarding packets but do not benefit from the multicast, it is a natural objective to compute a tree that minimizes the total cost of the Steiner nodes. We therefore consider the problem of computing, for a given node-weighted graph and a set of terminals, a Steiner tree with Steiner nodes of minimum total weight. For graph classes that admit spanning trees of maximum degree at most d, we obtain a 0.775d-approximation algorithm. We show that this result implies a 3.875-approximation algorithm for unit disk graphs, an O(1/α2)-approximation algorithm for α-unit disk graphs, and an O(λ)-approximation algorithm for (λ + 1)-claw-free graphs.

We describe a novel approach for constructing a single spanning tree for data aggregation towards a sink node. The tree is universal in the sense that it is static and independent of the number of data sources and fusion-costs at intermediate nodes. The tree construction is in polynomial time, and for low doubling dimension topologies it guarantees a O(log2 n)-approximation of the optimal aggregation cost. With constant fusion-cost functions our aggregation tree gives a O(logn)-approximation for every Steiner tree to the sink.

In this paper, a novel approach based on genetic programming algorithm (GPA) is proposed to solve the optimal solution of weight vectors on GP-decision tree. In this GP-decision tree algorithm, the GP-decision tree is constructed according to the error rate of tree nodes and the error rate reduction of partitioned nodes. By using this algorithm, not only the weight vectors of tree nodes can be solved, but also the structure of GP-decision tree can be determined. Experimental results show this algorithm is efficient and the right trend forecasting model can be selected by using this GP-decision tree algorithm.

In this paper, we present new efficient strategy for constructing a wireless tree network containing n nodes of diameter Delta while satisfying the QoS requirements such as bandwidth and delay. Given a tree network T, a coredian path is a path in T that minimizes the centdian function, ak-coredian tree is a subtree of T with k leaves that minimizes the centdian function, and a (k, l)-coredian tree is a subtree of T with k leaves and diameter l at most thatminimizes the centdian function. The (k, l)-coredian tree can serve as a backbone for a network, where intermediate nodes belong to the backbone and the leaves serve as the heads of the clusters covering the rest of the network. We show that a coredian path can be constructed at O(Delta)time with O(n) messages and a k-coredian tree can be constructed at O(kDelta) time with O(kn) messages. While a(k, l)-coredian tree can be constructed at O(n2) time with O(n2) messages. A simulation is presented for various values of n and k.

Drawing a tree consists of two stages: determining the position of each node, and actually rendering the individuals nodes and interconnecting branches. The algorithm described in this paper is concerned with the first stage: given a list of nodes, an indication of the hierarchical relationship among them, and their shape and size, where should each node be positioned for optimal aesthetic effect? This algorithm determines the positions of the nodes for any arbitrary general tree. It is the most desirable positioning with respect to certain widely-accepted heuristics. The positioning, specified in x, y co-ordinates, minimizes the width of the tree. In a general tree, there is no limit on the number of offspring per node; this contrasts with binary and ternary trees, for example, which are trees with a limit of two and three offspring per node. This algorithm operates in time O(N), where N is the number of nodes in the tree. Previously, most tree drawings have been positioned by the sure hand of a human graphic designer. Many computer-generated positionings have been either trivial or contained irregularities. Earlier work by Wetherell and Shannon1 and Tilford,2 upon which this algorithm builds, failed to position the interior nodes of some trees correctly. The algorithm presented here correctly positions a tree's node using only two passes. It also handles several practical considerations: alternative orientations of the tree, variable node sizes and out-of-bounds conditions. Radack,3 also building on Tilford's work, has solved this same problem with a different algorithm which makes four passes.

A novel content-based image retrieval data structure is developed in present work. It can improve the searching efficiency significantly. All images are organized into a tree, in which every node is comprised of images with similar features. Images in a children node have more similarity (less variance) within themselves in relative to its parent. It means that every node is a cluster and each of its children nodes is a sub-cluster. Information contained in a node includes not only the number of images, but also the center and the variance of these images. Upon the addition of new images, the tree structure is capable of dynamically changing to ensure the minimization of total variance of the tree. Subsequently, a heuristic method has been designed to retrieve the information from this tree. Given a sample image, the probability of a tree node that contains the similar images is computed using the center of the node and its variance. If the probability is higher than a certain threshold, this node will be recursively checked to locate the similar images. So will its children nodes if their probability is also higher than that threshold. If no sufficient similar images were founded, a reduced threshold value would be adopted to initiate a new seeking from the root node. The search terminates when it found sufficient similar images or the threshold value is too low to give meaningful sense. Experiments have shown that the proposed dynamic cluster tree is able to improve the searching efficiency notably.

The problem of matching random tree models of multi-component patterns to tables or graphs containing components extracted from diverse data sources is considered. We focus on bi-level trees whose branches emanate from one root node and terminate on different leaf nodes. Node and branch attributes are treated as random variables. Tree nodes represent pattern components of specified types that occur in tables or graphs to be searched. For each item in the table or graph with a type match to the tree root, there is a set of components from the table or graph that are candidate leaves for optimal matches to the tree model. We adopt a view of optimal matches to random tree models as minimum cost assignments of candidate leaves to tree branches. Model-based formulas are derived for computing costs associated with assignments of specific candidate leaf components from tables or graphs to specific tree branches. We specify an ontology suitable for dynamic geo-spatial query problems in which (1) tree nodes represent physical objects or events on the ground (buildings, roads, communication transmissions...), and (2) branch attributes characterize, with uncertainty, distance or time separations between components, and angles between links connecting components. Our approach is used to search very large images for specific types of buildings in probabilistically constrained spatial arrangements, with the goal of ranking model matches for efficient inspection by human analysts.