Search

The rapid development of Internet of Medical Things (IoMT) is remarkable. However, IoMT faces many problems including privacy disclosure, long delay of service orders, low retrieval efficiency of medical data, and high energy cost of fog computing. For these, this paper proposes a data privacy protection and efficient retrieval scheme for IoMT based on low-cost fog computing. First, a fog computing system is located between a cloud server and medical workers, for processing data retrieval requests of medical workers and orders for controlling medical devices. Simultaneously, it preprocesses physiological data of patients uploaded by IoMT, collates them into various data sets, and transmits them to medical institutions in this way. It makes the entire execution process of low latency and efficient. Second, multidimensional physiological data are of great value, and we use ciphertext retrieval to protect privacy of patient data in this paper. In addition, this paper uses range tree to build an index for storing physiological data vectors, and meanwhile a range retrieval method is also proposed to improve data search efficiency. Finally, bat algorithm (BA) is designed to allocate cost on a fog server group for significant energy cost reduction. Extensive experiments are conducted to demonstrate the efficiency of the proposed scheme.

This article presents a fast algorithm for finding the Adams consensus tree of a set of conflicting phylogenetic trees with identical leaf labels. Its worst-case running time is O ( k n log ⁡ n ) , where k is the number of input trees and n is the size of the leaf label set; in comparison, the original algorithm of Adams has a worst-case running time of O ( k n 2 ) . To achieve subquadratic running time, the centroid path decomposition technique is applied in a novel way that traverses the input trees by following a centroid path in each of them in unison. For k = 2 , an even faster algorithm running in O ( n ⋅ log ⁡ n log ⁡ log ⁡ n ) time is provided, which relies on an extension of the wavelet tree-based technique of Bose et al. for orthogonal range counting on a grid. Our extended wavelet tree data structure also supports truncated range maximum/minimum queries efficiently.

A simple linear-time algorithm for constructing a linear context-free tree grammar of size O(rg + r g log (n/r g))for a given input tree T of size n is presented, where g is the size of a minimal linear context-free tree grammar for T, and r is the maximal rank of symbols in T (which is a constant in many applications). This is the first example of a grammar-based tree compression algorithm with a good, i.e. logarithmic in terms of the size of the input tree, approximation ratio. The analysis of the algorithm uses an extension of the recompression technique from strings to trees., Comment: 45 pages, published in Information and Computation. Approximation ratio improved since the first version, figures improved, some examples added. A small calculation error corrected since the previous version (all claims hold as previously)

A tree $t$-spanner $T$ of a graph $G$ is a spanning tree of $G$ such that the distance in $T$ between every pair of verices is at most $t$ times the distance in $G$ between them. There are efficient algorithms that find a tree $t\cdot O(\log n)$-spanner of a graph $G$, when $G$ admits a tree $t$-spanner. In this paper, the search space is narrowed to $v$-concentrated spanning trees, a simple family that includes all the breadth first search trees starting from vertex $v$. In this case, it is not easy to find approximate tree spanners within factor almost $o(\log n)$. Specifically, let $m$ and $t$ be integers, such that $m>0$ and $t\geq 7$. If there is an efficient algorithm that receives as input a graph $G$ and a vertex $v$ and returns a $v$-concentrated tree $t\cdot o((\log n)^{m/(m+1)})$-spanner of $G$, when $G$ admits a $v$-concentrated tree $t$-spanner, then there is an algorithm that decides 3-SAT in quasi-polynomial time.

In order to conduct a statistical analysis on a given set of phylogenetic gene trees, we often use a distance measure between two trees. In a statistical distance-based method to analyze discordance between gene trees, it is a key to decide "biological meaningful" and "statistically well-distributed" distance between trees. Thus, in this paper, we study the distributions of the three tree distance metrics: the edge difference, the path difference, and the precise $K$ interval cospeciation distance, between two trees: first, we focus on distributions of the three tree distances between two random unrooted trees with $n$ leaves ($n \geq 4$); and then we focus on the distributions the three tree distances between a fixed rooted species tree with $n$ leaves and a random gene tree with $n$ leaves generated under the coalescent process with given the species tree. We show some theoretical results as well as simulation study on these distributions., 18 pages, 11 figures

