Computing all subtree repeats in ordered trees

We consider the problem of computing all subtree repeats in a given labeled ordered tree. We first transform the tree to a string representing its postfix notation, and then present an algorithm based on the bottom-up technique to solve it. The proposed algorithm consists of two phases: the preprocessing phase and the phase where all subtree repeats are computed. The linear time and space complexity of the proposed algorithm are important parts of its quality.     

Mining frequent closed rooted trees

Many knowledge representation mechanisms are based on tree-like structures, thus symbolizing the fact that certain pieces of information are related in one sense or another. There exists a well-studied process of closure-based data mining in the itemset framework: we consider the extension of this process into trees. We focus mostly on the case where labels on the nodes are nonexistent or unreliable, and discuss algorithms for closure-based mining that only rely on the root of the tree and the link structure. We provide a notion of intersection that leads to a deeper understanding of the notion of support-based closure, in terms of an actual closure operator. We describe combinatorial characterizations and some properties of ordered trees, discuss their applicability to unordered trees, and rely on them to design efficient algorithms for mining frequent closed subtrees both in the ordered and the unordered settings. Empirical validations and comparisons with alternative algorithms are provided.     

Mining closed and maximal frequent subtrees from databases of labeled rooted trees

Tree structures are used extensively in domains such as computational biology, pattern recognition, XML databases, computer networks, and so on. One important problem in mining databases of trees is to find frequently occurring subtrees. Because of the combinatorial explosion, the number of frequent subtrees usually grows exponentially with the size of frequent subtrees and, therefore, mining all frequent subtrees becomes infeasible for large tree sizes. We present CMTreeMiner, a computationally efficient algorithm that discovers only closed and maximal frequent subtrees in a database of labeled rooted trees, where the rooted trees can be either ordered or unordered. The algorithm mines both closed and maximal frequent subtrees by traversing an enumeration tree that systematically enumerates all frequent subtrees. Several techniques are proposed to prune the branches of the enumeration tree that do not correspond to closed or maximal frequent subtrees. Heuristic techniques are used to arrange the order of computation so that relatively expensive computation is avoided as much as possible. We study the performance of our algorithm through extensive experiments, using both synthetic data and data sets from real applications. The experimental results show that our algorithm is very efficient in reducing the search space and quickly discovers all closed and maximal frequent subtrees.     

Drawing rooted trees in linear time

The aim of automatic graph drawing is the development of algorithms for creating nice and easily readable layouts of abstractly given graphs. For the special case of rooted trees of unbounded degree, John Q. Walker II presented a drawing algorithm in this journal in 1990. This algorithm is an extension of the Reingold–Tilford algorithm. It yields very good results and is therefore widely used. Furthermore, it is widely assumed to run in linear time, as the author claims in his article. However, the algorithm in its presented form clearly needs quadratic runtime. We explain the reasons for that and state a revised algorithm that creates the same layouts in linear time. Copyright © 2006 John Wiley & Sons, Ltd.     

The weight-constrained maximum-density subtree problem and related problems in trees

