Arborescence

Résumé

thumb|Exemple de représentation arborescente En mathématiques, plus précisément dans la théorie des graphes : une arborescence est un arbre comportant un sommet particulier r, nommé racine de l'arborescence, à partir duquel il existe un chemin unique vers tous les autres sommets. En informatique, cette notion désigne souvent celle d'arbre de la théorie des graphes. Une arborescence désigne alors généralement une organisation des données en mémoire, de manière logique et hiérarchisée, utilisant une structure algorithmique d'arbre. Cette organisation rend plus efficace la consultation et la manipulation des données stockées. Les usages les plus courants en sont :

l'arborescence de fichiers, qui est l'organisation hiérarchique des fichiers sur une partition, et dans certains cas de partitions entre elles – par exemple : partitions virtuelles (« lecteurs logiques ») dans des partitions réelles ;
le tri arborescent en mémoire ;
les fichiers en mode sé

Source officielle

https://fr.wikipedia.org/wiki/Arborescence

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (32)

Publications associées

Chargement

Personnes associées (5)

Personnes associées

Chargement

Unités associées (4)

Unités associées

Chargement

Concepts associés (8)

Concepts associés

Chargement

Cours associés (6)

Cours associés

Chargement

Séances de cours associées (11)

Séances de cours associées

Chargement

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

Chargement

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

Chargement

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

Chargement

EPFL2011