Hierarchical data are often modelled as trees. An interesting query identifies pairs of similar trees. The standard approach to tree similarity is the tree edit distance, which has successfully been applied in a wide range of applications. In terms of runtime, the state-of-the-art algorithm for the tree edit distance is RTED, which is guaranteed to be fast independent of the tree shape. Unfortunately, this algorithm requires up to twice the memory of its competitors. The memory is quadratic in the tree size and is a bottleneck for the tree edit distance computation.In this paper we present a new, memory efficient algorithm for the tree edit distance, AP-TED (All Path Tree Edit Distance). Our algorithm runs at least as fast as RTED without trading in memory efficiency. This is achieved by releasing memory early during the first step of the algorithm, which computes a decomposition strategy for the actual distance computation. We show the correctness of our approach and prove an upper bound for the memory usage. The strategy computed by AP-TED is optimal in the class of all-path strategies, which subsumes the class of LRH strategies used in RTED. We further present the AP-TED+ algorithm, which requires less computational effort for very small subtrees and improves the runtime of the distance computation. Our experimental evaluation confirms the low memory requirements and the runtime efficiency of our approach. HighlightsWe address the memory problem of the strategy computation in the RTED algorithm for the tree edit distance.We prove an upper bound which guarantees that the strategy computation never uses more memory than the distance computation.We compute the optimal strategy in the class of all-path strategies which subsumes the LRH strategies used before.We develop new single-path functions which are better in terms of runtime and memory than the previously used functions.

Let P be a set of n colored points in the plane. Introduced by Hart [7], a consistent subset of P, is a set \(S\subseteq P\) such that for every point p in \(P\setminus S\), the closest point of p in S has the same color as p. The consistent subset problem is to find a consistent subset of P with minimum cardinality. This problem is known to be NP-complete even for two-colored point sets. Since the initial presentation of this problem, aside from the hardness results, there has not been significant progress from the algorithmic point of view. In this paper we present the following algorithmic results: 1. The first subexponential-time algorithm for the consistent subset problem. 2. An \(O(n\log n)\)-time algorithm that finds a consistent subset of size two in two-colored point sets (if such a subset exists). Towards our proof of this running time we present a deterministic \(O(n \log n)\)-time algorithm for computing a variant of the compact Voronoi diagram; this improves the previously claimed expected running time. 3. An \(O(n\log ^2 n)\)-time algorithm that finds a minimum consistent subset in two-colored point sets where one color class contains exactly one point; this improves the previous best known \(O(n^2)\) running time which is due to Wilfong (SoCG 1991). 4. An O(n)-time algorithm for the consistent subset problem on collinear points that are given from left to right; this improves the previous best known \(O(n^2)\) running time. 5. A non-trivial \(O(n^6)\)-time dynamic programming algorithm for the consistent subset problem on points arranged on two parallel lines.

In this paper, we design parallel write-efficient geometric algorithms that perform asymptotically fewer writes than standard algorithms for the same problem. This is motivated by emerging non-volatile memory technologies with read performance being close to that of random access memory but writes being significantly more expensive in terms of energy and latency. We design algorithms for planar Delaunay triangulation, $k$-d trees, and static and dynamic augmented trees. Our algorithms are designed in the recently introduced Asymmetric Nested-Parallel Model, which captures the parallel setting in which there is a small symmetric memory where reads and writes are unit cost as well as a large asymmetric memory where writes are $\omega$ times more expensive than reads. In designing these algorithms, we introduce several techniques for obtaining write-efficiency, including DAG tracing, prefix doubling, reconstruction-based rebalancing and $\alpha$-labeling, which we believe will be useful for designing other parallel write-efficient algorithms.

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.

The reconstruction of evolutionary trees from data sets on overlapping sets of species is a central problem in phylogenetics. Provided that the tree reconstructed for each subset of species is rooted and that these trees t together consistently, the space of all parent trees that ‘display’ these trees was recently shown to satisfy the following strong property: there exists a path from any one parent tree to any other parent tree by a sequence of local rearrangements (nearest neighbour interchanges) so that each intermediate tree also lies in this same tree space. However, the proof of this result uses a non-constructive argument. In this paper we describe a specic, polynomial-time procedure for navigating from any given parent tree to another while remaining in this tree space. The results are of particular relevance to the recent study of ‘phylogenetic terraces’.

This paper considers the problem of identifying all locations of subtrees in a large tree or in a large collection of trees that are similar to a specified pattern tree, where all trees are assumed to be rooted and node-labeled. The tree edit distance is a widely-used measure of tree (dis-)similarity, but is NP-hard to compute for unordered trees. To cope with this issue, we propose a new similarity measure which extends the concept of unordered tree inclusion by taking the costs of insertion and substitution operations on the pattern tree into account, and present an algorithm for computing it. Our algorithm has the same time complexity as the original one for unordered tree inclusion, i.e., it runs in $O(|T_1||T_2|)$ time, where $T_1$ and $T_2$ denote the pattern tree and the text tree, respectively, when the maximum outdegree of $T_1$ is bounded by a constant. Our experimental evaluation using synthetic and real datasets confirms that the proposed algorithm is fast and scalable and very useful for bibliographic matching, which is a typical entity resolution problem for tree-structured data. Furthermore, we extend our algorithm to also allow a constant number of deletion operations on $T_1$ while still running in $O(|T_1||T_2|)$ time.

