Search

A height-balanced tree is a desired data structure for performing operations such as search, insert and delete, on high-dimensional external data storage. Its preference is due to the fact that it always maintains logarithmic height even in worst cases. It is a rooted binary tree in which for every vertex the difference (denoted as balance factor) in the heights of the subtrees, rooted at the left and the right child of the vertex, is at most one. In this paper, we consider two subclasses of height-balanced trees and . A tree in is such that all the vertices up to (a predetermined) level t has balance factor one and the remaining vertices have balance factor zero. A tree in is such that all the vertices at alternate levels up to t has balance factor one and the remaining vertices have balance factor zero. We prove that every tree in the classes and is a subtree of the hypercube.

In Social network system, existing “people you might know” or “Mutual friends” recommending applications are commonly utilized to list two-hop mediate relationships that one could have with another in order to tighten the bonds among groups. However, as the number of SNS users increase dramatically, the relationship data get so huge that the performance of Mutual Friends recommendation system becomes an urgent problem considering the developers’ requirements. Here we propose a sorting algorithm in Hadoop----a parallel computing framework, to enhance the efficiency of “Mutual friends” recommendation process by taking advantage of the novel map reduce model. In the revised application, original sorting algorithm of intermediate data, merge sort, is replaced by a more time saving sorting approach which introduces a B-Tree like data structure, 2-3 Tree to store the user friendship data and conducts the sorting process. As number of user increases, the revised user defined map reduce functions perform better than the conventional design in time consuming aspect.

A tree is scattered if it does not contain a subdivision of the complete binary tree as a subtree. We show that every scattered tree contains a vertex, an edge, or a set of at most two ends preserved by every embedding of T. This extends results of Halin, Polat and Sabidussi. Calling two trees equimorphic if each embeds in the other, we then prove that either every tree that is equimorphic to a scattered tree T is isomorphic to T, or there are infinitely many pairwise non-isomorphic trees which are equimorphic to T. This proves the tree alternative conjecture of Bonato and Tardif for scattered trees, and a conjecture of Tyomkyn for locally finite scattered trees.

Given a very large, node-weighted, rooted tree on, say, n nodes, if one has only enough space to display a k-node summary of the tree, what is the most informative way to draw the tree? We define a type of weighted tree that we call a summary tree of the original tree that results from aggregating nodes of the original tree subject to certain constraints. We suggest that the best choice of which summary tree to use (among those with a fixed number of nodes) is the one that maximizes the information-theoretic entropy of a natural probability distribution associated with the summary tree, and we provide a (pseudopolynomial-time) dynamic-programming algorithm to compute this maximum entropy summary tree, when the weights are integral. The result is an automated way to summarize large trees and retain as much information about them as possible, while using (and displaying) only a fraction of the original node set. We illustrate the computation and use of maximum entropy summary trees on five real data sets whose weighted tree representations vary widely in structure. We also provide an additive approximation algorithm and a greedy heuristic that are faster than the optimal algorithm, and generalize to trees with real-valued weights.

A transversal in a rooted tree is any set of nodes that meets every path from the root to a leaf. We let c(T,k) denote the number of transversals of size k in a rooted tree T. We define a partial order on the set of all rooted trees with n nodes by saying that a tree T succeeds a tree T′ if c(T,k) is at least c(T′,k) for all k and strictly greater than c(T′,k) for at least one k. We prove that, for every choice of positive integers d and n, the set of all rooted trees on n nodes where each node has at most d children has a unique minimal element with respect to this partial order and we describe this tree. In addition, we determine asymptotically the expected values of c(T,k) in special families of trees. C © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 32–43, 2013

A height-balanced tree is a rooted binary tree T in which for every vertex v ? V (T), the heights of the subtrees, rooted at the left and right child of v, differ by at most one; this difference is called the balance factor of v. These trees are extensively used as data structures for sorting and searching. We embed several subclasses of height-balanced trees of height h in Qh + 1 under certain conditions. In particular, if a tree T is such that the balance factor of every vertex in the first three levels is arbitrary (0 or 1) and the balance factor of every other vertex is zero, then we prove that T is embeddable in its optimal hypercube with dilation 1 or 2 according to whether it is balanced or not. � 2009 Elsevier Inc. All rights reserved.