Given a tree T=(V,E) of n nodes such that each node v is associated with a value-weight pair (val _v ,w _v ), where value val _v is a real number and weight w _v is a non-negative integer, the density of T is defined as \(\frac{\sum_{v\in V}{\mathit{val}}_{v}}{\sum_{v\in V}w_{v}}\). A subtree of T is a connected subgraph (V′,E′) of T, where V′?V and E′?E. Given two integers w _min? and w _max?, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=(V′,E′) satisfying w _min?≤∑_v∈V′ w _v ≤w _max?. In this paper, we first present an O(w _max? n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S?V, we also present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.     

Complexity analysis of balloon drawing for rooted trees

In a balloon drawing of a tree, all the children under the same parent are placed on the circumference of the circle centered at their parent, and the radius of the circle centered at each node along any path from the root reflects the number of descendants associated with the node. Among various styles of tree drawings reported in the literature, the balloon drawing enjoys a desirable feature of displaying tree structures in a rather balanced fashion. For each internal node in a balloon drawing, the ray from the node to each of its children divides the wedge accommodating the subtree rooted at the child into two sub-wedges. Depending on whether the two sub-wedge angles are required to be identical or not, a balloon drawing can further be divided into two types: even sub-wedge and uneven sub-wedge types. In the most general case, for any internal node in the tree there are two dimensions of freedom that affect the quality of a balloon drawing: (1) altering the order in which the children of the node appear in the drawing, and (2) for the subtree rooted at each child of the node, flipping the two sub-wedges of the subtree. In this paper, we give a comprehensive complexity analysis for optimizing balloon drawings of rooted trees with respect to angular resolution, aspect ratio and standard deviation of angles under various drawing cases depending on whether the tree is of even or uneven sub-wedge type and whether (1) and (2) above are allowed. It turns out that some are NP-complete while others can be solved in polynomial time. We also derive approximation algorithms for those that are intractable in general.     

Lexicographic generation of ordered trees

We show a one-one correspondence between all the regular binary trees with n internal nodes and certain integer sequences, an algorithm for generating these trees lexicographically, and the ranking function and the corresponding unranking procedure. We then extend the generating algorithm to k-ary trees, and analyze the amount of work done per tree. Relations to existing algorithms are discussed.     

The average height of r-typly rooted planted plane trees

In this paper we generalize a result of de Bruijn, Knuth und Rice concerning the average height of planted plane trees withn nodes. First we compute the number of allr-typly rooted planted plane trees (r-trees) withn nodes and height less than or equal tok. Assuming that all planted plane trees withn nodes are equally likely, we show, that in the average a planted plane tree is a 3-tree for largen; for this distribution we compute also the cumulative distribution function and the variance. Finally, we shall derive an exact expression and its asymptotic equivalent for the average height \(\bar h_r \) (n) of anr-tree withn nodes. We obtain for all ε>0 $$\bar h_r (n) = \sqrt {\pi n} - \frac{1}{2}(r - 2) + O(1n(n)/n^{1/2 - \varepsilon } ).$$      

Canonical forms for labelled trees and their applications in frequent subtree mining

Tree structures are used extensively in domains such as computational biology, pattern recognition, XML databases, computer networks, and so on. In this paper, we first present two canonical forms for labelled rooted unordered trees–the breadth-first canonical form (BFCF) and the depth-first canonical form (DFCF). Then the canonical forms are applied to the frequent subtree mining problem. Based on the BFCF, we develop a vertical mining algorithm, RootedTreeMiner, to discover all frequently occurring subtrees in a database of labelled rooted unordered trees. The RootedTreeMiner algorithm uses an enumeration tree to enumerate all (frequent) labelled rooted unordered subtrees. Next, we extend the definition of the DFCF to labelled free trees and present an Apriori-like algorithm, FreeTreeMiner, to discover all frequently occurring subtrees in a database of labelled free trees. Finally, we study the performance and the scalability of our algorithms through extensive experiments based on both synthetic data and datasets from real applications.     

Improved approximation of the largest common subtree of two unordered trees of bounded height

We present a polynomial time 1.5h-approximation algorithm for the problem of finding the largest common subtree between two rooted, labeled, and unordered trees of height at most h, where a tree S is called a subtree of a tree T if S is obtained from T by deletion of some nodes in T. This result improves the previous 2h-approximation algorithm.     

一种适用于顺序XML树的前缀编码方法

在对XML数据模型和XML查询语言中的顺序性进行分析的基础上,提出了一种用于顺序XML树的前缀编码方法,并从唯一性、确定性、动态性、灵活性和简洁性五个方面论证了这种编码的正确性和有效性;同时,运用分层编码的思想解决当XML文档规模增大时编码长度增加的问题。     

A metric for rooted trees with unlabeled vertices based on nested parentheses

In this paper, we propose a new metric for rooted trees with unlabeled vertices based on alignments of nested parenthesis strings. We prove that the time complexity for computing this metric is NP-hard and present a 1.5-approximation algorithm for it.     

POTMiner: mining ordered, unordered, and partially-ordered trees

Non-linear data structures are becoming more and more common in data mining problems. Trees, in particular, are amenable to efficient mining techniques. In this paper, we introduce a scalable and parallelizable algorithm to mine partially-ordered trees. Our algorithm, POTMiner, is able to identify both induced and embedded subtrees in such trees. As special cases, it can also handle both completely ordered and completely unordered trees.     

用有序FP-tree挖掘最大频繁项集

提出了完全前缀路径和有序FP-tree的概念,给出根据数据项所在的层建立有序FP-tree的方法,利用有序FP-tree表示数据.提出用有序FP-tree中的完全前缀路径进行最大频繁项集挖掘的算法——MFIM算法,该算法利用有序FP-tree中的完全前缀路径对挖掘算法进行优化.实验结果表明,该算法对于浓密数据集中挖掘长模式具有较好的性能.     

A note on a result of R. Kemp on R-typly rooted planted plane trees

R. Kemp has shown that the average height of r-tuply rooted planted plane trees is $$\sqrt {\pi n} - \frac{1}{2}(r - 2) + O(\log (n)n^{1/2 - \varepsilon } ), \varepsilon > 0, n \to \infty ,$$ assuming that all such trees withn nodes are equally likely. We give a quite short proof of this result (with an error term ofO (1)).