Given a weighted graph G = ( V , E ) and a subset R of V, a Steiner tree in G is a tree which spans all vertices in R. The vertices in V ? R are called Steiner vertices. A full Steiner tree is a Steiner tree in which each vertex of R is a leaf. The full Steiner tree problem is to find a full Steiner tree with minimum weight. The bottleneck full Steiner tree problem is to find a full Steiner tree which minimizes the length of the longest edge. The k-bottleneck full Steiner tree problem is to find a bottleneck full Steiner tree with at most k Steiner vertices. The smallest full Steiner tree problem is to find a full Steiner tree with the minimum number of Steiner vertices.We show that the full Steiner tree problem in general graphs cannot be approximated within a factor of O ( log 2 - e ? | R | ) for any e 0 . We also provide a polynomial-time approximation factor preserving reduction from the full Steiner tree problem to the group Steiner tree problem. Based on that, the first approximation algorithm for the full Steiner tree problem in general graphs is obtained. Moreover, we show that the same hardness result holds for the node-weighted version of the full Steiner tree problem. We prove that it is NP-hard to approximate the k-bottleneck full Steiner tree problem within a factor of 2 - e . The smallest full Steiner tree problem is shown to be NP-complete and does not admit any polynomial-time O ( ( 1 - e ) ln ? n ) -approximation algorithm. The presented reductions show the connection between the full Steiner tree, the group Steiner tree, and the connected set cover problems. In addition, we present an O ( | E | log ? | V | ) time algorithm for the bottleneck full Steiner tree problem which relaxes the assumption, that G is a complete graph, in Chen et al. 7 algorithm.

Let P be a set of n points in the plane. The k-nearest-neighbor (abbreviated as k-NN) query problem is to preprocess P into a data structure that quickly reports k closest points in P for a query point q. This paper addresses a generalization of the k-NN query problem to a query set Q of points, namely, the group k-nearest-neighbor query problem, in the L 1 plane. More precisely, a query is assigned with a set Q of at most m points and a positive integer k with k ? n , and the distance between a point p of P and a query set Q is defined as the sum of L 1 distances from p to all q ? Q . The maximum number m of query points Q is assumed to be known in advance and to be at most n. In this paper, we propose two algorithms, one based on the range tree and the other based on a data structure for segment dragging queries, and obtain the following complexity bounds: (1) a group k-NN query can be handled in O ( T min log ? n + ( k + m 2 ) ( log ? log ? n + log ? m ) ) time after preprocessing P using O ( m 2 n log 2 ? n ) space, where T min = min ? { k + m , m 2 } , or (2) a group k-NN query can be handled in O ( ( k + m ) log 2 ? n + m 2 ( log ? ? n + log ? m ) ) time after preprocessing P using O ( m 2 n ) space, where ? 0 is an arbitrarily small constant. We also show that our approach can be applied to the weighted group k-nearest-neighbor query problem and the group k-farthest-neighbor query problem.

Given an edge-weighted graph G = ( V , E ) and a subset R of V, a Steiner tree of G is a tree which spans all the vertices in R. A full Steiner tree is a Steiner tree which has all the vertices of R as its leaves. The full Steiner tree problem is to find a full Steiner tree of G with minimum weight. In this paper we consider the full Steiner tree problem when G is a unit disk graph. We present a 20-approximation algorithm for the full Steiner tree problem in G. As for λ-precise unit disk graphs we present a ( 10 + 1 λ ) -approximation algorithm, where λ is the length of the shortest edge in G.

We consider the problem of multiple sequence alignment under a fixed evolutionary tree: given a tree whose leaves are labeled by sequences, find ancestral sequences to label its internal nodes so as to minimize the total length of the tree, where the length of an edge is the edit distance between the sequences labeling its endpoints. We present a new polynomial-time approximation algorithm for this problem, and analyze its performance on regular d-ary trees with d a constant. On such a tree, the algorithm finds a solution within a factor (d + 1)/(d − 1) of the minimum in O(kdT(d, n) + k2dn2) time, where k is the number of leaves in the tree, n is the length of the longest sequence labeling a leaf, and T(d, n) is the time to compute a Steiner point for d sequences of length at most n. (A Steiner point for a set S of sequences is a sequence P that minimizes the sum of the edit distances from P to each sequence in S . The time T(d, n) is O(d2dnd), given O(dsd+1)-time preprocessing for an alphabet of size s.) The approximation algorithm is conceptually simple and easy to implement, and actually applies to any metric space in which a Steiner point for any fixed-sized set can be computed in polynomial time. We also introduce a new problem, bottleneck tree-alignment, in which the objective is to label the internal nodes of the tree so as to minimize the length of the longest edge. We describe an exponential-time exact algorithm for the case of unit-cost edit operations, and show there is a simple linear-time approximation algorithm for the general case that finds a solution within a factor O(logk) of the minimum.