An ordered tree is called a non-regular tree with a prescribed branching sequence (or non-regular tree for short) if its internal nodes have a prespecified degree sequence in preorder list. We define a concise representation, called right distance sequences to describe such trees. A coding tree helps us to systematically investigate the structural representation of non-regular trees. Consequently, we present a loopless algorithm to generate Gray-codes of non-regular trees using right distance sequences.

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.

In the dynamic tree problem the goal is the maintenance of an arbitrary n-vertex forest, where the trees are subject to joining and splitting by, respectively, adding and removing edges. Depending on the application, information can be associated to nodes or edges (or both), and queries might require to combine values in path or (sub)trees. In this paper we present a novel data structure, called the Depth First Tour Tree, based on a linearization of a DFS visit of the tree. Despite the simplicity of the approach, similar to the ET-Trees (based on a Euler Tour), our data structure is able to answer queries related to both paths and (sub)trees. In particular, focusing on subtree computations, we show how to customize the data structure in order to answer queries for a concrete application: keeping track of the biconnectivity measures, including the impact of the removal of articulation points, of a dynamic undirected graph.

In this paper we address the problem of how to learn a structural prototype that can be used to represent the variations present in a set of trees. The prototype serves as a pattern space representation for the set of trees. To do this we construct a super-tree to span the union of the set of trees. This is a chicken and egg problem, since before the structure can be estimated correspondences between the nodes of the super-tree and the nodes of the sample tree must be to hand. We demonstrate how to simultaneously estimate the structure of the super-tree and recover the required correspondences by minimizing the sum of the tree edit-distances over pairs of trees, subject to edge consistency constraints. Each node of the super-tree corresponds to a dimension of the pattern space, and for each tree we construct a pattern vector in which the elements of the weights corresponding to each of the dimensions of the super-tree. We perform pattern analysis on the set of trees by performing principal components analysis on the vectors. The method is illustrated on a shape analysis problem involving shock-trees extracted from the skeletons of 2D objects.

This paper introduces a concept and design of decision trees based on information granules - multivariable entities characterized by high homogeneity (low variability). As such granules are developed via fuzzy clustering and play a pivotal role in the growth of the decision trees, they will be referred to as C-fuzzy decision trees. In contrast with "standard" decision trees in which one variable (feature) is considered at a time, this form of decision trees involves all variables that are considered at each node of the tree. Obviously, this gives rise to a completely new geometry of the partition of the feature space that is quite different from the guillotine cuts implemented by standard decision trees. The growth of the C-decision tree is realized by expanding a node of tree characterized by the highest variability of the information granule residing there. This paper shows how the tree is grown depending on some additional node expansion criteria such as cardinality (number of data) at a given node and a level of structural dependencies (structurability) of data existing there. A series of experiments is reported using both synthetic and machine learning data sets. The results are compared with those produced by the "standard" version of the decision tree (namely, C4.5).

The tree matching problem is considered of given labeled trees P and T , determining if the pattern tree P can be obtained from the text tree T by deleting degree-one and degree-two nodes and, in the case of unordered trees, by also permuting siblings. The constrained tree inclusion problem is more sensitive to the structure of the pattern tree than the general tree inclusion problem. Further, it can be solved in polynomial time for both unordered and ordered trees. Algorithms based on the restricted subtree homeomorphism algorithm of M.-J. Chung [J. Algorithms 8 (1) (1987) 106–112] are presented that solve the constrained tree inclusion problem in O ( m 1.5 n ) time on unordered trees with m and n nodes, and in O ( m n ) time on ordered trees, using O ( m n ) additional space.

The notion of the tree edit distance provides a unifying framework for measuring distance and finding approximate common patterns between two trees. A diversity of tree edit distance measures have been proposed to deal with tree related problems, such as minor containment, maximum common subtree isomorphism, maximum common embedded subtree, and alignment of trees. These classes of problems are characterized by the conditions of the tree mappings, which specify how to associate the nodes in one tree with the nodes in the other. In this paper, we study the declarative semantics of edit distance measures based on the tree mapping. In prior work, the edit distance measures have been not well-formalized. So the relationship among various algorithms based on the tree edit distance has hardly been studied. Our framework enables us to study the relationship. By using our framework, we reveal the declarative semantics of the alignment of trees, which has remained unknown in prior work.

