Search

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.

This paper studies the problem of constructing a minimum-cost multicast tree (or Steiner tree) in which each node is associated with a cost that is dependent on its degree in the multicast tree. The cost of a node may depend on its degree in the multicast tree due to a number of reasons. For example, a node may need to perform various processing for sending messages to each of its neighbors in the multicast tree. Thus, the overhead for processing the messages increases as the number of neighbors increases. This paper devises a novel technique to deal with the degree-dependent node costs and applies the technique to develop an approximation algorithm for the degree-dependent node-weighted Steiner tree problem. The bound on the cost of the tree constructed by the proposed approximation algorithm is derived to be 2((ln (k/2))+1)(W_T∗ + B), where k is the size of the set of multicast members, W_T∗ is the cost of a minimum-cost Steiner tree T∗, and B is related to the degree-dependent node costs. Simulations are carried out to study the performance of the proposed algorithm. A distributed implementation of the proposed algorithm is presented. In addition, the proposed algorithm is generalized to solve the degree-dependent node-weighted constrained forest problem.

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.

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.

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.

We study the problem of running full binary tree based algorithms on a hypercube with faulty nodes. The key to this problem is to devise a method for embedding a full binary tree into the faulty hypercube. Based on a novel embedding strategy, we present two results for embedding an (n-1) tree fa full binary tree with 2/sup n-1/ nodes) into an n-cube (a hypercube with 2/sup n/ nodes) with unit dilation and load. For the problem where the root of the tree must be mapped to a specified hypercube node (specified root embedding problem), we show that up to n-2 (node or edge) faults can be tolerated. This result is optimal in the following sense: 1) it is time-optimal, 2) (n-1)-tree is the largest fall binary tree that can be embedded in an n-cube, and 3) n-2 faults Is the maximum number of worst-case faults that can be tolerated in the specified root problem. Furthermore, we also show that any algorithm for this problem cannot be totally recursive in nature. For the problem where the root can be mapped to any nonfaulty hypercube node (variable root embedding problem), we show that up to 2n-3-[log n] faults can be tolerated. Thus we have improved upon the previous result of n-1-[log n]. In addition, we show that the algorithm for the variable root embedding problem is optimal within a class of algorithms called recursive embedding algorithms as far as the number of tolerable faults is concerned. Finally, we show that when an O(1spl radic/n) fraction of nodes in the hypercube are faulty, it is not always possible to have an O(1)-load variable root embedding no matter how large the dilation is. >

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. >

A generalization of the min-cut partitioning problem, called min-cost tree partitioning, is introduced. In the generalized problem. the nodes of a hypergraph G are to be mapped onto the vertices of a tree structure T, and the cost function to be minimized is the cost of routing the hyperedges of G on the edges of T. The standard min-cut problem is the simple case in which the tree T is a single edge connecting two vertices. Several VLSI design applications for this problem are discussed. An iterative improvement heuristic for this problem in which nodes of the hypergraph are moved between the vertices of the tree is described. The running time of a single pass of the heuristic for the unweighted version of the problem is Q(P*D*t/sup 3/), where P is the total number of pins in the hypergraph G, D is the maximum number of nodes in a hyperedge of G, and t is the number of vertices in the tree T. Several test results are discussed. >

We consider the problem of embedding a complete binary tree in squareor hexagonally-connected VLSI arrays Of processing elements (PE's). This problem can be solved in a radically different manner from current layout techniques which are aimed at laying out a given graph in the plane. The difference is due to the fact that a PE can be used both as a tree node and as a connecting element between distant nodes. New embedding schemes are presented in which (asymptotically) 100 percent of the PE's are utilized as tree nodes. This is a significant savings over known schemes, which achieve 50 percent utilization (the well-known H-tree) and 71 percent for some hexagonal schemes. These schemes also speed up signal propagation from the root to the leaves.

Three algorithms are given to construct a weighted r-ary tree with a given set of integer weighted leaves in which the weight of a parent node is 1 + max of its sons. Two goals are of interest; to minimize 1) the weight of the root of the tree, and 2) the number of internal nodes.

The authors consider a class of AND-OR tree circuits and study their response to random-pattern inputs as the depth of the tree is allowed to increase indefinitely. Each binary input of a circuit is independently chosen to be one (zero) with probability x (1-x). The logic of the circuit determines the probability of success (one) at the output as a monotonically increasing S-shaped function of x called the probability transfer function. The probability transfer function of an AND-OR tree is shown to have just one interior fixed point (with respect to changes in depth of the tree) in the

A new tree code is introduced for discrete-time stationary Gaussian sources with hounded, integrable power spectra and the squared-error distortion measure. The codewords in the tree are reconstructions of Karhunen-Loeve transforms of the source words. The branching factor and the number of code letters per branch may vary with level in the tree. A theorem that guarantees the existence of an optimal code for any code rate using such a tree is proved. The proof uses the random coding argument in conjunction with a theorem on survival of a branching process with random environment. A suboptimal but computationally affordable realization of the theorem's coding technique was used for encoding simulations for six autoregressive sources at rates of 1.0, 0.50, 0.25 , and 0.10 bits per source symbol. The average distortion results were generally within 1 dB of the distortion-rate bound but varied widely depending on the source and rate. The results were compared with those for transform quantization simulations for the same sources and rates. The tree code always performed better but only by an average of 0.44 dB all sources and rates. Longer source blocks and more intensive search would certainly improve the performance of the tree codes, but at the expense of extra computation and storage.

We consider the problem of optimally partitioning an n-dimensional lattice, L = L, X ... X LN, where Lj is a one-dimensional lattice with kj elements, by means of a binary tree into specified (labeled) subsets of L. Such lattices arise from problems in pattern classification, in nonlinear regression, in defining logical equations, and a number of related areas. When viewed as the partitioning of a vector space, each point in the lattice corresponds to a subregion of the space which is relatively homogeneous with respect to classification or range of a dependent variable. Optimality is defined in terms of a general cost function which includes the following: 1) min-max path length (i. e., minimize the maximum number of nodes traversed in making a decision); 2) minimum number of nodes in the tree; and 3) expected path length. It is shown that an optimal tree can be recursively constructed through the application of invariant imbedding (dynamic programming). An algorithm is detailed which embodies this recursive approach. The algorithm allows the assignment of a "don't care" label to elements of L.