Efficient large-scale annotation of genomic intervals is essential for personal genome interpretation in the realm of precision medicine. There are 13 possible relations between two intervals according to Allen's interval algebra. Conventional interval trees are routinely used to identify the genomic intervals satisfying a coarse relation with a query interval, but cannot support efficient query for more refined relations such as all Allen's relations. We design and implement a novel approach to address this unmet need. Through rewriting Allen's interval relations, we transform an interval query to a range query, then adapt and utilize the range trees for querying. We implement two types of range trees: a basic 2-dimensional range tree (2D-RT) and an augmented range tree with fractional cascading (RTFC) and compare them with the conventional interval tree (IT). Theoretical analysis shows that RTFC can achieve the best time complexity for interval queries regarding all Allen's relations among the three trees. We also perform comparative experiments on the efficiency of RTFC, 2D-RT and IT in querying noncoding element annotations in a large collection of personal genomes. Our experimental results show that 2D-RT is more efficient than IT for interval queries regarding most of Allen's relations, RTFC is even more efficient than 2D-RT. The results demonstrate that RTFC is an efficient data structure for querying large-scale datasets regarding Allen's relations between genomic intervals, such as those required by interpreting genome-wide variation in large populations., Comment: 4 figures, 4 tables

In this short paper, we report the performance of multiple thread-parallel algorithms for spherical region queries on multicore architectures motivated by a challenging data analytics application in materials science. Performances of two tree-based algorithms and a naive algorithm are compared to identify the length scales at which these approaches perform optimally. The optimal algorithm is then used to scale the driving materials science application, which is shown to deliver over 17X speedup using 32 OpenMP threads on data sets containing many millions of atoms.

Suzuki and Niida (Ann. Pure. Appl. Logic, 2015) showed the following results on independent distributions (IDs) on an AND-OR tree, where they took only depth-first algorithms into consideration. (1) Among IDs such that probability of the root having value 0 is fixed as a given r such that 0 < r < 1, if d is a maximizer of cost of the best algorithm then d is an independent and identical distribution (IID). (2) Among all IDs, if d is a maximizer of cost of the best algorithm then d is an IID. In the case where non-depth-first algorithms are taken into consideration, the counter parts of (1) and (2) are left open in the above work. Peng et al. (Inform. Process. Lett., 2017) extended (1) and (2) to multi-branching trees, where in (2) they put an additional hypothesis on IDs that probability of the root having value 0 is neither 0 nor 1. We give positive answers for the two questions of Suzuki-Niida. A key to the proof is that if ID d achieves the equilibrium among IDs then we can chose an algorithm of the best cost against d from depth-first algorithms. In addition, we extend the result of Peng et al. to the case where non-depth-first algorithms are taken into consideration., 12 pages, 1 figure

As internet traffic is growing day by day, it is a key requirement to increase more and more IP addresses. IPv4 cannot accommodate this need due to the exhaustion of its 2 32 address. Hence in order to effectively satisfies this increase in demand for IP address new addressing scheme called IPv6 is developed. It has 2 128 addresses so the exhaustion is not possible in near future. To forward IPv4 packet efficient mechanisms are there. But IPv6 is of 128bit length, so the present forwarding techniques is not possible to forward IPv6 packet effectively. In this paper we try to explore currently existing different lookup algorithms (Distributed Memory Organizations, Triec, Recursive Balanced Multi-way range trees and Range tree based IPv6 lookup) and analyze the best lookup algorithm for 100+ Gbps IPv6 packet forwarding by performing a comparative survey.

Radio coloring of a graph G with diameter d is an assignment f of positive integers to the vertices of G such that |f(u)-f(v)|≥1+d-d(u,v), where u and v are any two distinct vertices of G and d(u,v) is the distance between u and v. The number max {f(u):u∈V(G)} is called the span of f. The minimum of spans over all radio colorings of G is called radio number of G, denoted by rn(G). An m-distant tree T is a tree in which there is a path P of maximum length such that every vertex in V(T)∖V(P) is at the most distance m from P. This path P is called a central path. For every tree T, there is an integer m such that T is a m-distant tree. In this paper, we determine the radio number of some m-distant trees for any positive integer m≥2, and as a consequence of it, we find the radio number of a class of 1-distant trees (or caterpillars).