Many optimizations have been done to 3DR-tree index structure and many opinions have been proposed. Modification by splitting mechanism is one of them. There are two index trees in 3DR-tree index structure after modification: one is a history tree for past data storage and the other is an active tree for current data storage. In this article, optimization of history tree is firstly done and is proved theoretically. Then a correspondent insert algorithm is designed.

We consider two tree statistics that extend in a natural way the parameters depth of a node resp. distance between two nodes. The ancestor-tree of p given nodes in a rooted tree T is the subtree of T, spanned by the root and these p nodes and generalizes the depth (ancestor-tree of a single node), whereas the spanning subtree induced by p given nodes in a tree T generalizes the distance (induced spanning subtree of two nodes). We study the random variables size of the ancestor-tree resp. spanning subtree size for two tree families, the simply generated trees and the recursive trees. We will assume here the random tree model and also that all () possibilities of selecting p nodes in a tree of size n are equally likely. For random simply generated trees we can then characterize for a fixed number p of chosen nodes the limiting distribution of both parameters as generalized Gamma distributions, where we prove the convergence of the moments too. For some specific simply generated tree families we can give exact formulae for the first moments. In the instance of random recursive trees, we will show that the considered parameters are asymptotically normally distributed, where we can give also exact formulae for the expectation and the variance. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004

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.

Fringe analysis uses the distribution of bottom subtrees or fringe of search trees under the assumption of random insertion of keys, yielding an average case analysis of the fringe. The results in the fringe give upper and lower bounds for several measures for the whole tree.We are interested in the fringe analysis of the synchronized parallel insertion algorithms of Paul, Vishkin, and Wagener (PVW) on 2–3 trees. This algorithm inserts k keys with k processors into a tree of size n with time O(logn+logk). As the direct analysis of this algorithm is very difficult we tackle this problem by introducing a new family of algorithms, denoted by MacroSplit algorithms, and our main theorem proves that two algorithms of this family, denoted MaxMacroSplit and MinMacroSplit, bound the behavior of the fringe in the PVW algorithm.Previous work deals with the fringe analysis of sequential algorithms, but this type of analysis was still an open problem for parallel algorithms on search trees. We extend fringe analysis to parallel algorithms and we get a rich mathematical structure giving new interpretations even in the sequential case. We prove that random insertion of keys generates a binomial distribution, that the synchronized insertion of keys can be modeled by a Markov chain, and that the coefficients of the transition matrix of the Markov chain are related to the expected local behavior of our algorithm. Finally, we show that the coefficients of the power expansion of this matrix over (n+1)−1 are the binomial transform of the expected local behavior of the algorithm. We finally show that the fringe of the PVW algorithm asymptotically converges to the sequential case.

Plagiarism is a form of cheating that has been so much happen. One of prevention is to make the anti-plagiarism system. The system that must compare a query document with all documents in the database requires a very long time. The more irrelevant document in database compare with the query that will be matched will waste the time. This paper will discuss a system to detect plagiarism by using indexing method as a way to eliminate irrelevant documents in order to reduce the document database that will be matched with the query document. Matching between a query document and documents in database will be done with Longest Common Subsequence (LCS) algorithm. The system will use inverted index as the form to eliminate irrelevant documents using a 2-3 tree data structure. Indexing is done by inserting the fingerprint of the document. To find the fingerprint this paper will use winnowing algorithm. The results of the system shows to execute 1 query and 10000 documents corpus, most of them are not relevant, takes 59 seconds and 134 seconds with and without respectively. The f-measure value, the average value of precision and recall, is obtained 0.7387 by indexing with 0.15 as the threshold of indexing elimination and 0.000428 without indexing.

