Search

This paper addresses the reverse 1-center problem on a weighted tree. Here, a facility has already been located in a predetermined node of the tree network and we want to improve the 1-center objective value at that node as efficiently as possible within a given budget. For solving this problem under uniform linear cost functions, we develop a combinatorial algorithm with running time , where is the number of vertices of the tree.

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.

We give two self-stabilizing algorithms for tree networks. The first computes an index, called guide pair, for each process P in O(h) rounds using O(@d"Plogn) space per process, where h is the height of the tree, @d"P the degree of P, and n the number of processes in the network. Guide pairs have numerous applications, including ordered traversal or navigation in the tree. Our second algorithm, which uses the guide pairs computed by the first algorithm, solves in O(n) rounds the ranking problem for an ordered tree, where each process has an input value. This second algorithm has space complexity O(b+@d"Plogn) in each process P, where b is the number of bits needed to store an input value. The first algorithm orders the tree processes according to their topological positions. The second algorithm orders (ranks) the processes according to their input values.

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.

For concurrent database access, the B-link tree is a well-suited data structure; this paper describes a modification of the B-link tree to reduce the expense associated with splits and merges while moving down the tree. The modification is keyed to the concept of stability in each B-link tree node. Being stable amounts to a node having somewhere between a small percentage more than the minimum number and a small percentage fewer than the maximum number of child links such a node may have. When additions or deletions lead to instability in a node, either an overflow or underflow is considered to be imminent. Upon visiting a node, an update process will determine if the node's content is at the B-link maximum or minimum; if this is the case, the process performs whatever split or merge and redistribution operations necessary to make this and any related node stable. As a result of this action, there will always be room for an overflowed child to insert an entry in its parent and likewise room for an underflowed child to remove an entry from its parent; backward propagation of insertions or deletions further up the Blink tree are thus eliminated, improving the possible degree of concurrency. Further, no node will be left without a parent, obviating horizontal traversal within the tree in all but highly infrequent process scheduling scenarios.

Our context of interest is tree-structured exact search in metric spaces. We make the simple observation that, the deeper a data item is within the tree, the higher the probability of that item being excluded from a search. Assuming a fixed and independent probability p of any subtree being excluded at query time, the probability of an individual data item being accessed is \( (1-p)^d\) for a node at depth d. In a balanced binary tree half of the data will be at the maximum depth of the tree so this effect should be significant and observable. We test this hypothesis with two experiments on partition trees. First, we force a balance by adjusting the partition/exclusion criteria, and compare this with unbalanced trees where the mean data depth is greater. Second, we compare a generic hyperplane tree with a monotone hyperplane tree, where also the mean depth is greater. In both cases the tree with the greater mean data depth performs better in high-dimensional spaces. We then experiment with increasing the mean depth of nodes by using a small, fixed set of reference points to make exclusion decisions over the whole tree, so that almost all of the data resides at the maximum depth. Again this can be seen to reduce the overall cost of indexing. Furthermore, we observe that having already calculated reference point distances for all data, a final filtering can be applied if the distance table is retained. This reduces further the number of distance calculations required, whilst retaining scalability. The final structure can in fact be viewed as a hybrid between a generic hyperplane tree and a LAESA search structure.

International audience; Semantic Backpropagation (SB) was introduced in GP so as to take into account the semantics of a GP tree at all intermediate states of the program execution, i.e., at each node of the tree. The idea is to compute the optimal " should-be " values each subtree should return, whilst assuming that the rest of the tree is unchanged, and to choose a subtree that matches as well as possible these target values. A single tree is evolved by iteratively replacing one of its nodes with the best subtree from a static library according to this local fitness, with tree size as a secondary criterion. Previous results for standard Boolean GP benchmarks that have been obtained by the authors with another variant of SB are improved in term of tree size. SB is then applied for the first time to categorical GP benchmarks, and outperforms all known results to date for three variable finite algebras.

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.

Matching of tree structures is equivalent to the problem of searching for maximum cliques in tree association graphs. Pelillo and colleagues have recently proposed a method for searching for maximum weight cliques that gives weight to association graphs on the basis of similarities of the attributes of tree nodes. Here, the obtained maximum weight clique corresponds to the maximum similarity subtree isomorphism. This paper proposes a tree structure-matching scheme using tree association graphs, as a general scheme for performing nonrigid body registration of tree structures in three-dimensional medical images. Matching of tree structures of three-dimensional medical images of bronchi, blood vessels, and the like must be capable of handling changes in body positions accompanying their changes as well as physiological changes due to breathing exercises etc. In addition, it needs to recognize topology errors of pseudo or false branches occurring during image processing. This study, as attributes of tree nodes, constructs similarities using body volume change rates extending over the parents, children and siblings, focusing on the positional relations of the nodes of the parents, children, and siblings. The similarities proposed are those having high general properties that can be applied to changes in positions and shapes that occur inside a body since they focus on their general properties. In addition, as a method for avoiding mismatches due to topology errors, changing the weights of neighboring edges on the basis of similarities is added. The proposed scheme has been confirmed to show a high correct solution rate or true positive fraction regardless of high degree changes in positions and shapes when applied to a bronchial model generated inside a computer. It has also been confirmed that mismatches due to topology errors occur at a very low rate with the proposed scheme. © 2004 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 87(2): 59–72, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.10216

In a box-drawing of a rooted tree, each node is drawn by a rectangular box of prescribed size, no two boxes overlap each other, all boxes corresponding to siblings of the tree have the same x-coordinate at their left sides, and a parent node is drawn at a given distance apart from its first child. A box drawing of a tree is compact if it attains the minimum possible rectangular area enclosing the drawing. We give a linear-time algorithm for finding a compact box-drawing of a tree. A known algorithm does not always find a compact box-drawing and takes time O(n 2 ) if a tree has n nodes. © 2003 Wiley Periodicals, Inc.

A tree of rings is an undirected graph obtained from a tree by replacing each node of the tree with a cycle (called tree-node-cycle) and then contracting the edges of the tree so that two cycles corresponding to the two end-nodes of any edge have precisely one node in common and no three tree-node-cycles share a same node. (A more general definition may allow them to share the same node.) Given a set of paths on a tree of rings, the path coloring problem is to color these paths with the smallest number of colors so that any two paths sharing an edge are assigned different colors. In this paper, we present a 2-approximation algorithm for this problem.

The Priority Search Tree is the classic solution for the problem of dynamic 2-dimensional searching for the orthogonal query range of the form [a,b]×(-∞,c] (3-sided rectangle). It supports all operations in logarithmic worst case complexity in both main and external memory. In this work we show that the update and query complexities can be improved to expected doubly-logarithmic, when the input coordinates are being continuously drawn from specific probability distributions. We present three pairs of linear space solutions for the problem, i.e. a RAM and a corresponding I/O model variant: (1) First, we improve the update complexity to doubly-logarithmic expected with high probability, under the most general assumption that both the x- and y-coordinates of the input points are continuously being drawn from a distribution whose density function is unknown but fixed. (2) Next, we improve both the query complexity to doubly-logarithmic expected with high probability and the update complexity to doubly-logarithmic amortized expected, by assuming that only the x-coordinates are being drawn from a class of smooth distributions, and that the deleted points are selected uniformly at random among the currently stored points. In fact, the y-coordinates are allowed to be arbitrarily distributed. (3) Finally, we improve both the query and the update complexity to doubly-logarithmic expected with high probability by moreover assuming the y-coordinates to be continuously drawn from a more restricted class of realistic distributions. All data structures are deterministic and their complexity's expectation is with respect to the assumed distributions. They comprise combinations of known data structures and of two new data structures introduced here, namely the Weight Balanced Exponential Tree and the External Modified Priority Search Tree.

In this paper we describe the discrete interval encoding tree for storing subsets of types having a total order and a predecessor and a successor function. In the following, we consider for simplicity only the case for integer sets; the generalization is not difficult.The discrete interval encoding tree is based on the observation that the set of integers {i[mid ]a[les ]i[les ]b} can be perfectly represented by the closed interval [a, b]. The general idea is to represent a set by a binary search tree of integers in which maximal adjacent subsets are each represented by an interval. For example, inserting the sequence of numbers 6, 9, 2, 13, 8, 14, 10, 7, 5 into a binary search tree, respectively, into a discrete interval encoding tree results in the tree structures shown in figure 1.The efficiency of the interval representation, both in terms of space and time, improves with the density of the set, i.e. with the number of adjacencies between set elements. So what we propose is a ‘diet’ (discrete interval encoding tree) for ‘fat’ sets in the sense of ‘the same amount of information with less nodes’.

A new and simple method of indexing a tree for tree patterns is presented. A tree pattern is a tree whose leaves can be labelled by a special symbol S, which serves as a placeholder for any subtree. Given a subject tree T with n nodes, the tree is preprocessed and an index, which consists of a standard string compact suffix automaton and a subtree jump table, is constructed. The number of distinct tree patterns which match the tree is \(\mathcal{O}(2^n)\), and the size of the index is \(\mathcal{O}(n)\). The searching phase uses the index, reads an input tree pattern P of size m and computes the list of positions of all occurrences of the pattern P in the tree T. For an input tree pattern P in linear prefix notation pref(P) = P 1 S P 2 S …S P k , k ≥ 1, the searching is performed in time \(\mathcal{O}(m + \sum\limits_{i=1}^k |occ(P_i)|))\), where occ(P i ) is the set of all occurrences of P i in pref(T).

A ring tree is a tree graph with an optional additional edge that closes a unique cycle. Such a cycle is called a ring and the nodes on it are called ring nodes. The capacitated ring tree problem (CRTP) asks for a network of minimal overall edge cost that connects given customers to a depot by ring trees. Ring trees are required to intersect in the depot which has to be either a ring node of degree two in a ring tree or a node of degree one if the ring tree does not contain a ring. Customers are predefined as of type 1 or type 2. The type 2 customers have to be ring nodes, whereas type 1 customers can be either ring nodes or nodes in tree sub-structures. Additionally, optional Steiner nodes are given which can be used as intermediate network nodes if advantageous. Capacity constraints bound both the number of the ring trees as well as the number of customers allowed in each ring tree. In this paper we present first advanced neighborhood structures for the CRTP. Some of them generalize existing concepts for the TSP and the Steiner tree problem, others are CRTP-specific. We also describe models to explore these multinode and multi-edge exchange neighborhoods in one or more ring trees efficiently. Moreover, we embed these techniques in a heuristic multi-start framework and show that it produces high quality results for small and medium size literature instances.

In this paper we show how a slight modification of (a, 2b)-trees allows us to perform member and neighbor queries in O( log n) time and updates in O(1) worst-case time (once the position of the inserted or deleted key is known). Our data structure is quite natural and much simpler than previous worst-case optimal solutions. It is based on two techniques : 1) bucketing, i.e., storing an ordered list of 2 log n keys in each leaf of an (a, 2b) tree, and 2) preventive splitting, i.e., splitting nodes before they can grow bigger than allowed. If only insertions are allowed, it can also be used as a finger search tree with O( log * n) worst-case update time.