In phylogenetics, a common strategy used to construct an evolutionary tree for a set of species $$X$$ is to search in the space of all such trees for one that optimizes some given score function (such as the minimum evolution, parsimony or likelihood score). As this can be computationally intensive, it was recently proposed to restrict such searches to the set of all those trees that are compatible with some circular ordering of the set $$X$$ . To inform the design of efficient algorithms to perform such searches, it is therefore of interest to find bounds for the number of trees compatible with a fixed ordering in the neighborhood of a tree that is determined by certain tree operations commonly used to search for trees: the nearest neighbor interchange (nni), the subtree prune and regraft (spr) and the tree bisection and reconnection (tbr) operations. We show that the size of such a neighborhood of a binary tree associated with the nni operation is independent of the tree’s topology, but that this is not the case for the spr and tbr operations. We also give tight upper and lower bounds for the size of the neighborhood of a binary tree for the spr and tbr operations and characterize those trees for which these bounds are attained.

Let $P$ and $S$ be two disjoint sets of $n$ and $m$ points in the plane, respectively. We consider the problem of computing a Steiner tree whose Steiner vertices belong to $S$, in which each point of $P$ is a leaf, and whose longest edge length is minimum. We present an algorithm that computes such a tree in $O((n+m)\log m)$ time, improving the previously best result by a logarithmic factor. We also prove a matching lower bound in the algebraic computation tree model., Comment: 7 pages

Efficient enumerative coding for tree sources is, in general, surprisingly intricate-a simple uniform encoding of type classes, which is asymptotically optimal in expectation for many classical models, such as FSMs, turns out not to be so in this case. We describe an efficiently computable enumerative code that is universal in the family of tree models in the sense that, for a string emitted by an unknown source whose model is supported on a known tree, the expected normalized code length of the encoding approaches the entropy rate of the source with a convergence rate (K/2)(log n)/n, where K is the number of free parameters of the model family. Based on recent results characterizing type classes of context trees, the code consists of the index of the sequence in the tree type class, and an efficient description of the class itself using a nonuniform encoding of selected string counts. The results are extended to a twice-universal setting, where the tree underlying the source model is unknown.

Since the Hoeffding tree algorithm was proposed in the literature, decision trees became one of the most popular tools for mining data streams. The key point of constructing the decision tree is to determine the best attribute to split the considered node. Several methods to solve this problem were presented so far. However, they are either wrongly mathematically justified (e.g., in the Hoeffding tree algorithm) or time-consuming (e.g., in the McDiarmid tree algorithm). In this paper, we propose a new method which significantly outperforms the McDiarmid tree algorithm and has a solid mathematical basis. Our method ensures, with a high probability set by the user, that the best attribute chosen in the considered node using a finite data sample is the same as it would be in the case of the whole data stream.

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.

Spatial partitioning trees are needed for processing collision detections efficiently. In order to select split planes for spatial partitioning trees, the tree balance and the number of polygons overlapped with the split plane should be considered. In this paper, the heuristic algorithm controlling weight values of tree build criteria is proposed for spatial partitioning trees of 3D games. As the weight values are changed, tree build time, T-junction elimination time which can cause visual artifacts in splitting polygons overlapped with the split plane, rendering speed (frame per second: FPS) according to tree balance are analysed under 3D game simulations.

In the last few decades, several techniques to randomly generate a deterministic finite automaton have been developed. These techniques have implications in the enumeration and random generation of automata of size n. One of the ways to generate a finite automaton is to generate a random tree and to complete it to a deterministic finite automaton, assuming that the tree will be the automaton's breadth-first spanning tree. In this paper we explore further this method, and the string representation of a tree, and use it to counting the number of automata having a tree as a breadth-first spanning subtrees. We introduce the notions of characteristic and difference sequence of a tree, and define the weight of a tree. We also present a recursive formula for this quantity in terms of the "derivative" of a tree. Finally, we analyze the implications of this formula in terms of exploring trees with the largest and smallest number of automata in the span of the tree and present simple applications for finding densities of subsets of DFAs.

We consider the problem of tree template matching, a type of tree pattern matching, where the tree templates have some of their leaves denoted as ''don@?t care'', and propose a solution based on the bottom-up technique. Specifically, we transform the tree pattern matching problem for unranked ordered trees to a string matching problem, by transforming the tree template and the subject tree to strings representing their postfix bar notation, and then propose a table-driven algorithm to solve it. The proposed algorithm is divided into two phases: the preprocessing and the searching phase. The tree template is preprocessed once, and the searching phase can be applied to many subject trees, without the need of preprocessing the tree template again. Although we prove that the space required for preprocessing is exponential in the size of the tree template in the worst case, we show that for a specific class of tree templates, the space required is linear in the size of the tree template. The time for the searching phase is linear in the size of the subject tree in the worst case. Thus, the algorithm is asymptotically optimal when one needs to search for a given tree template, of constant to logarithmic size, in many subject trees.