Given a set S of n points on Rd, we show, for fixed d, how to construct in O(nlogn) time a data structure we call the balanced aspect ratio (BAR) tree. A BAR tree is a binary space partition tree on S that has O(logn) depth in which every region is convex and “fat” (that is, has a bounded aspect ratio). While previous hierarchical data structures such as k-d trees, quadtrees, octrees, fair-split trees, and balanced box decompositions can guarantee some of these properties, we know of no previous data structure that combines all of these properties simultaneously. The BAR tree data structure has numerous applications ranging from geometric searching problems in fixed dimensional space to the visualization of graphs and three-dimensional worlds.

A method to determine the least central subtree of a tree is given. The structure of the trees having a single point as a least central subtree is described, and the relation of a least central subtree of a tree to the centroid as well as to the center of that tree is given.

We study the state complexity of regular tree languages for tree matching problem. Given a tree t and a set of pattern trees L, we can decide whether or not there exists a subtree occurrence of trees in L from the tree t by considering the new language L′ which accepts all trees containing trees in L as subtrees. We consider the case when we are given a set of pattern trees as a regular tree language and investigate the state complexity. Based on the sequential and parallel tree concatenation, we define three types of tree languages for deciding the existence of different types of subtree occurrences. We also study the deterministic top-down state complexity of path-closed languages for the same problem.

A central problem in wide-area networks is to efficiently multicast a message to all members (hosts) of a target group. One of the most effective methods to multicast a message is to send the message along the edges of a spanning tree connecting all the members of the group. In this paper, we propose a new fully distributed algorithm to build a minimum spanning tree (MST) in a generic communication network. During the execution, the algorithm maintains a collection of disjoint trees spanning all the group members. Every tree, which initially consists of only one node, independently expands by joining the closest tree, until all of the nodes are connected in a single tree. The resulting communication topology is both robust (there are no singularities subject to failures) and scalable (every node stores a limited amount of local information that is independent of the size of the network).

The directed topology tree data structure is developed for maintaining binary trees dynamically. Each of a certain set of tree operations is shown to takeO(logn) time, wherenis the number of vertices in the trees. The directed topology trees are used to implement link?cut trees and dynamic expression trees. The results of experimental comparisons with the dynamic trees of Sleator and Tarjan are presented.

We introduce the bucket recursive tree, a generalization of recursive trees. The tree grows from a succession of integer labels that join the multitype nodes of the tree according to a stochastic rule. We study the multivariate structure of the tree and obtain a multivariate central limit theorem for the joint distribution of the number of nodes of different types for trees with bucket size b ⩽ 26. For trees with b > 26 a phase change in the distribution is detected and the central limit theorem does not hold. Recent results on the extended Pólya urn models (Smythe, 1995) provide the basic tool to reach these results. Two kinds of distances are also studied: The tree height and the depth of the nth label. Strong laws for the height are obtained via a technique based on introducing “ghost nodes”, then removing them. The ghost nodes create a companion tree that relates our tree to Biggins' (1976) first- and last-birth problem in a multitype process. A weak law for the depth is obtained by formulating and asymptotically manipulating the depth probability generating function.

The red-black trees are binary trees in which a longest path from every node v to a leaf is at most twice as long as a shortest path from v to a leaf. We examine sequences of simple insertions (insertions without promotions or any other restructuring operations) in red-black trees. We prove that the case of red-black trees is the same as the class of trees that is defined by an insertion algorithm for red-black trees that uses promotions to restore balance. The proof demonstrates that every red-black tree can be built from the empty tree by a sequence of simple insertions We also prove that every red-black tree contains a skinny red-black subtree of the same height (a red-black tree with the smallest number of nodes for its height) by giving a sequence of simple insertions that can be used to build the given red-black tree from the skinny red-black subtree. From this result we conclude that the skinny red-black trees have the minimum path length among all red-black trees of the same height, a result that seems intuitively obvious but whose proof is not.