Operations performed in a Binary Search Tree generally starts from root node. As result search space (total number of nodes) constitutes entire tree, where a normal users intention is only certain part of the tree. In this paper we propose a noble method for performing operations such as insertion, deletion and retrieval within the local search space of a lookup node rather than the root node. To define local search space of a node, we implement leaf nodes null pointers, which are generally remains unused. These local search spaces divides the actual search space which generally constitutes entire tree. Hence complexity reduced to O(log m) from O(log n) for a local node, where m is the number of nodes present in sub tree formed by local search space and n is the number of nodes present in the tree.

Trees are often drawn as boxes-and-arrows charts that tend to fix the mental image of a tree into a graph structure. Another way of representing trees is to show them as nested sets. The chapter highlights this approach. To show a tree as nested sets, replace the boxes with ovals and then nest subordinate ovals inside their parents. Containment represents subordination. The root will be the largest oval and will contain every other node. The leaf nodes will be the innermost ovals, with nothing else inside them, and the nesting will show the hierarchical relationship. This is a natural way to model a parts explosion because a final assembly is made of physically nested assemblies that finally break down into separate parts. This approach is used to model a tree with nested sets with number pairs that always contain the pairs of their subordinates so that a child node is within the bounds of its parent. The chapter uses this approach of representation of a tree graph to present techniques to perform operations, such as finding root and leaf nodes, finding subtrees, finding levels and paths in a tree, finding the height of a tree, deleting nodes and subtrees, closing gaps in the tree, using summary functions on trees, and inserting and updating trees. The chapter also provides techniques to convert nested sets into adjacent list models, and compare nodes and structures of these models. All of these techniques are explained using simple SQL codes maintaining an organizational chart table to represent the hierarchy and people of a sample organization.

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

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.