One of the classic data structures for storing point sets in R^2 is the priority search tree, introduced by McCreight in 1985. We show that this data structure can be made in-place, i.e., it can be stored in an array such that each entry stores only one point of the point set and no entry is stored in more than one location of that array. It combines a binary search tree with a heap. We show that all the standard query operations can be performed within the same time bounds as for the original priority search tree, while using only O(1) extra space. We introduce the min-max priority search tree which is a combination of a binary search tree and a min-max heap. We show that all the standard queries which can be done in two separate versions of a priority search tree can be done with a single min-max priority search tree. As an application, we present an in-place algorithm to enumerate all maximal empty axis-parallel rectangles amongst points in a rectangular region R in R^2 in O(mlogn) time with O(1) extra space, where m is the total number of maximal empty rectangles.

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.

Author(s): Evans, SN; Grubel, R; Wakolbinger, A | Abstract: Remy's algorithm is a Markov chain that iteratively generates a sequence of random trees in such a way that the nth tree is uniformly distributed over the set of rooted, planar, binary trees with 2n + 1 vertices. We obtain a concrete characterization of the Doob-Martin boundary of this transient Markov chain and thereby delineate all the ways in which, loosely speaking, this process can be conditioned to "go to infinity" at large times. A (deterministic) sequence of finite rooted, planar, binary trees converges to a point in the boundary if for each m the random rooted, planar, binary tree spanned by m + 1 leaves chosen uniformly at random from the nth tree in the sequence converges in distribution as n tends to infinity-a notion of convergence that is analogous to one that appears in the recently developed theory of graph limits. We show that a point in the Doob-Martin boundary may be identified with the following ensemble of objects: a complete separable ℝ-tree that is rooted and binary in a suitable sense, a diffuse probability measure on the R-tree that allows us to make sense of sampling points from it, and a kernel on the R-tree that describes the probability that the first of a given pair of points is below and to the left of their most recent common ancestor while the second is below and to the right. Two such ensembles represent the same point in the boundary if for each m the random, rooted, planar, binary trees spanned by m + 1 independent points chosen according to the respective probability measures have the same distribution. Also, the Doob-Martin boundary corresponds bijectively to the set of extreme point of the closed convex set of nonnegative harmonic functions that take the value 1 at the binary tree with 3 vertices; in other words, the minimal and full Doob-Martin boundaries coincide. These results are in the spirit of the identification of graphons as limit objects in the theory of graph limits.

This article presents two new deterministic algorithms for constructing consensus trees. Given an input of $k$ phylogenetic trees with identical leaf label sets and $n$ leaves each, the first algorithm constructs the majority rule (+) consensus tree in $O(k n)$ time, which is optimal since the input size is $\Omega (k n)$ , and the second one constructs the frequency difference consensus tree in $\min \lbrace O(k n^{2}), O(k n (k + \log ^{2}n))\rbrace$ time.

The Binary Identification Problem for weighted trees asks for the minimum cost strategy (decision tree) for identifying a vertex in an edge weighted tree via testing edges. Each edge has assigned a different cost, to be paid for testing it. Testing an edge e reveals in which component of T−e lies the vertex to be identified. We give a complete characterization of the computational complexity of this problem with respect to both tree diameter and degree. In particular, we show that it is strongly NP-hard to compute a minimum cost decision tree for weighted trees of diameter at least 6, and for trees having degree three or more. For trees of diameter five or less, we give a polynomial time algorithm. Moreover, for the degree 2 case, we significantly improve the straightforward O(n3) dynamic programming approach, and provide an O(n2) time algorithm. Finally, this work contains the first approximate decision tree construction algorithm that breaks the barrier of factor logn.

Let T be a (not necessarily positive) weighted tree with n leaves numbered by the set { 1 , … , n } . For any i 1 , … , i k ∈ { 1 , … , n } , define D i 1 , … , i k ( T ) to be the sum of the lengths of the edges of the minimal subtree joining i 1 , … , i k . We will call such numbers “ k -weights” of the tree and we call the k -weights for any k ≥ 2 “multi-weights” of the tree. In this paper, we give a characterization of the families of real numbers that are the families of the multi-weights of a tree.

We present new results on Cartesian trees with applications in range minimum queries and bottleneck edge queries. We introduce a cache-oblivious Cartesian tree for solving the range minimum query problem, a Cartesian tree for the bottleneck edge query problem on trees and undirected graphs, and a proof that no Cartesian tree exists for the two-dimensional version of the range minimum query problem.