Cloud computing is getting increasingly popular, but has yet to be widely adopted arguably because there are many security and privacy problems that have not been adequately addressed. A specific problem encountered in the context of cloud storage, where clients outsource their data (files) to untrusted cloud storage servers, is to convince the clients that their data are kept intact at the storage servers. An important approach to achieve this goal is called Proof of Retrievability (POR), by which a storage server can convince a client --- via a concise proof --- that its data can be recovered. However, existing POR solutions can only deal with static data (i.e., data items must be fixed), and actually are not secure when used to deal with dynamic data (i.e., data items need be inserted, deleted, and modified). Motivated by the need to securely deal with dynamic data, we propose the first dynamic POR scheme for this purpose. Moreover, we introduce a new property, called fairness, which is necessary and also inherent to the setting of dynamic data because, without ensuring it, a dishonest client could legitimately accuse an honest cloud storage server of manipulating its data. Our solution is based on two new tools, one is an authenticated data structure we call range-based 2-3 trees (rb23Tree for short), and the other is an incremental signature scheme we call hash-compress-and-sign (HCS for short). These tools might be of independent value as well.

This chapter covers Schuman's genealogy, the derivation of his first and middle names, and the change in spelling of his last name. The lives of his paternal great-grandparents, both sets of grandparents, and his parents are covered, with emphasis on Schuman's German Jewish ancestry. The service of Samuel Schuhmann, Bill's father, in the Spanish-American War is mentioned as well as Sam's colorful past. Schuman grew up around relatives who were committed to their professional lives and noncommittal to their religious lives, and their priorities are reflected in Schuman's later life choices. Schuman's association with Manhattan is established in this chapter.

This paper presents the first concurrent non-blocking k-ary search tree. Our data structure generalizes the recent non-blocking binary search tree of Ellen et al. [5] to trees in which each internal node has k children. Larger values of k decrease the depth of the tree, but lead to higher contention among processes performing updates to the tree. Our Java implementation uses single-word compare-and-set operations to coordinate updates to the tree. We present experimental results from a 16-core Sun machine with 128 hardware contexts, which show that our implementation achieves higher throughput than the non-blocking skip list of the Java class library and the leading lock-based concurrent search tree of Bronson et al. [3].

Tree structures play an important role in computer science. For instance, the binary tree is a fundamental data structure for rapidly storing sorted data and rapidly retrieving stored data. In this paper, we establish the structures of k-noncrossing trees and k-proper trees. Moreover, the relations between these structures and k-ary trees are also constructed. It exposes that such structures may be employed as efficient data structures for computer and information science.

We propose a pipelined Dynamic Search Tree (pDST) on FPGA which offers high throughput for lookup, insert and delete operations as well as the capability to perform in-place incremental updates. Based on the pipelined 2-3 tree data structure, our pDST supports one lookup per clock cycle and maintains tree balance under continual insert and delete operations. A novel buffered update scheme together with a bi-directional linear pipeline allows the pDST to perform one insert or delete operation per O(log N) cycles (N being the tree capacity) without stalling the lookup operations. Nodes at each pipeline stage are allocated and freed by a free-node chaining mechanism which greatly simplifies the memory management circuit. Our prototype implementation of a 15-level, 32-bit key dual-port pDST requires 192 blocks of 36 Kb BRAMs (64%) and 12.8k LUTs (6.3%) on a Virtex 5 LX330 FPGA. The circuit has a maximum capacity of 96k 32-bit keys and clock rate of 135 MHz, supporting 242 million lookups and concurrently 3.97 million inserts or deletes per second.

An XML tree pattern query, represented as a labeled tree, is essentially a complex selection predicate on both structure and content of an XML. Tree pattern matching has been identified as a core operation in querying XML data. However, almost all the proposed algorithms only deal with unordered trees, by which the order of siblings is not considered. In this paper, we discuss a new algorithm for processing ordered tree pattern queries, for which not only the ancestor-descendant and parent-child relationships, but also the order of siblings are significant. The time complexity of the algorithm is bounded by O(|D||Q| + |T|leafQ) and its space overhead is by O(leafTleafQ), where T stands for a document tree, Q for a tree pattern query and D is a largest data stream associated with a query node q of Q, which contains the database nodes that match the node predicate at q. leafT (leafQ) represents the number of the leaf nodes of T (resp. Q). In addition, the algorithm can be adapted to an indexing environment with XB-trees being used. Experiments have been conducted, which shows that the new algorithm is promising.