A parallel suffix tree construction algorithm is presented. The suffix tree is decomposed into many sub-suffix trees according to characters of the string to be suffixed, each of which is a suffix tree starting with a specific character. Theoretic prove is given to show that the proposed decomposition scheme is correct and the decomposed sub­suffix trees can be constructed in parallel on multiple node computers in a distributed system. The workload of generating a suffix tree is almost evenly distributed among many nodes in the distributed system, and both the time and space cost is greatly reduced. Moreover, once sub-suffix trees are constructed on each node, multiple keywords starting with different characters can be searched in parallel on the node computers. Comparison results on suffix tree generating cost and keyword string matching performance show that the presented suffix tree algorithm is better in terms of time complexity on both construction and matching.

Till date in all the books they talks about height of a general tree like height balanced tree. In this paper we talk about width of a general tree. Width of a general tree is defined as number of nodes at each level and maximum of them. The recursive algorithm for width has been given. Later in the paper the iterative version using the stack is given.

The structure of Galton-Watson trees conditioned to be of a given size is well-understood. We provide yet another embedding theorem that permits us to obtain asymptotic probabilities of events that are determined by what happens near the root of these trees. As an example, we derive the probability that a Galton-Watson tree is cut when each node is independently removed with probability p, where by cutting a tree we mean that every path from root to leaf must have at least one removed node.