tree traversal refers to the process of visiting each node in a specified order. Given the inorder traversal of a binary tree, along with one of its preorder or postorder traversals, the original binary tree can be uniquely identified. Many recursive and non recursive method of construction of the tree from inorder and any of the postorder or preorder traversal have been proposed. In this paper one of the proposed algorithms has been examined. This algorithm computes the wrong tree for some input sequences. We show a particular situation in which the algorithm fails and a solution for this situation is proposed. The proposed a modified non-recursive algorithm for reconstructing a binary tree which generates the correct tree otherwise an error has been reported.

Let R and B be sets of red and blue points in the plane in general position. We study the problem of computing a k-level binary space partition (BSP) tree to classify/separate R and B, such that the tree defines a linear decision at each internal node and each leaf of the tree corresponds to a (convex) cell of the partition that contains only red or only blue points. Specifically, we show that a 2-level tree can be computed, if one exists, in time O(n2). We show that a minimum-level (3 ≤ k ≤ log n) tree can be computed in time nO( log n). In the special case of axis-parallel partitions, we show that 2-level and 3-level trees can be computed in time O(n), while a minimum-level tree can be computed in time O(n5).

Trees are one of the fundamental data structures used in Computer Science. We present a new kind of acyclic pushdown automata, the tree pattern pushdown automaton and the nonlinear tree pattern pushdown automaton, constructed for an ordered tree. These automata accept all tree patterns and nonlinear tree patterns, respectively, which match the tree and represent a full index of the tree for such patterns. Given a tree with n nodes, the numbers of these distinct tree patterns and nonlinear tree patterns can be at most 2n?1 +n and at most (2+v)n?1+2, respectively, where v is the maximal number of nonlinear variables allowed in nonlinear tree patterns. The total sizes of nondeterministic versions of the two pushdown automata are O(n) and O(n2), respectively. We discuss the time complexities and show timings of our implementations using the bit-parallelism technique. The timings show that for a given tree the running time is linear to the size of the input pattern.

The path spectrum of a graph is the set of lengths of all maximal paths in the graph. A set S of positive lengths is tree spectral if it is the path spectrum of a tree. We show that for each even integer s ⩾ 2 at least 34.57% of all subsets of the set { 2 , 3 , … , s } are tree spectral, and for each odd integer s ⩾ 2 at least 27.44% of all subsets of the set { 2 , 3 , … , s } are tree spectral.

In data integration applications, a join matches elements that are common to two data sources. Since elements are represented slightly different in each source, an approximate join must be used to do the matching. For XML data, most existing approximate join strategies are based on some ordered tree matching technique, such as the tree edit distance. In data-centric XML, however, the sibling order is irrelevant, and two elements should match even if their subelement order varies. Thus, approximate joins for data-centric XML must leverage unordered tree matching techniques. This is computationally hard since the algorithms cannot rely on a predefined sibling order. In this paper, we give a solution for approximate joins based on unordered tree matching. The core of our solution are windowed pq-grams which are small subtrees of a specific shape. We develop an efficient technique to generate windowed pq-grams in a three-step process: sort the tree, extend the sorted tree with dummy nodes, and decompose the extended tree into windowed pq-grams. The windowed pq-grams distance between two trees is the number of pq-grams that are in one tree decomposition only. We show that our distance is a pseudo-metric and empirically demonstrate that it effectively approximates the unordered tree edit distance. The approximate join using windowed pq-grams can be efficiently implemented as an equality join on strings, which avoids the costly computation of the distance between every pair of input trees. Experiments with synthetic and real world data confirm the analytic results and show the effectiveness and efficiency of our technique.

We give a (ln n+1)-approximation for the decision tree (DT) problem. An instance of DT is a set of m binary tests T=(T 1,…,T m ) and a set of n items X=(X 1,…,X n ). The goal is to output a binary tree where each internal node is a test, each leaf is an item and the total external path length of the tree is minimized. Total external path length is the sum of the depths of all the leaves in the tree. DT has a long history in computer science with applications ranging from medical diagnosis to experiment design. It also generalizes the problem of finding optimal average-case search strategies in partially ordered sets which includes several alphabetic tree problems. Our work decreases the previous best upper bound on the approximation ratio by a constant factor. We provide a new analysis of the greedy algorithm that uses a simple accounting scheme to spread the cost of a tree among pairs of items split at a particular node. We conclude by showing that our upper bound also holds for the DT problem with weighted tests.