The previously fastest algorithms for computing the R* consensus tree of two given (rooted) phylogenetic trees T1 and T2 with a leaf label set of cardinality n run in Θ(n3) time [3, 8]. In this manuscript, we describe a new O(n2 log n)-time algorithm to solve the problem. This is a significant improvement because the R* consensus tree is defined in terms of a set Rmaj which may contain Ω(n3) elements, so any direct approach which explicitly constructs Rmaj requires Ω(n3) time.

Self-adjusting trees are data structures that modify their own structure to reflect the probabilistic nature of access patterns. The splay tree of Tarjan and Sleator performs tree operations in amortized O(log n) time. The splay operation moves an accessed node all the way to the root of the tree, and thus may not be the most efficient type of self-adjustment. In this paper several variations of the splay tree are described. Simulations are used to compare the optimality of the searches done by these trees for various patterns of data access.

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.

We study the optimal tree structure for the key management problem. In the key tree, when two or more leaves are deleted or replaced, the updating cost is defined to be the number of encryptions needed to securely update the remaining keys. Our objective is to find the optimal tree structure where the worst case updating cost is minimum. We first prove the degree upper bound (k + 1)2 - 1 when k leaves are deleted from the tree. Then we focus on the 2-deletion problem and prove that the optimal tree is a balanced tree with certain root degree 5 ≤ d ≤ 7 where the number of leaves in the subtrees differs by at most one and each subtree is a 2-3 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.

Tree edit distance is one of the most frequently used distance measures for comparing trees. When using the tree edit distance, we need to determine the cost of each operation, but this is a labor-intensive and highly skilled task. This paper proposes an algorithm for learning the costs of tree edit operations from training data consisting of pairs of similar trees. To formalize the cost learning problem, we define a probabilistic model for tree alignment that is a variant of tree edit distance. Then, the parameters of the model are estimated using the expectation maximization (EM) technique. In this paper, we develop an algorithm for parameter learning that is polynomial in time (O{mn2d6)) and space (O{n2d4)) where n, d, and m represent the size of the trees, the maximum degree of trees, and the number of training pairs of trees, respectively.

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.

This report contains 70 sets of software fault trees used to test a software fault tree key node safety metric. Each page represents a set often trees with an identical root node hazard. To the left of the initial tree on each page arc the negatively mutated trees. To the right are the positively mutated trees. Under each tree is the value produced by the metric equation, (S), when run on the tree.

Simple families of increasing trees can be constructed from simply generated tree families, if one considers for every tree of size $n$ all its increasing labellings, i.$\,$e. labellings of the nodes by distinct integers of the set $\{1, \dots, n\}$ in such a way that each sequence of labels along any branch starting at the root is increasing. Three such tree families are of particular interest: recursive trees, plane-oriented recursive trees and binary increasing trees. We study the quantity number of descendants of node $j$ in a random tree of size $n$ and give closed formulæ for the probability distribution and all factorial moments for those subclass of tree families, which can be constructed via an insertion process. Furthermore limiting distribution results of this parameter are given.

The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts of a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the XPath evaluation problem on trees that are compressed via straight-line context-free tree grammars is investigated.

Consider an ordered, static tree /spl Tscr/ on t nodes where each node has a label from alphabet set /spl Sigma/. Tree /spl Tscr/ may be of arbitrary degree and of arbitrary shape. Say, we wish to support basic navigational operations such as find the parent of node u, the ith child of u, and any child of it with label /spl alpha/. In a seminal work over fifteen years ago, Jacobson (1989) observed that pointer-based tree representations are wasteful in space and introduced the notion of succinct data structures. He studied the special case of unlabeled trees and presented a succinct data structure of 2t + o(t) bits supporting navigational operations in O(1) time. The space used is asymptotically optimal with the information-theoretic lower bound averaged over all trees. This led to a slew of results on succinct data structures for arrays, trees, strings and multisets. Still, for the fundamental problem of structuring labeled trees succinctly, few results, if any, exist even though labeled trees arise frequently in practice, e.g. in the data as in markup text (XML) or in augmented data structures. We present a novel approach to the problem of succinct manipulation of labeled trees by designing what we call the xbw transform of the tree, in the spirit of the well-known Burrows-Wheeler transform for strings. The xbw transform uses path-sorting and grouping to linearize the labeled tree /spl Tscr/ into two coordinated arrays, one capturing the structure and the other the labels. Using the properties of the xbw transform, we (i) derive the first-known (near-)optimal results for succinct representation of labeled trees with O(1) time for navigation operations, (ii) optimally support the powerful subpath search operation for the first time, and (iii) introduce a notion of tree entropy and present linear time algorithms for compressing a given labeled tree up to its entropy beyond the information-theoretic lower bound averaged over all tree inputs. Our xbw transform is simple and likely to spur new results in the theory of tree compression and indexing, and may have some practical impact in XML data processing.