This paper presents a heuristic to construct the minimum-entropy tree admitting a given leaf specification. The tree is constructed in stages. We start at the level which is furthest from the root and work our way to the root one level at a time. Phase I generates the outdegrees of an auxiliary decision tree. In Phase II the decision tree is constructed and we give a method of labelling the nodes in it. Phase III of the algorithm presents the technique to obtain the minimum-entropy tree. The algorithm incorporates a procedure called “minimum entropy separation on k nodes”.

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.

Consider a tree partitioning process in which n elements are split into b at the root of a tree (b a design parameter), the rest going recursively into two subtrees with a binomial probability distribution. This extends some familiar tree data structures of computer science like the digital trie and the digital search tree. The exponential generating function for the expected size of the tree satisfies a difference-differential equation of order b, The solution involves going to ordinary (rather than exponential) generating functions, analyzing singularities by means of Mellin transforms and contour integration. The method is of some general interest since a large number of related problems on digital structures can be treated in this way via singularity analysis of ordinary generating functions. 0 1992 John Wiley & Sons, Inc.

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

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.

We consider the problem of maintaing a random binary search tree under insertions and deletions under the conditions that (i) no extra permanent storage space be used besides the tree itself, and (ii) that at any point in time the tree be perfectly random, meaning that it is drawn from the ideal binary search tree distribution. We present a simple solution to this problem with an expected deletion time of O(logn) and expected insertion time of O(log2 n) time.

Ashoot is a fixed subset of branches rooted at a given vertex of a tree. We show that interchanging two nonintersecting shoots is an isomorphism of a tree only in two trivial cases: when either the shoots are isomorphic as rooted trees or their roots are similar in a tree obtained by deleting the shoots without the roots. The proof is based on a sufficient condition for similarity of two vertices in a tree. We also consider some applications of the above results to problems concerning Number Deck reconstruction of a tree.

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.

Two basic results for the Euclidean Steiner minimal tree problem are shown: (1) all admissible partitions of the set of nodes (which the tree should span) correspond to degenerate full Steiner topologies, and can be systematically derived from these topologies if degeneracy occurs; (2) for any given full Steiner tree topology there exists a lower bound on the value of the corresponding Steiner tree (this bound holds as an equality if the tree is full). Taken together these two results suggest a relatively efficient (although still exponential) branch and bound algorithm for the Steiner minimal tree construction. The algorithm uses the lower bound to discard some topologies after a brief check, and does away with the need to check all the possible partitions of the node set.

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.