Given dissimilarity data on pairs of objects in a set, we study the problem of fitting a tree metric to this data so as to minimize additive error (i.e. some measure of the difference between the tree metric and the given data). This problem arises in constructing an M-level hierarchical clustering of objects (or an ultrametric on objects) so as to match the given dissimilarity data - a basic problem in statistics. Viewed in this way, the problem is a generalization of the correlation clustering problem (which corresponds to M = 1). We give a very simple randomized combinatorial algorithm for the M-level hierarchical clustering problem that achieves an approximation ratio of M+2. This is a generalization of a previous factor 3 algorithm for correlation clustering on complete graphs. The problem of fitting tree metrics also arises in phylogeny where the objective is to learn the evolution tree by fitting a tree to dissimilarity data on taxa. The quality of the fit is measured by taking the l/sub p/ norm of the difference between the tree metric constructed and the given data. Previous results obtained a factor 3 approximation for finding the closest tree tree metric under the l/spl infin/ norm. No nontrivial approximation for general l/sub p/ norms was known before. We present a novel LP formulation for this problem and obtain an O((log n log log n)/sup 1/p/) approximation using this. Enroute, we obtain an O((log n log log n)/sup 1/p/) approximation for the closest ultrametric under the l/sub p/ norm. Our techniques are based on representing and viewing an ultrametric as a hierarchy of clusterings, and may be useful in other contexts.

Links between the Calkin–Wilf tree and the Stern–Brocot tree are discussed answering the questions: What is the jth vertex in the nth level of the Calkin–Wilf tree? and Where is the vertex rs located in the Calkin–Wilf tree? A simple mechanism is described for converting the jth vertex in the nth level of the Calkin–Wilf tree into the jth entry in the nth level of the Stern–Brocot tree. We also provide a simple method for evaluating terms in the Hyperbinary sequence thus answering a challenge raised in Quantum in September 1997. We also examine successors and predecessors in both trees.

We study two enumeration problems for up–down alternating trees, i.e., rooted labelled trees T, where the labels v1,v2,v3,… on every path starting at the root of T satisfy v1v3⋯. First we consider various tree families of interest in combinatorics (such as unordered, ordered, d-ary and Motzkin trees) and study the number Tn of different up–down alternating labelled trees of size n. We obtain for all tree families considered an implicit characterization of the exponential generating function T(z) leading to asymptotic results of the coefficients Tn for various tree families. Second we consider the particular family of up–down alternating labelled ordered trees and study the influence of such an alternating labelling to the average shape of the trees by analyzing the parameters label of the root node, degree of the root node and depth of a random node in a random tree of size n. This leads to exact enumeration results and limiting distribution results.

A dynamic multiway segment tree (DMST) is proposed for IP lookups in this paper. DMST is designed for dynamic routing tables that can dynamically insert and delete prefixes. DMST is implemented as a B-tree that has all distinct end points of ranges as its keys. The complexities of search, insertion, deletion, and memory requirement are the same as the existing multiway range tree (MRT) and prefix in B-tree (PIBT) for prefixes. In addition, a pipelined DMST search engine is proposed to further speed up the search operations. The proposed pipelined DMST search engine uses off-chip SRAMs instead of on-chip SRAMs because the capacity of the latter is too small to hold large routing tables and the cost of the latter is too expensive. By utilizing current FPGA and off-chip SRAM technologies, our proposed five-stage pipelined search engine can achieve the worst case throughputs of 33.3 and 41.7 million packets per second (Mpps) with 144-bit and 288-bit wide SRAM blocks, respectively. Furthermore, a straightforward extension of the pipelined search engine with multiple independent off-chip SRAMs can achieve the throughput of 200 Mpps which is equivalent to 102 Gbps for minimal Ethernet packets of size 64 bytes.

Given a set S of n red and blue points in the plane, a planar bichromatic minimum spanning tree is the shortest possible spanning tree of S, such that every edge connects a red and a blue point, and no two edges intersect. We show that computing this tree is NP-hard in general. For points in convex position, a cubic-time algorithm can be easily designed using dynamic programming. We adapt such an algorithm for the special case where the number of red points (m) is much smaller than the number of blue points (n), resulting in an O ( n m 2 ) time algorithm. For the general case, we present a factor O ( n ) approximation algorithm that runs in O ( n log n log log n ) time. Finally, we show that if the number of points in one color is bounded by a constant, the optimal tree can be computed in polynomial time.

Recently, Gu et al. [N.S.S. Gu, N.Y. Li, T. Mansour, 2-Binary trees: Bijections and related issues, Discrete Math. 308 (2008) 1209–1221] introduced 2-binary trees and 2-plane trees which are closely related to ternary trees. In this note, we study the 2-noncrossing tree, a noncrossing tree in which each vertex is colored black or white and there is no ascent (u,v) such that both the vertices u and v are colored black. By using the representation of Panholzer and Prodinger for noncrossing trees, we find a correspondence between the set of 2-noncrossing trees of n edges with a black root and the set of 5-ary trees with n internal vertices.