We describe a linear algorithm for comparing two similar ordered rooted trees with node labels. The method for comparing trees is the usual tree edit distance. We show that an optimal mapping which uses at most k insertions or deletions can then be constructed in O(nk3) where n is the size of the trees. The approach is inspired by the Zhang-Shasha algorithm for tree edit distance in combination with an adequate pruning of the search space.

Frequent structure mining (FSM) aims to discover and extract patterns frequently occurring in structural data, such as trees and graphs. FSM finds many applications in bioinformatics, XML processing, Web log analysis, and so on. We present a new FSM technique for finding patterns in rooted unordered labeled trees. The patterns of interest are cousin pairs in these trees. A cousin pair is a pair of nodes sharing the same parent, the same grandparent, or the same great-grandparent, etc. Given a tree T, our algorithm finds all interesting cousin pairs of T in O(|T|/sup 2/) time where |T| is the number of nodes in T. Experimental results on synthetic data and phylogenies show the scalability and effectiveness of the proposed technique. To demonstrate the usefulness of our approach, we discuss its applications to locating co-occurring patterns in multiple evolutionary trees, evaluating the consensus of equally parsimonious trees, and finding kernel trees of groups of phylogenies. We also describe extensions of our algorithms for undirected acyclic graphs (or free trees).

Due to the rapid growth of tree structured data or semistructured data such as Web documents, efficient learning of structural features from tree structured data becomes more and more important. In order to represent tree structured patterns with rich structural features, we introduce a new type of structural variables, called height-constrained variables. An (i,j)-height-constrained variable can be replaced with any tree such that the trunk length of the tree is at least i and the height of the tree is at most j. Then, we define a term tree as a rooted tree pattern with ordered children and height-constrained variables. The minimal language (MINL) problem for term trees is to find a term tree t such that the language generated by t is minimal among languages, generated by term trees, which contains all given tree structured data. Let OTTh be the set of all term trees with (i,j)-height-constrained variables for any i and j (1 ≤ i ≤ j) and no variable-chain. We assume that there are at least two edge labels. In this paper, we give a polynomial time algorithm for the MINL problem for OTTh. Thus we show that the class OTTh is polynomial time inductively inferable from positive data.

We consider the polynomial time learnability of ordered tree patterns with internal structured variables, in the query learning model of Angluin (1988). An ordered tree pattern with internal structured variables, called a term tree, is a representation of a tree structured pattern in semistructured or tree structured data such as HTML/XML files. Standard variables in term trees can be substituted by an arbitrary tree of arbitrary height. In this paper, we introduce a new type of variables, which are called height-bounded variables. An i-height-bounded variable can be replaced with any tree of height at most i. By this type of variables, we can define tree structured patterns with rich structural features. We assume that there are at least two edge labels. We give a polynomial time algorithm for term trees with height-bounded variables using membership queries and one positive example. We also give hardness results which indicate that one positive example is necessary to learn term trees with height-bounded variables.

An unordered labeled tree is a tree in which each node has a string label and the parent-child relationship is significant, but the order among siblings is unimportant. This paper presents an approach to the nearest neighbor search problem for these trees. Given a database D of unordered labeled trees and a query tree Q, the goal is to find those trees in D that "approximately" contain Q. Our approach is based on storing the paths of the trees in a suffix array and then counting the number of mismatching paths between the query tree and a data tree. To speed up a search, we use a hash-based technique to filter out unqualified data trees at an early stage of the search. Experimental results obtained by running our techniques on phylogenetic trees and synthetic data demonstrate the good performance of the proposed approach. We also discuss the use of our work in XML and scientific database management.