It is well-known that to minimize the number of comparisons a binary search tree should be perfectly balanced. Previous work has shown that a dominating factor over the running time for a search is the number of cache faults performed, and that an appropriate memory layout of a binary search tree can reduce the number of cache faults by several hundred percent. Motivated by the fact that during a search branching to the left or right at a node does not necessarily have the same cost, e.g. because of branch prediction schemes, we in this paper study the class of skewed binary search trees. For all nodes in a skewed binary search tree the ratio between the size of the left subtree and the size of the tree is a fixed constant (a ratio of 1/2 gives perfect balanced trees). In this paper we present an experimental study of various memory layouts of static skewed binary search trees, where each element in the tree is accessed with a uniform probability. Our results show that for many of the memory layouts we consider skewed binary search trees can perform better than perfect balanced search trees. The improvements in the running time are on the order of 15%.

An ultrametric tree is an evolutionary tree in which the distances from the root to all leaves in the tree are equal. The Minimum Ultrametric Tree construction problem is the problem of constructing an ultrametric tree from distance matrices with minimum cost. It is shown that to construct a minimum cost ultrametric tree is NP-hard. In this paper, we present an efficient parallel branch and bound algorithm to construct a minimum ultrametric tree with less cost. The experimental results show that our proposed algorithm can discover optimal solutions for 38 species within reasonable time with 16 computing nodes

Publisher Summary A tree is a special kind of directed graph. Graphs are data structures that are made up of nodes connected by edges. There are several ways to define a tree: it is a graph with no cycles and it is a graph where all nodes except the root have indegree one and the root has indegree zero. Another defining property is that a path can be found from the root to any other node in the tree by following the edges in their natural direction. Most Structured Query Language (SQL) databases use the adjacency list model for two reasons. The first reason is that Dr. Codd came up with it in the early days of the relational model, and nobody thought about it after that. The second reason is that the adjacency list is a way of “faking” pointer chains—the traditional programming method in procedural languages for handling trees. Because SQL is a set-oriented language, the nested set model is a better model for the approach discussed in this chapter.

International audience; A binary unordered tree is a tree where each internal node has two children and the relative order of the subtrees of a node is not important (i.e. two trees are different if they differ only in the respective ordering of subtrees of nodes). We present a new method to generate all binary rooted unordered trees with n internal nodes, without duplications, in O(log n) time.

The design of the cell tree, an object-oriented dynamic index structure for geometric databases, is described. The data objects in the database are represented as unions of convex point sets (cells). The cell tree is a balanced tree structure whose leaves contain the cells and whose interior nodes correspond to a hierarchy of nested convex polyhedra. This index structure allows quick access to the cells (and thereby to the data objects) that occupy a given location in space. The cell tree is designed for paged secondary memory to minimize the number of disk accesses occurring during a tree search. Point locations and range searches can be carried out very efficiently using the cell tree. >

We present a token-based algorithm for solving the K-entry critical section problem. Based on Raymond's (1989) tree-based approach, we regard the nodes as being arranged in a directed tree structure, and all messages used in the algorithm are sent along the directed edges of the tree. There are K tokens in the system; we use a bag structure at each node to record the collection of the neighboring nodes, possibly with multiple occurrences of the same node, through which the K tokens can be located. As a result, there are K paths from each node leading to the K tokens in the system. Our algorithm requires at most 2 KD messages for a node to enter the CS, where D is the diameter of the tree. Therefore, when the diameter D is much smaller than N, the number of nodes, e.g. D=O(1) as in a star or D=O(logN) as in a binary tree, our algorithm's upper bound on the number of messages per CS is smaller than those previously reported.

The paper analyzes the fault-tolerance of complete binary tree networks. It shows how an N-mode tree subject to random failures can simulate a perfect, fault-free tree under different fault models. If edges fail with independent probability p >

