Tree structure

Summary

A tree structure, tree diagram, or tree model is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, although the chart is generally upside down compared to a biological tree, with the "stem" at the top and the "leaves" at the bottom. A tree structure is conceptual, and appears in several forms. For a discussion of tree structures in specific fields, see Tree (data structure) for computer science; insofar as it relates to graph theory, see tree (graph theory) or tree (set theory). Other related articles are listed below. Terminology and properties The tree elements are called "nodes". The lines connecting elements are called "branches". Nodes without children are called leaf nodes, "end-nodes", or "leaves". Every finite tree structure has a member that has no superior. This member is called the "root" or root node. The root is the starting node. But the conv

Official source

https://en.wikipedia.org/wiki/Tree_structure

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (32)

Related publications

Related people (5)

Related people

Related units (4)

Related units

Related concepts (8)

Related concepts

Related courses (6)

Related courses

Related lectures (11)

Related lectures

Related publications (32)

Scaling Similarity Joins over Tree-Structured Data

Yu Tang

Given a large collection of tree-structured objects (e.g., XML documents), the similarity join finds the pairs of objects that are similar to each other, based on a similarity threshold and a tree edit distance measure. The state-of-the-art similarity join methods compare simpler approximations of the objects (e.g., strings), in order to prune pairs that cannot be part of the similarity join result based on distance bounds derived by the approximations. In this paper, we propose a novel similarity join approach, which is based on the dynamic decomposition of the tree objects into subgraphs, according to the similarity threshold. Our technique avoids computing the exact distance between two tree objects, if the objects do not share at least one common subgraph. In order to scale up the join, the computed subgraphs are managed in a two-layer index. Our experimental results on real and synthetic data collections show that our approach outperforms the state-of-the-art methods by up to an order of magnitude.

Assoc Computing Machinery2015

Grammar-Based Tree Compression

Grammar-based compression means to find a small grammar that generates a given object. Such a grammar reveals the structure of the object (according to the grammar formalism used); the main advantage of this compression method is that the resulting grammar can often be used in further computations without prior decompression. A linear time bottom-up algorithm is presented which transforms a tree into a particular context-free tree grammar. For common XML documents the algorithm performs well, compressing the tree structure to about 5 per cent of the original size. The validation of an XML document against an XML type can be done without decompression, in linear time w.r.t. the size of the grammar (for a fixed type). While the involved grammars can be double exponentially smaller than the represented trees, testing them for equivalence can be done in polynomial space w.r.t. the sum of their sizes.

2004

Despite more than a century of research, we still lack a concise description of the different types of neurons in the brain. This is a result of their large variance in morphology and the time consuming reconstruction process. In this thesis we design novel fully automated algorithms to release neuroscientists from such burdern. To that end, we first propose a filtering method that enhances neurite structures while rejecting structured noise. Prior work rely on filters optimized for signals of a particular shape, such as an ideal edge or ridge. While these approaches are optimal when the image conforms to these ideal shapes, their performance quickly degrades on many types of real data where the image deviates from such ideal model. We show that by learning rotational features, we can outperform state-of-the-art filament detection techniques on many different kinds of imagery. More specifically, we demonstrate superior performance for the detection of blood vessel in retinal scans, neurons in brightfield microscopy imagery, and streets in satellite imagery. Afterwards we propose algorithms that extract automatically the tree structures present on the images by maximizing a global likelihood under a generative model in noisy 2D images and 3D image stacks. Unlike earlier methods that rely mostly on local evidence, our method builds a set of candidate trees over many different subsets of points likely to belong to the final one and then chooses the best one according to a global objective function. Since we are not systematically trying to span all nodes, our algorithm is able to eliminate noise while retaining the right tree structure. We performed extended evaluation of the proposed algorithms and participated on a prestigious neuron reconstruction challenge. We obtained an award "for our deeper potential, more original approach, and ultimate scalability of our proposed solution". Finally, we propose system that tracks, segments and traces neurons in time-lapse microscopy and is suitable for high throughput image analysis. We examined neuronal differentiation datasets where gene expressions were inhibited using RNA interference. We were able to corroborate previously known behaviours and to derive new ones.

EPFL2011