A random suffix search tree is a binary search> tree constructed for the suffixes Xi = 0.BiBi+1Bi+2... of a sequence B1, B2... of independent identically distributed random b- ary digits Bj. Let Dn denote the depth of the node for Xn in this tree when B1 is uniform on ℤb. We show that for any value of \(b > 1, \mathbb{E}{{\text{D}}_n} = 2 \log n + O({\log ^2}\log n)\) just as for the random binary search tree. We also show that \({D_n}/\mathbb{E}{{\text{D}}_n} \to 1\) in probability.

The time complexity analysis of the IDA* algorithm has shown that predicting the growth of the search tree essentially relies on only two criteria: The number of nodes in the brute-force search tree for a given depth and the equilibrium distribution of the heuristicestimate. Since the latter can be approximated by random sampling, we accurately predict the number of nodes in the brute-force search tree for large depth in closed form by analyzing the spectrum of the problem graph or one of its factorization.We further derive that the asymptotic brute-force branching factor is in fact the spectral radius of the problem graph and exemplify our considerations in the domain of the (n2 - 1)-Puzzle.

structure is being used for designing of databases, software system etc. Different data structures are being used for different kinds of applications and some data structures are particular used for specific tasks. B-trees are particularly used for implementation of databases. Hash tables are widely used for implementations of compilers. Tree is non linear data structure which is better than array, linked list because the time complexity for different operations like searching, insertion, deletion etc. is less in the case of tree. The time complexity for dynamic operations like searching, insertion, deletion, updating a node etc. is directly proportional to the height of red black tree. As the height(h) of red black tree is directly proportional to the O(lg(n)) where n represents the total number of nodes in a particular red black tree. So the time complexity for different dynamic operations like searching, insertion, deletion, updating a node etc. is directly proportional to the O(lg(n)). In this paper, Minimum and maximum ratio of number of red internal nodes to black internal nodes in Red Black tree is determined and explained with the help of diagram.

Comparative studies of tree-building methods have shown minimum evolution to be in general an accurate criterion for selecting a true tree. To improve the use of this criterion, this paper proposes a method for rapidly and directly calculating a length of a dichotomous tree without having to resort to branch length calculations. This direct calculation (DC) method applies to the complete final topology, giving equal importance to each branch after a dichotomy. According to this method, the tree length S(DC) is S(DC) = sigma(i) sigma(j)(D(ij)/2(B(ij))) = (sigma(ij) sigma D(ij)2(Bmax-B(ij)))/2(Bmax)(-1) where D(ij) is the observed distance between taxa i and j, B(ij) is the number of branches connecting i and j, Bmax is the greatest B(ij) in the tree, and the powers of two are due to the dichotomy of the tree. This tree length expression may be used as a rapid method for selecting the shortest tree from a set of hypothetical or subobtimal trees.

A tree of rings is an undirected graph obtained from a tree by replacing each node of the tree with a cycle and then contracting the edges of the tree so that two cycles corresponding to the two end-nodes of any edge have precisely one node in common. Given a set of paths on a tree of rings, the routing problem is to color the paths with the smallest number of colors so that any two paths sharing an edge are assigned different colors. We present a 2-approximation algorithm in this paper.

A self-organizing tree (S-TREE) has a self-organizing capability and better performance than previously reported tree-structured clustering. In the S-TREE algorithm, since a tree grows in greedy fashion, a pruning mechanism is necessary to reduce the effect of bad leaf nodes. Extra nodes are pruned when the tree reaches a predetermined maximum size (U). U is problem-dependent and is therefore difficult to specify beforehand. Furthermore, since U gives the limit of tree growth and also prevents self-organizing of the tree, it may produce unnatural clustering. We are presenting a new pruning algorithm without U. In this paper, we present results showing the performance of the new pruning algorithm using samples generated from normal distributions. The results of computational experiments showed that the new pruning algorithm works well for clustering of those samples.

We consider random tries constructed from sequences of i.i.d. random variables with a common density $f$ on $\lbrack 0, 1 \rbrack$ (i.e., paths down the tree are carved out by the bits in the binary expansions of the random variables). The depth of insertion of a node and the height of a node are studied with respect to their limit laws and their weak and strong convergence properties. In addition, laws of the iterated logarithm are obtained for the height of a random trie when $\int f^2 < \infty$. Finally, we study two popular improvements of the trie, the $\mathrm{PATRICIA}$ tree and the digital search tree, and show to what extent they improve over the trie.