Dissertations / Theses on the topic 'Hierarchical graphs'
To see the other types of publications on this topic, follow the link: Hierarchical graphs.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Hierarchical graphs.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Busatto, Giorgio. "An abstract model of hierarchical graphs and hierarchical graph transformation." Oldenburg : Univ., Fachbereich Informatik, 2002. http://deposit.ddb.de/cgi-bin/dokserv?idn=967851955.
Full text
2
Busatto, Giorgio [Verfasser]. "An abstract model of hierarchical graphs and hierarchical graph transformation / von Giorgio Busatto." Oldenburg : Univ., Fachbereich Informatik, 2002. http://d-nb.info/967851955/34.
Full text
3
Dorrian, Henry Joseph. "Hierarchical graphs and oscillator dynamics." Thesis, Manchester Metropolitan University, 2015. http://e-space.mmu.ac.uk/580120/.
Full textAbstract:
In many types of network, the relationship between structure and function is of great significance. This work is particularly concerned with community structures, which arise in a wide variety of domains. A simple oscillator model is applied to networks with community structures and shows that waves of regular oscillation are caused by synchronised clusters of nodes. Moreover, we demonstrate that such global oscillations may arise as a direct result of network topology. We also observe that additional modes of oscillation (as detected through frequency analysis) occur in networks with additional levels of hierarchy and that such modes may be directly related to network structure. This method is applied in two specific domains (metabolic networks and metropolitan transport), demonstrating the robustness of the results when applied to real world systems. A topological analysis is also applied to the real world networks of metabolism and metropolitan transport using standard graphical measures. This yields a new artificial network growth model, which agrees closely with the graphical measures taken on metabolic pathway networks. This new model demonstrates a simple mechanism to produce the particular features found in these networks. We conclude that (where the distribution of oscillator frequencies and the interactions between them are known to be unimodal) the observations may be applicable to the detection of underlying community structure in networks, shedding further light on the general relationship between structure and function in complex systems.
4
Slade, Michael L. "A layout algorithm for hierarchical graphs with constraints /." Online version of thesis, 1994. http://hdl.handle.net/1850/11724.
Full text
5
Puch-Solis, Roberto O. "Hierarchical junction trees." Thesis, University of Warwick, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.365243.
Full text
6
Reynolds, Jason. "A hierarchical layout algorithm for drawing directed graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp04/mq20694.pdf.
Full text
7
Wallgrün, Jan Oliver. "Hierarchical Voronoi graphs spatial representation and reasoning for mobile robots." Berlin Heidelberg Springer, 2008. http://d-nb.info/99728210X/04.
Full text
8
Spisla, Christiane [Verfasser]. "Compaction of Orthogonal and Hierarchical Graph Drawings Using Constraint Graphs and Minimum Cost Flows / Christiane Spisla." München : Verlag Dr. Hut, 2019. http://d-nb.info/119641467X/34.
Full text
9
Santana, Maia Deise. "A study of hierarchical watersheds on graphs with applications to image segmentation." Thesis, Paris Est, 2019. http://www.theses.fr/2019PESC2069.
Full textAbstract:
La littérature abondante sur la théorie des graphes invite de nombreux problèmes à être modélisés dans ce cadre. En particulier, les algorithmes de regroupement et de segmentation conçus dans ce cadre peuvent être utilisés pour résoudre des problèmes dans de nombreux domaines tels que l'analyse d'image qui est le principal domaine d'application de cette thèse. Dans ce travail, nous nous concentrons sur un outil de segmentation semi-supervisé largement étudié dans la morphologie mathématique et appliqué à l'analyse d'image, notamment les Ligne de Partage des Eaux (LPE). Nous étudions la notion de hiérarchie de LPE, qui est une extension multi-échelle de la notion de LPE permettant de décrire une image ou, plus généralement, un ensemble de donnés par des partitions à plusieurs niveaux de détail. Les contributions principales de cette étude sont les suivantes : - Reconnaissance de hiérarchies de LPE : nous proposons une caractérisation des hiérarchies de LPE qui mène à un algorithme efficace pour déterminer si une hiérarchie est une hiérarchie de LPE d'un graphe donné. - Opérateur watersheding : nous présentons l'opérateur watersheding, qui, étant donné un graphe pondéré, associe n'importe quelle hiérarchie à une hiérarchie de LPE de ce graphe. Nous montrons que cet opérateur est idempotent et que ses points fixes sont les hiérarchies de LPE. Nous proposons également un algorithme efficace pour calculer le résultat de cet opérateur. - Probabilité de hiérarchies de LPE : nous proposons et étudions une notion de probabilité d'une hiérarchie de LPE, et nous concevons un algorithme pour calculer la probabilité d'une hiérarchie de LPE. De plus, nous présentons des algorithmes pour calculer des hiérarchies de LPE de probabilité minimale et maximale pour un graphe pondéré donné. - Combinaison de hiérarchies : nous étudions une famille d'opérateurs pour combiner des hiérarchies de partitions et nous étudions les propriétés de ces opérateurs lorsqu'ils sont appliqués à des hiérarchies de LPE. En particulier, nous prouvons que, dans certaines conditions, la famille des hiérarchies de LPE est fermée pour l'opérateur de combinaison. - Évaluation de hiérarchies : nous proposons un cadre d'évaluation de hiérarchies, qui est également utilisé pour évaluer les hiérarchies de LPE et les combinaisons des hiérarchies. En conclusion, cette thèse révise des propriétés existantes et des nouvelles propriétés liées aux hiérarchies de LPE, montrant la richesse théorique de ce cadre et fournissant une vue d'ensemble des ses applications dans l'analyse d'image et dans la vision par ordinateur et, plus généralement, dans le traitement de donnés et dans l'apprentissage automatiqueThe wide literature on graph theory invites numerous problems to be modeled in the framework of graphs. In particular, clustering and segmentation algorithms designed this framework can be applied to solve problems in various domains, including image processing, which is the main field of application investigated in this thesis. In this work, we focus on a semi-supervised segmentation tool widely studied in mathematical morphology and used in image analysis applications, namely the watershed transform. We explore the notion of a hierarchical watershed, which is a multiscale extension of the notion of watershed allowing to describe an image or, more generally, a dataset with partitions at several detail levels. The main contributions of this study are the following : - Recognition of hierarchical watersheds : we propose a characterization of hierarchical watersheds which leads to an efficient algorithm to determine if a hierarchy is a hierarchical watershed of a given edge-weighted graph. - Watersheding operator : we introduce the watersheding operator, which, given an edge-weighted graph, maps any hierarchy of partitions into a hierarchical watershed of this edge-weighted graph. We show that this operator is idempotent and its fixed points are the hierarchical watersheds. We also propose an efficient algorithm to compute the result of this operator. - Probability of hierarchical watersheds : we propose and study a notion of probability of hierarchical watersheds, and we design an algorithm to compute the probability of a hierarchical watershed. Furthermore, we present algorithms to compute the hierarchical watersheds of maximal and minimal probabilities of a given weighted graph. - Combination of hierarchies : we investigate a family of operators to combine hierarchies of partitions and study the properties of these operators when applied to hierarchical watersheds. In particular, we prove that, under certain conditions, the family of hierarchical watersheds is closed for the combination operator. - Evaluation of hierarchies : we propose an evaluation framework of hierarchies, which is further used to assess hierarchical watersheds and combinations of hierarchies. In conclusion, this thesis reviews existing and introduces new properties and algorithms related to hierarchical watersheds, showing the theoretical richness of this framework and providing insightful view for its applications in image analysis and computer vision and, more generally, for data processing and machine learning
10
Charpentier, Bertrand. "Multi-scale clustering in graphs using modularity." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-244847.
Full textAbstract:
This thesis provides a new hierarchical clustering algorithm for graphs, named Paris, which can be interpreted through the modularity score and its resolution parameter. The algorithm is agglomerative and based on a simple distance between clusters induced by the probability of sampling node pairs. It tries to approximate the optimal partitions with respect to the modularity score at any resolution in one run. In addition to the Paris hierarchical algorithm, this thesis proposes four algorithms that compute rankings of the sharpest clusters, clusterings and resolutions by processing the hierarchy output by Paris. These algorithms are based on a new measure of stability for clusterings, named sharp-score. Key outcomes of these four algorithms are the possibility to rank clusters, detect sharpest clusterings scale, go beyond the resolution limit and detect relevant resolutions. All these algorithms have been tested on both synthetic and real datasets to illustrate the efficiency of their approaches.Denna avhandling ger en ny hierarkisk klusteralgoritm för grafer, som heter Paris, vilket kan tolkas av modularitetsresultatet och dess upplösningsparameter. Algoritmen är agglomerativ och är baserad på ett enda avstånd mellan kluster som induceras av sannolikheten för sampling av nodpar. Det försöker att approximera de optimala partitionerna vid vilken upplösning som helst i en körning. Förutom en hierarkisk algoritm föreslår denna avhandling fyra algoritmer som beräknar rankningar av de bästa grupperna, kluster och resolutioner genom att bearbeta hierarkiproduktionen i Paris. Dessa algoritmer bygger på ett nytt koncept av klusterstabilitet, kallad sharpscore. Viktiga resultat av dessa fyra algoritmer är förmågan att rangordna kluster, upptäcka bästa klusterskala, gå utöver upplösningsgränsen och upptäcka de mest relevanta resolutionerna. Alla dessa algoritmer har testats på både syntetiska och verkliga datamängder för att illustrera effektiviteten i deras metoder.
11
Stoffel, Edgar-Philipp. "Hierarchical graphs as organisational principle and spatial model applied to pedestrian indoor navigation." Diss., kostenfrei, 2009. http://edoc.ub.uni-muenchen.de/10620/.
Full text
12
Olifer, Maksim. "Architectural model synthesis from source code using Simulink and Hierarchical Function Call-Graphs." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-296883.
Full textAbstract:
Modern software systems developed in the automotive industry are very complex. In order to analyze, understand, and document these software systems, architectural models of the systems at different abstraction levels are used. However, these models are typically ambiguous and inconsistent with the implementation. This thesis presents an approach to construct an unambiguous model of C code in an automatic manner, with a focus on architecture consistency by employing the Simulink environment extended by an external custom GUI. Such approach also facilitates compliance with the functional safety standard ISO 26262 that requires models of software systems (including legacy code), where the models capture both its behavior and structure. More specifically, we develop a method for hierarchical modelling in Simulink and describe mapping to the actual C code architecture expressed by distinct abstraction levels (e.g. layers, modules, functions). Although Simulink is capable of handling modular structures, there is a lack of proper visual representation support, which at the moment can reflect only inter-functional dependencies in terms of caller-to-callee relations, omitting any hierarchical view of abstraction layers. An attempt to extend graphical features of Simulink had several drawbacks and performance issues. As an enhanced solution, external GUI was developed for enabling a "complete" representation of the code architecture. For that purpose, reverse engineering approaches were employed with a help of LLVM compiler infrastructure and poolalloc project. A further analysis of LLVM IR allowed extracting a function call graph, including indirect function calls with a satisfactory precision (which can be possibly improved). For a better performance, the resulting graph was placed in a database, which allowed to dynamically select particular parts and relations of the graph. The developed tool-chain was evaluated on a two production software system called COO7 and GMS. This thesis was done at Scania CV AB in Södertälje, Sweden.
13
Decelle, Aurélien. "Statistical physics of disordered networks - Spin Glasses on hierarchical lattices and community inference on random graphs." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00653375.
Full textAbstract:
Cette thèse aborde des aspects fondamentales et appliquées de la théorie des verres de spin etplus généralement des systèmes complexes. Les premiers modèles théoriques décrivant la transitionvitreuse sont apparues dans les années 1970. Ceux-ci décrivaient les verres à l'aide d'interactionsaléatoires. Il a fallu alors plusieurs années avant qu'une théorie de champs moyen pour ces systèmessoient comprises. De nos jours il existe un grand nombre de modèles tombant dans la classe de" champs moyen " et qui sont bien compris à la fois analytiquement, mais également numériquementgrâce à des outils tels que le monte-carlo ou la méthode de la cavité. Par ailleurs il est bien connu quele groupe de renormalisation a échoué jusque ici à pouvoir prédire le comportement des observablescritiques dans les verres hors champs moyen. Nous avons donc choisi d'étudier des systèmes eninteraction à longue portée dont on ignore encore si la physique est identique à celle du champmoyen. Nous avons montré dans une première partie, la facilité avec laquelle on peut décrire unetransformation du groupe de renormalisation dans les systèmes ferromagnétiques en interaction àlongue portée dé finies sur le réseau hiérarchique de Dyson. Dans un second temps, nous avons portéenotre attention sur des modèles de verre de spin sur ce même réseau. Un début d'analyse sur cestransformations dans l'espace réel est présenté ainsi qu'une comparaison de la mesure de l'exposantcritique nu par différentes méthodes. Si la transformation décrite semble prometteuse il faut cependantnoter que celle-ci doit encore être améliorée afin d'être considérée comme une méthode valide pournotre système. Nous avons continué dans cette même direction en analysant un modèle d'énergiesaléatoires toujours en utilisant la topologie du réseau hiérarchique. Nous avons étudié numériquementce système dans lequel nous avons pu observer l'existence d'une transition de phase de type " criseentropique " tout à fait similaire à celle du REM de Derrida. Toutefois, notre modèle présente desdifférences importantes avec ce dernier telles que le comportement non-analytique de l'entropie à latransition, ainsi que l'émergence de " criticalité " dont la présence serait à confirmer par d'autres études.Nous montrons également à l'aide de notre méthode numérique comment la température critique dece système peut-être estimée de trois façon différentes.Dans une dernière partie nous avons abordé des problèmes liés aux systèmes complexes. Il aété remarqué récemment que les modèles étudiés dans divers domaines, par exemple la physique, labiologie ou l'informatique, étaient très proches les uns des autres. Ceci est particulièrement vrai dansl'optimisation combinatoire qui a en partie été étudiée par des méthodes de physique statistique. Cesméthodes issues de la théories des verres de spin et des verres structuraux ont été très utilisées pourétudier les transitions de phase qui ont lieux dans ces systèmes ainsi que pour inventer de nouveauxalgorithmes pour ces modèles. Nous avons étudié le problème de l'inférence de modules dans lesréseaux à l'aide de ces même méthodes. Nous présentons une analyse sur la détection des modules topologiques dans des réseaux aléatoires et démontrons la présence d'une transition de phase entre une région où ces modules sont indétectables et une région où ils sont détectables. Par ailleurs, nous avons implémenté pour ces problèmes un algorithme utilisant Belief Propagation afin d'inférer les modules ainsi que d'apprendre leurs propriétés en ayant pour unique information la structure du réseau. Finalementnous avons appliqué cet algorithme sur des réseaux construits à partir de données réelles et discutonsles développements à apporter à notre méthode.
14
Cuenca, Pauta Erick. "Visualisation de données dynamiques et complexes : des séries temporelles hiérarchiques aux graphes multicouches." Thesis, Montpellier, 2018. http://www.theses.fr/2018MONTS054/document.
Full textAbstract:
L'analyse de données de plus en plus complexes, volumineuses et issues de différentes sources (e.g. internet, médias sociaux, etc.) est une tâche difficile. Elle reste cependant cruciale dans de très nombreux domaines d'application. Elle implique, pour pouvoir en extraire des connaissances, de mieux comprendre la nature des données, leur évolution ou les nombreuses relations complexes qu'elles peuvent contenir. La visualisation d'informations s'intéresse aux méthodes de représentations visuelles et interactives permettant d'aider un utilisateur à extraire des connaissances. C'est dans ce contexte que se situe le travail présenté dans ce mémoire. Dans un premier temps, nous nous intéressons à la visualisation de longues séries temporelles hiérarchiques. Après avoir analysé les différentes approches existantes, nous présentons le système MultiStream permettant de visualiser, explorer et comparer l'évolution de séries organisées dans une structure hiérarchique. Nous illustrons son utilisation par deux exemples d'utilisation : émotions exprimées dans des médias sociaux et évolution des genres musicaux. Dans un second temps nous abordons la problématique de données complexes modélisées sous la forme de graphes multicouches (différentes types d'arêtes peuvent relier les n÷uds). Plus particulièrement nous nous intéressons au requêtage visuel de graphes volumineux en présentant VERTIGo un système qui permet de construire des requêtes, d'interroger un moteur spécifique, de visualiser/explorer les résultats à différentes niveaux de détail et de suggérer de nouvelles extensions de requêtes. Nous illustrons son utilisation à l'aide d'un graphe d'auteurs provenant de différentes communautésThe analysis of data that is increasingly complex, large and from different sources (e.g. internet, social medias, etc.) is a dificult task. However, it remains crucial for many fields of application. It implies, in order to extract knowledge, to better understand the nature of the data, its evolution or the many complex relationships it may contain. Information visualization is about visual and interactive representation methods to help a user to extract knowledge. The work presented in this document takes place in this context. At first, we are interested in the visualization of large hierarchical time series. After analyzing the different existing approaches, we present the MultiStream system for visualizing, exploring and comparing the evolution of the series organized into a hierarchical structure. We illustrate its use by two examples: emotions expressed in social media and the evolution of musical genres. In a second time, we tackle the problem of complex data modeled in the form of multilayer graphs (different types of edges can connect the nodes). More specifically, we are interested in the visual querying of large graphs and we present VERTIGo, a system which makes it possible to build queries, to launch them on a specific engine, to visualize/explore the results at different levels of details and to suggest new query extensions. We illustrate its use with a graph of co-authors from different communities
15
Reda, Fatima Al. "Modélisation de mouvement de foules avec contraintes variées." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS235/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à la modélisation de mouvements de foules. Nous proposons un modèle microscopique basé sur la théorie des jeux. Chaque individu a une certaine vitesse souhaitée, celle qu'il adopterait en l'absence des autres. Une personne est influencée par certains de ses voisins, pratiquement ceux qu'elle voit devant elle. Une vitesse réelle est considérée comme possible si elle réalise un équilibre de Nash instantané: chaque individu fait son mieux par rapport à un objectif personnel (vitesse souhaitée), en tenant compte du comportement des voisins qui l'influencent. Nous abordons des questions relatives à la modélisation ainsi que les aspects théoriques du problème dans diverses situations, en particulier dans le cas où chaque individu est influencé par tous les autres, et le cas où les relations d'influence entre les individus présentent une structure hiérarchique. Un schéma numérique est développé pour résoudre le problème dans le second cas (modèle hiérarchique) et des simulations numériques sont proposées pour illustrer le comportement du modèle. Les résultats numériques sont confrontés avec des expériences réelles de mouvements de foules pour montrer la capacité du modèle à reproduire certains effets.Nous proposons une version macroscopique du modèle hiérarchique en utilisant les mêmes principes de modélisation au niveau macroscopique, et nous présentons une étude préliminaire des difficultés posées par cette approche.La dernière problématique qu'on aborde dans cette thèse est liée aux cadres flot gradient dans les espaces de Wasserstein aux niveaux continu et discret. Il est connu que l'équation de Fokker-Planck peut s'interpréter comme un flot gradient pour la distance de Wasserstein continue. Nous établissons un lien entre une discrétisation spatiale du type Volume Finis pour l'équation de Fokker-Planck sur une tesselation de Voronoï et les flots gradient sur le réseau sous-jacent, pour une distance de type Wasserstein récemment introduite sur l'espace de mesures portées par les sommets d'un réseauxWe are interested in the modeling of crowd motion. We propose a microscopic model based on game theoretic principles. Each individual is supposed to have a desired velocity, it is the one he would like to have in the absence of others. We consider that each individual is influenced by some of his neighbors, practically the ones that he sees. A possible actual velocity is an instantaneous Nash equilibrium: each individual does its best with respect to a personal objective (desired velocity), considering the behavior of the neighbors that influence him. We address theoretical and modeling issues in various situations, in particular when each individual is influenced by all the others, and in the case where the influence relations between individuals are hierarchical. We develop a numerical strategy to solve the problem in the second case (hierarchical model) and propose numerical simulations to illustrate the behavior of the model. We confront our numerical results with real experiments and prove the ability of the hierarchical model to reproduce some phenomena.We also propose to write a macroscopic counterpart of the hierarchical model by translating the same modeling principles to the macroscopic level and make the first steps towards writing such model.The last problem tackled in this thesis is related to gradient flow frameworks in the continuous and discrete Wasserstein spaces. It is known that the Fokker-Planck equation can be interpreted as a gradient flow for the continuous Wasserstein distance. We establish a link between some space discretization strategies of the Finite Volume type for the Fokker- Planck equation in general meshes (Voronoï tesselations) and gradient flows on the underlying networks of cells, in the framework of discrete Wasserstein-like distance on graphs recently introduced
16
Sansen, Joris. "La visualisation d’information pour les données massives : une approche par l’abstraction de données." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0636/document.
Full textAbstract:
L’évolution et la démocratisation des technologies ont engendré une véritable explosion de l’information et notre capacité à générer des données et le besoin de les analyser n’a jamais été aussi important. Pourtant, les problématiques soulevées par l’accumulation de données (stockage, temps de traitement, hétérogénéité, vitesse de captation/génération, etc. ) sont d’autant plus fortes que les données sont massives, complexes et variées. La représentation de l’information, de part sa capacité à synthétiser et à condenser des données, se constitue naturellement comme une approche pour les analyser mais ne résout pas pour autant ces problèmes. En effet, les techniques classiques de visualisation sont rarement adaptées pour gérer et traiter cette masse d’informations. De plus,les problèmes que soulèvent le stockage et le temps de traitement se répercutent sur le système d’analyse avec par exemple, la distanciation de plus en plus forte entre la donnée et l’utilisateur : le lieu où elle sera stockée et traitée et l’interface utilisateur servant à l’analyse. Dans cette thèse nous nous intéressons à ces problématiques et plus particulièrement à l’adaptation des techniques de visualisation d’informations pour les données massives. Pour cela, nous nous intéressons tout d’abord à l’information de relation entre éléments, comment est-elle véhiculée et comment améliorer cette transmission dans le contexte de données hiérarchisées. Ensuite, nous nous intéressons à des données multivariées,dont la complexité à un impact sur les calculs possibles. Enfin, nous présentons les approches mises en oeuvre pour rendre nos méthodes compatibles avec les données massivesThe evolution and spread of technologies have led to a real explosion of information and our capacity to generate data and our need to analyze them have never been this strong. Still, the problems raised by such accumulation (storage, computation delays, diversity, speed of gathering/generation, etc. ) is as strong as the data are big, complex and varied. Information visualization,by its ability to summarize and abridge data was naturally established as appropriate approach. However, it does not solve the problem raised by Big Data. Actually, classical visualization techniques are rarely designed to handle such mass of information. Moreover, the problems raised by data storage and computation time have repercussions on the analysis system. For example,the increasing distance between the data and the analyst : the place where the data is stored and the place where the user will perform the analyses arerarely close. In this thesis, we focused on these issues and more particularly on adapting the information visualization techniques for Big Data. First of all focus on relational data : how does the existence of a relation between entity istransmitted and how to improve this transmission for hierarchical data. Then,we focus on multi-variate data and how to handle their complexity for the required computations. Finally, we present the methods we designed to make our techniques compatible with Big Data
17
Kakraba, Samuel. "A Hierarchical Graph for Nucleotide Binding Domain 2." Digital Commons @ East Tennessee State University, 2015. https://dc.etsu.edu/etd/2517.
Full textAbstract:
One of the most prevalent inherited diseases is cystic fibrosis. This disease is caused by a mutation in a membrane protein, the cystic fibrosis transmembrane conductance regulator (CFTR). CFTR is known to function as a chloride channel that regulates the viscosity of mucus that lines the ducts of a number of organs. Generally, most of the prevalent mutations of CFTR are located in one of two nucleotide binding domains, namely, the nucleotide binding domain 1 (NBD1). However, some mutations in nucleotide binding domain 2 (NBD2) can equally cause cystic fibrosis. In this work, a hierarchical graph is built for NBD2. Using this model for NBD2, we examine the consequence of single point mutations on NBD2. We collate the wildtype structure with eight of the most prevalent mutations and observe how the NBD2 is affected by each of these mutations.
18
Fehri, Amin. "Image Characterization by Morphological Hierarchical Representations." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLEM063/document.
Full textAbstract:
Cette thèse porte sur l'extraction de descripteurs hiérarchiques et multi-échelles d'images, en vue de leur interprétation, caractérisation et segmentation. Elle se décompose en deux parties.La première partie expose des éléments théoriques et méthodologiques sur l'obtention de classifications hiérarchiques des nœuds d'un graphe valué aux arêtes. Ces méthodes sont ensuite appliquées à des graphes représentant des images pour obtenir différentes méthodes de segmentation hiérarchique d'images. De plus, nous introduisons différentes façons de combiner des segmentations hiérarchiques. Nous proposons enfin une méthodologie pour structurer et étudier l'espace des hiérarchies que nous avons construites en utilisant la distance de Gromov-Hausdorff entre elles.La seconde partie explore plusieurs applications de ces descriptions hiérarchiques d'images. Nous exposons une méthode pour apprendre à extraire de ces hiérarchies une bonne segmentation de façon automatique, étant donnés un type d'images et un score de bonne segmentation. Nous proposons également des descripteurs d'images obtenus par mesure des distances inter-hiérarchies, et exposons leur efficacité sur des données réelles et simulées. Enfin, nous étendons les potentielles applications de ces hiérarchies en introduisant une technique permettant de prendre en compte toute information spatiale a priori durant leur constructionThis thesis deals with the extraction of hierarchical and multiscale descriptors on images, in order to interpret, characterize and segment them. It breaks down into two parts.The first part outlines a theoretical and methodological approach for obtaining hierarchical clusterings of the nodes of an edge-weighted graph. In addition, we introduce different approaches to combine hierarchical segmentations. These methods are then applied to graphs representing images and derive different hierarchical segmentation techniques. Finally, we propose a methodology for structuring and studying the space of hierarchies by using the Gromov-Hausdorff distance as a metric.The second part explores several applications of these hierarchical descriptions for images. We expose a method to learn how to automatically extract a segmentation of an image, given a type of images and a score of evaluation for a segmentation. We also propose image descriptors obtained by measuring inter-hierarchical distances, and expose their efficiency on real and simulated data. Finally, we extend the potential applications of these hierarchies by introducing a technique to take into account any spatial prior information during their construction
19
Choset, Howie M. Burdick Joel Wakeman Burdick Joel Wakeman. "Sensor based motion planning : the hierarchical generalized Voronoi graph /." Diss., Pasadena, Calif. : California Institute of Technology, 1996. http://resolver.caltech.edu/CaltechETD:etd-12182007-090504.
Full text
20
Holzer, Martin. "Hierarchical speed-up techniques for shortest-path algorithms." [S.l. : s.n.], 2003. http://www.bsz-bw.de/cgi-bin/xvms.cgi?SWB10605142.
Full text
21
Wengle, Emil. "Modelling Hierarchical Structures in Networks Using Graph Theory : With Application to Knowledge Networks in Graph Curricula." Thesis, Uppsala universitet, Signaler och system, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-415044.
Full textAbstract:
Community detection is a topic in network theory that involves assigning labels to nodes based on some distance measure or centrality index. Detecting communities within a network can be useful to perform information condensation. In this thesis we explore how to use the approach for pedagogical purposes, and more precisely to condense and visualise the networks of facts, concepts and procedures (also called Knowledge Components (KCs)) that are offered in higher education programmes. In details, we consider one of the most common quantities used to evaluate the goodness of a community classification, which is the concept of modularity. Detecting communities by computing the maximum possible modularity indexes is indeed usually desired, but this approach is generally unavailable because the associated optimisation problem is NP-complete. This is why practitioners use other algorithms, that instead of computing the optimum they rely on various heuristics to find communities: some use modularity directly, some start from the entire graph and divide it repeatedly, and some contain random elements. This thesis investigates the trade-offs of using different community detection algorithms and variations of the concept of modularity first in general terms, and then for the purpose of identifying communities in knowledge graphs associated to higher education programmes, which can be modelled as directed graphs of KCs. We discover, tweaking and applying these algorithms both on synthetic but also field data that the Louvain algorithm is among the better algorithms of those that we considered, which is mostly thanks to its efficiency. It does not produce a full hierarchy, however, so we recommend Fast Newman if hierarchy is important.
22
Ismaeel, Alaa Aly Khalaf [Verfasser], and H. [Akademischer Betreuer] Schmeck. "Dynamic Hierarchical Graph Drawing / Alaa Aly Khalaf Ismaeel. Betreuer: H. Schmeck." Karlsruhe : KIT-Bibliothek, 2012. http://d-nb.info/1023081776/34.
Full text
23
Cybis, Gabriela Bettella. "Phenotypic Bayesian phylodynamics : hierarchical graph models, antigenic clustering and latent liabilities." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2014. http://hdl.handle.net/10183/132858.
Full textAbstract:
Combining models for phenotypic and molecular evolution can lead to powerful inference tools. Under the flexible framework of Bayesian phylogenetics, I develop statistical methods to address phylodynamic problems in this intersection. First, I present a hierarchical phylogeographic method that combines information across multiple datasets to draw inference on a common geographical spread process. Each dataset represents a parallel realization of this geographic process on a different group of taxa, and the method shares information between these realizations through a hierarchical graph structure. Additionally, I develop a multivariate latent liability model for assessing phenotypic correlation among sets of traits, while controlling for shared evolutionary history. This method can efficiently estimate correlations between multiple continuous traits, binary traits and discrete traits with many ordered or unordered outcomes. Finally, I present a method that uses phylogenetic information to study the evolution of antigenic clusters in influenza. The method builds an antigenic cartography map informed by the assignment of each influenza strain to one of the antigenic clusters.
24
Yang, Fang. "Construction and application of hierarchical matrix preconditioners." Diss., University of Iowa, 2008. https://ir.uiowa.edu/etd/196.
Full textAbstract:
H-matrix techniques use a data-sparse tree structure to represent a dense or a sparse matrix. The leaves of the tree store matrix sub-blocks that are represented in full-matrix format or Rk-matrix (low rank matrix) format. H-matrix arithmetic is defined over the H-matrix representation, which includes operations such as addition, multiplication, inversion, and LU factorization. These H-matrix operations approximate results with almost optimal computational complexity. Based on the properties of H-matrices, the H-matrix preconditioner technique has been introduced. It uses H-matrix operations to construct preconditioners, which are used in iterative methods to speed up the solution of large systems of linear equations (Ax = b). To apply the H-matrix preconditioner technique, the first step is to represent a problem in H-matrix format. The approaches to construct an H-matrix can be divided into two categories: geometric approaches and algebraic approaches.
In this thesis, we present our contributions to algebraic H-matrix construction approaches and H-matrix preconditioner technique. We have developed a new algebraic H-matrix construction approach based on matrix graphs and multilevel graph clustering approaches. Based on the new construction approach, we have also developed a scheme to build algebraic H-matrix preconditioners for systems of saddle point type. To verify the effectiveness of our new construction approach and H-matrix preconditioner scheme, we have applied them to solve various systems of linear equations arising from finite element methods and meshfree methods. The experimental results show that our preconditioners are competitive to other H-matrix preconditioners based on domain decomposition and existing preconditioners such as JOR and AMG preconditioners. Our H-matrix construction approach and preconditioner technique provide an alternative effective way to solve large systems of linear equations.
25
Raitner, Marcus. "Efficient visual navigation a study by the example of hierarchically structured graphs." [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=978647084.
Full text
26
Song, Yi-Zhe. "Hierarchical image descriptions for classification and painting." Thesis, University of Bath, 2009. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.501634.
Full textAbstract:
The overall argument this thesis makes is that topological object structures captured within hierarchical image descriptions are invariant to depictive styles and offer a level of abstraction found in many modern abstract artworks. To show how object structures can be extracted from images, two hierarchical image descriptions are proposed. The first of these is inspired by perceptual organisation; whereas, the second is based on agglomerative clustering of image primitives. This thesis argues the benefits and drawbacks of each image description and empirically show why the second is more suitable in capturing object strucutures. The value of graph theory is demonstrated in extracting object structures, especially from the second type of image description. User interaction during the structure extraction process is also made possible via an image hierarchy editor. Two applications of object structures are studied in depth. On the computer vision side, the problem of object classification is investigated. In particular, this thesis shows that it is possible to classify objects regardless of their depictive styles. This classification problem is approached using a graph theoretic paradigm; by encoding object structures as feature vectors of fixed lengths, object classification can then be treated as a clustering problem in structural feature space and that actual clustering can be done using conventional machine learning techniques. The benefits of object structures in computer graphics are demonstrated from a Non-Photorealistic Rendering (NPR) point of view. In particular, it is shown that topological object structures deliver an appropriate degree of abstraction that often appears in well-known abstract artworks. Moreover, the value of shape simplification is demonstrated in the process of making abstract art. By integrating object structures and simple geometric shapes, it is shown that artworks produced in child-like paintings and from artists such as Wassily Kandinsky, Joan Miro and Henri Matisse can be synthesised and by doing so, the current gamut of NPR styles is extended. The whole process of making abstract art is built into a single piece of software with intuitive GUI.
27
McKenzie, Chapter Harrison Lee. "Textured Hierarchical Precomputed Radiance Transfer." DigitalCommons@CalPoly, 2010. https://digitalcommons.calpoly.edu/theses/333.
Full textAbstract:
Computing complex lighting simulations such as global illumination is a computationally intensive task. Various real time solutions exist to approximate aspects of global illumination such as shadows, however, few of these methods offer single pass rendering solutions for soft shadows (self and other) and inter-reflections. In contrast, Precomputed Radiance Transfer (PRT) is a real-time computer graphics technique which pre-calculates an object's response to potential incident light. At run time, the actual incident light can be used to quickly illuminate the surface, rendering effects such as soft self-shadows and inter-reflections. In this thesis, we show that by calculating PRT lighting coefficients densely over a surface as texture data, additional surface detail can be encoded by integrating other computer graphics techniques, such as normal mapping. By calculating transfer coefficients densely over the surface of a mesh as texture data, greater fidelity can be achieved in lighting coarse meshes than simple interpolation can achieve. Furthermore, the lighting on low polygon objects can be enhanced by drawing surface normal and occlusion data from highly tessellated, detailed meshes. By applying such data to a decimated, simplified mesh, a more detailed and visually pleasing reconstruction can be displayed for a lower cost. In addition, this thesis introduces Hierarchical PRT, which extends some surface effects, such as soft shadows, between objects. Previous approaches to PRT used a more complex neighborhood transfer scheme in order to extend these lighting effects. Hierarchical PRT attempts to capture scene information in a tree data structure which represents coarse lighting relationships between objects. Potential occlusions can be found at run time by utilizing the same spherical harmonic representation used to represent surface lighting to instead store light "filters" between scene tree nodes. Such "filters" can be combined over a set of nodes in the scene to obtain the net shadowing of an object with good performance.
We present both visually pleasing results on simplified meshes using normal mapping and textured PRT and initial results using Hierarchical PRT that captures low frequency lighting information for a small number of dynamic objects which shadow static scene objects with good results.
28
Depardon, Benjamin. "Contribution to the Deployment of a Distributed and Hierarchical Middleware Applied to Cosmological Simulations." Lyon, Ecole normale supérieure, 2010. http://www.theses.fr/2010ENSL0585.
Full textAbstract:
Les travaux présentés dans cette thèse portent sur l’exécution d’applications sur les environnements hétérogènes et distribués que sont les grilles de calcul. Nous étudions de bout en bout le processus permettant à des utilisateurs d’exécuter des applications scientifiques complexes. Les contributions de cette thèse se situent donc à plusieurs niveaux. 1) Déploiement d’intergiciel hiérarchique : nous proposons dans un premier temps un modèle d’exécution pour les intergiciels hiérarchiques. À partir de ce modèle, nous présentons plusieurs heuristiques pour définir automatiquement la meilleure hiérarchie en fonction des exigences des utilisateurs et du type de plate-forme. Nous évaluons la qualité de ces heuristiques en conditions réelles avec l’intergiciel DIET. 2) Partitionnement de graphe : nous proposons un algorithme distribué et auto-stabilisant pour partitionner un graphe quelconque ayant des arêtes pondérées entre les noeuds. Le partitionnement est réalisé en fonction des distances pondérées entre les noeuds et forme des grappes au sein desquelles les noeuds sont à une distance maximale k d’un noeud élu dans la grappe. 3) Ordonnancement : nous étudions l’ordonnancement de tâches indépendantes sous des contraintes de limitation d’utilisation des ressources. Nous définissons des formulations en programme linéaire pour résoudre ce problème dans deux cas : lorsque les tâches arrivent toutes en même temps et lorsqu’elles ont des dates d’arrivée. 4) Simulations cosmologiques : nous avons étudié le comportement d’applications nécessaires à l’exécution de workflows de simulations cosmologiques. Puis, en se basant sur l’intergiciel de grille DIET, nous avons mis en place une infrastructure complète permettant à des utilisateurs non expérimentés de soumettre facilement des simulations cosmologiques sur une grille de calculThe results presented in this thesis deal with the execution of applications on heterogeneous and distributed environments: computing grids. We study, from end-to-end, the process allowing users to execute complex scientific applications. The contributions of this work are thus manifold. 1) Hierarchical middleware deployment: we first present an execution model for hierarchical middleware. Then, based on this model, we present several heuristics to automatically determine the shape of the hierarchy that would best fit the users’ needs, depending on the platform it is executed on. We evaluate the quality of the approach on a real platform using the DIET middleware. 2) Graph clustering: we propose a distributed and self-stabilizing algorithm for clustering weighted graphs. Clustering is done based on a distance metric between nodes: within each created cluster the nodes are no farther than a distance k from an elected leader in the cluster. 3) Scheduling: we study the scheduling of independent tasks under resources usage limitations. We define linear programs to solve this problem in two cases: when tasks arrive all at the same time, and when release dates are considered. 4) Cosmological simulations: we have studied the behavior of applications required to run cosmological simulations workflows. Then, based on the DIET grid middleware, we implemented a complete infrastructure allowing non-expert users to easily submit cosmological simulations on a computing grid
29
Brown, Steven W. "Interactive Part Selection for Mesh and Point Models Using Hierarchical Graph-cut Partitioning." Diss., CLICK HERE for online access, 2008. http://contentdm.lib.byu.edu/ETD/image/etd2420.pdf.
Full text
30
Lima, Daniel Mário de. "Análise visual de dados relacionais: uma abordagem interativa suportada por teoria dos grafos." Universidade de São Paulo, 2013. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-05052014-155415/.
Full textAbstract:
Bancos de dados relacionais são fontes de dados rigidamente estruturadas, caracterizadas por relacionamentos complexos entre um conjunto de relações (tabelas). Entender tais relacionamentos é um desafio, porque os usuários precisam considerar múltiplas relações, entender restrições de integridade, interpretar vários atributos, e construir consultas SQL para cada tentativa de exploração. Neste cenário, introduz-se uma metodologia em duas etapas; primeiro utiliza-se um grafo organizado como uma estrutura hierárquica para modelar os relacionamentos do banco de dados, e então, propõe-se uma nova técnica de visualização para exploração relacional. Os resultados demonstram que a proposta torna a exploração de bases de dados significativamente simplificada, pois o usuário pode navegar visualmente pelos dados com pouco ou nenhum conhecimento sobre a estrutura subjacente. Além disso, a navegação visual de dados remove a necessidade de consultas SQL, e de toda complexidade que elas requerem. Acredita-se que esta abordagem possa trazer um paradigma inovador no que tange à compreensão de dados relacionaisRelational databases are rigid-structured data sources characterized by complex relationships among a set of relations (tables). Making sense of such relationships is a challenging problem because users must consider multiple relations, understand their ensemble of integrity constraints, interpret dozens of attributes, and draw complex SQL queries for each desired data exploration. In this scenario, we introduce a twofold methodology; we use a hierarchical graph representation to efficiently model the database relationships and, on top of it, we designed a visualization technique for rapidly relational exploration. Our results demonstrate that the exploration of databases is deeply simplified as the user is able to visually browse the data with little or no knowledge about its structure, dismissing the need of complex SQL queries. We believe our findings will bring a novel paradigm in what concerns relational data comprehension.
31
Aleksakhin, Vladyslav. "Visualization of gene ontology and cluster analysis results." Thesis, Linnéuniversitetet, Institutionen för datavetenskap, fysik och matematik, DFM, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-21248.
Full textAbstract:
The purpose of the thesis is to develop a new visualization method for Gene Ontologiesand hierarchical clustering. These are both important tools in biology andmedicine to study high-throughput data such as transcriptomics and metabolomicsdata. Enrichment of ontology terms in the data is used to identify statistically overrepresentedontology terms, that give insight into relevant biological processes orfunctional modules. Hierarchical clustering is a standard method to analyze andvisualize data to nd relatively homogeneous clusters of experimental data points.Both methods support the analysis of the same data set, but are usually consideredindependently. However, often a combined view such as: visualizing a large data setin the context of an ontology under consideration of a clustering of the data.The result of the current work is a user-friendly program that combines twodi erent views for analysing Gene Ontology and Cluster simultaneously. To makeexplorations of such a big data possible we developed new visualization approach.
32
Testa, Henrique Gregianin. "Um modelo hierárquico para sistemas de tipos de arquivos implementado como um middleware." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2007. http://hdl.handle.net/10183/25504.
Full textAbstract:
Com a finalidade de facilitar a manipulação de documentos pelos usuários e aplicações, foram desenvolvidas no decorrer do tempo diversas formas para classificar e organizar esses documentos, incluindo a criação de diferentes mecanismos pertinentes a formatos de arquivos, os chamados sistemas de tipos de arquivos. É possível perceber nesse esforço uma crescente preocupação com a correta identificação dos arquivos e com a obtenção de maiores informações sobre seu conteúdo. Afinal, com esse conhecimento as aplicações e ambientes gráficos dos sistemas operacionais podem adicionar novas funcionalidades na manipulação de documentos e arquivos em geral. Neste trabalho se propõe um novo modelo e arquitetura para sistemas de tipos de arquivos. O modelo se baseia em um grafo de tipos representando relações hierárquicas e um índice de metadados de arquivos, usados em conjunto por funcionalidades que são disponibilizadas através de uma API. A construção do grafo de tipos, que desempenha papel central no modelo proposto, envolveu o estudo dos tipos de arquivos registrados nos principais sistemas operacionais, os tipos definidos pelo IANA (Internet Assigned Numbers Authority) e outros tipos comumente utilizados, com a finalidade de selecionálos e interrelacioná-los em uma hierarquia. A arquitetura proposta para o sistema de tipos é um middleware que oferece os serviços abstraindo operações de baixo nível específicos do sistema operacional. O modelo e arquitetura apresentados neste trabalho beneficia principalmente softwares que trabalham intensamente com arquivos, como IDEs (Integrated Development Environment) e ambientes gráficos.Several strategies to classify and organize documents by users and applications has being developed in order to facilitate its manipulation, including creation of different mechanisms related to file formats, known as file type systems. It is possible to notice in these works an increasing concern about file identification correctness and obtaining further information regarding its contents as well. This knowledge allow application and graphical environments of operating systems adding new functionalities on manipulation of documents and files. The present work proposes a new model and architecture to file type systems. The model is based on a file type graph representing hierarchical relationships and an index of file metadata. Both are used by functionalities provided through an API. To build the graph of file types, central piece on the proposed model, it was necessary to study file types registered on the most imporant operating systems, types defined by IANA and other types commonly used. The goal is to collect file types and interlink them in a hierarchy. The proposed architecture for the file type system is a middleware which provides services hiding native operating systems low level operations. The model and architecture presented in this work is specially useful to softwares that handle files intensely, like IDEs (Integrated Development Environment) and graphical environments.
33
Imaev, Aleksey A. "Hierarchical Modeling of Manufacturing Systems Using Max-Plus Algebra." Ohio University / OhioLINK, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1257871858.
Full text
34
Consoli, Sergio. "The development and application of metaheuristics for problems in graph theory : a computational study." Thesis, Brunel University, 2008. http://bura.brunel.ac.uk/handle/2438/3061.
Full textAbstract:
It is known that graph theoretic models have extensive application to real-life discrete optimization problems. Many of these models are NP-hard and, as a result, exact methods may be impractical for large scale problem instances. Consequently, there is a great interest in developing e±cient approximate methods that yield near-optimal solutions in acceptable computational times. A class of such methods, known as metaheuristics, have been proposed with success. This thesis considers some recently proposed NP-hard combinatorial optimization problems formulated on graphs. In particular, the min- imum labelling spanning tree problem, the minimum labelling Steiner tree problem, and the minimum quartet tree cost problem, are inves- tigated. Several metaheuristics are proposed for each problem, from classical approximation algorithms to novel approaches. A compre- hensive computational investigation in which the proposed methods are compared with other algorithms recommended in the literature is reported. The results show that the proposed metaheuristics outper- form the algorithms recommended in the literature, obtaining optimal or near-optimal solutions in short computational running times. In addition, a thorough analysis of the implementation of these methods provide insights for the implementation of metaheuristic strategies for other graph theoretic problems.
35
Anguelov, Bobby. "Video game pathfinding and improvements to discrete search on grid-based maps." Diss., University of Pretoria, 2011. http://hdl.handle.net/2263/22940.
Full textAbstract:
The most basic requirement for any computer controlled game agent in a video game is to be able to successfully navigate the game environment. Pathfinding is an essential component of any agent navigation system. Pathfinding is, at the simplest level, a search technique for finding a route between two points in an environment. The real-time multi-agent nature of video games places extremely tight constraints on the pathfinding problem. This study aims to provide the first complete review of the current state of video game pathfinding both in regards to the graph search algorithms employed as well as the implications of pathfinding within dynamic game environments. Furthermore this thesis presents novel work in the form of a domain specific search algorithm for use on grid-based game maps: the spatial grid A* algorithm which is shown to offer significant improvements over A* within the intended domain. CopyrightDissertation (MSc)--University of Pretoria, 2011.
Computer Science
unrestricted
36
Cowlagi, Raghvendra V. "Hierarchical motion planning for autonomous aerial and terrestrial vehicles." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/41066.
Full textAbstract:
Autonomous mobile robots - both aerial and terrestrial vehicles - have gained immense importance due to the broad spectrum of their potential military and civilian applications. One of the indispensable requirements for the autonomy of a mobile vehicle is the vehicle's capability of planning and executing its motion, that is, finding appropriate control inputs for the vehicle such that the resulting vehicle motion satisfies the requirements of the vehicular task. The motion planning and control problem is inherently complex because it involves two disparate sub-problems: (1) satisfaction of the vehicular task requirements, which requires tools from combinatorics and/or formal methods, and (2) design of the vehicle control laws, which requires tools from dynamical systems and control theory.
Accordingly, this problem is usually decomposed and solved over two levels of hierarchy. The higher level, called the geometric path planning level, finds a geometric path that satisfies the vehicular task requirements, e.g., obstacle avoidance. The lower level, called the trajectory planning level, involves sufficient smoothening of this geometric path followed by a suitable time parametrization to obtain a reference trajectory for the vehicle.
Although simple and efficient, such hierarchical separation suffers a serious drawback: the geometric path planner has no information of the kinematic and dynamic constraints of the vehicle. Consequently, the geometric planner may produce paths that the trajectory planner cannot transform into a feasible reference trajectory. Two main ideas appear in the literature to remedy this problem: (a) randomized sampling-based planning, which eliminates altogether the geometric planner by planning in the vehicle state space, and (b) geometric planning supported by feedback control laws. The former class of methods suffer from a lack of optimality of the resultant trajectory, while the latter class of methods makes a restrictive assumption concerning the vehicle kinematic model.
In this thesis, we propose a hierarchical motion planning framework based on a novel mode of interaction between these two levels of planning. This interaction rests on the solution of a special shortest-path problem on graphs, namely, one using costs defined on multiple edge transitions in the path instead of the usual single edge transition costs. These costs are provided by a local trajectory generation algorithm, which we implement using model predictive control and the concept of effective target sets for simplifying the non-convex constraints involved in the problem. The proposed motion planner ensures "consistency" between the two levels of planning, i.e., a guarantee that the higher level geometric path is always associated with a kinematically and dynamically feasible trajectory. We show that the proposed motion planning approach offers distinct advantages in comparison with the competing approaches of discretization of the state space, of randomized sampling-based motion planning, and of local feedback-based, decoupled hierarchical motion planning. Finally, we propose a multi-resolution implementation of the proposed motion planner, which requires accurate descriptions of the environment and the vehicle only for short-term, local motion planning in the immediate vicinity of the vehicle.
37
Kwok, Wing-hong, and 郭永康. "Streamlined and prioritized hierarchical relations: a technique for improving the effectiveness of theclassification-tree methodology." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2001. http://hub.hku.hk/bib/B2975107X.
Full text
38
Alessi, Nicola. "Hierarchical Inter-Regional Routing Algorithm for Interplanetary Networks." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amslaurea.unibo.it/17468/.
Full textAbstract:
Le comunicazioni interplanetarie sono caratterizzate da lunghi ritardi, perdite elevate e connettività intermittente con frequenti interruzioni. Lo stack TCP/IP è inadatto nell'affrontare questo tipo di problemi. Mentre inizialmente l'unico scenario di riferimento erano le comunicazioni interplanetarie, negli anni successivi è nato il termine "Challenged Networks" per identificare le reti in cui i protocolli tradizionali falliscono. L'idea si evolve così in Delay/Disruption Tolerant Networking(DTN), con l'obiettivo di fornire una soluzione adatta alle challenged network.
Tra i vari aspetti in cui le reti DTN differiscono dai protocolli TCP/IP abbiamo il modo in cui viene effettuato routing. L'attuale algoritmo di routing utilizzato proposto per le reti DTN è chiamato Contact Graph Routing(CGR). L'aspetto che contraddistingue il CGR dagli algoritmi di routing tradizionali è che esso costruisce una rotta di "contatti" (ovvero delle possibilità di comunicazione programmate), anzichè costruire un percorso di nodi. Questa caratteristica è efficace nell'ambito delle reti DTN, dove i contatti sono noti a priori. Nonostante il CGR sia molto efficiente, esso presenta dei problemi di scalabilità. Infatti, con l'aumentare del numero dei contatti, il suo tempo di esecuzione tende a crescere fino a degradare le prestazioni dell'intera rete. In questa tesi viene proposto un algoritmo di routing chiamato Hierarchical Inter-regional Routing (HIRR) che ha l'obiettivo di mitigare il problema di scalabilità del CGR dividendo i nodi della rete in diverse regioni amministrative, in cui l'utilizzo del CGR non risulta essere critico. Lo scopo principale di HIRR è quindi quello di cercare di trarre il massimo beneficio dal CGR, accettando un ragionevole compromesso fra ottimalità delle rotte e tempo di calcolo.
Questa tesi è stata svolta al NASA Jet Propulsion Laboratory(JPL) situato a Pasadena in California, aderendo al Visiting Student Research Program (VSRP).
39
Tran, The Truyen. "On conditional random fields: applications, feature selection, parameter estimation and hierarchical modelling." Curtin University of Technology, Dept. of Computing, 2008. http://espace.library.curtin.edu.au:80/R/?func=dbin-jump-full&object_id=18614.
Full textAbstract:
There has been a growing interest in stochastic modelling and learning with complex data, whose elements are structured and interdependent. One of the most successful methods to model data dependencies is graphical models, which is a combination of graph theory and probability theory. This thesis focuses on a special type of graphical models known as Conditional Random Fields (CRFs) (Lafferty et al., 2001), in which the output state spaces, when conditioned on some observational input data, are represented by undirected graphical models. The contributions of thesis involve both (a) broadening the current applicability of CRFs in the real world and (b) deepening the understanding of theoretical aspects of CRFs. On the application side, we empirically investigate the applications of CRFs in two real world settings. The first application is on a novel domain of Vietnamese accent restoration, in which we need to restore accents of an accent-less Vietnamese sentence. Experiments on half a million sentences of news articles show that the CRF-based approach is highly accurate. In the second application, we develop a new CRF-based movie recommendation system called Preference Network (PN). The PN jointly integrates various sources of domain knowledge into a large and densely connected Markov network. We obtained competitive results against well-established methods in the recommendation field.On the theory side, the thesis addresses three important theoretical issues of CRFs: feature selection, parameter estimation and modelling recursive sequential data. These issues are all addressed under a general setting of partial supervision in that training labels are not fully available. For feature selection, we introduce a novel learning algorithm called AdaBoost.CRF that incrementally selects features out of a large feature pool as learning proceeds. AdaBoost.CRF is an extension of the standard boosting methodology to structured and partially observed data. We demonstrate that the AdaBoost.CRF is able to eliminate irrelevant features and as a result, returns a very compact feature set without significant loss of accuracy. Parameter estimation of CRFs is generally intractable in arbitrary network structures. This thesis contributes to this area by proposing a learning method called AdaBoost.MRF (which stands for AdaBoosted Markov Random Forests). As learning proceeds AdaBoost.MRF incrementally builds a tree ensemble (a forest) that cover the original network by selecting the best spanning tree at a time. As a result, we can approximately learn many rich classes of CRFs in linear time. The third theoretical work is on modelling recursive, sequential data in that each level of resolution is a Markov sequence, where each state in the sequence is also a Markov sequence at the finer grain. One of the key contributions of this thesis is Hierarchical Conditional Random Fields (HCRF), which is an extension to the currently popular sequential CRF and the recent semi-Markov CRF (Sarawagi and Cohen, 2004). Unlike previous CRF work, the HCRF does not assume any fixed graphical structures.
Rather, it treats structure as an uncertain aspect and it can estimate the structure automatically from the data. The HCRF is motivated by Hierarchical Hidden Markov Model (HHMM) (Fine et al., 1998). Importantly, the thesis shows that the HHMM is a special case of HCRF with slight modification, and the semi-Markov CRF is essentially a flat version of the HCRF. Central to our contribution in HCRF is a polynomial-time algorithm based on the Asymmetric Inside Outside (AIO) family developed in (Bui et al., 2004) for learning and inference. Another important contribution is to extend the AIO family to address learning with missing data and inference under partially observed labels. We also derive methods to deal with practical concerns associated with the AIO family, including numerical overflow and cubic-time complexity. Finally, we demonstrate good performance of HCRF against rivals on two applications: indoor video surveillance and noun-phrase chunking.
40
Jezný, Lukáš. "Automatické rozvržení diagramů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2008. http://www.nusl.cz/ntk/nusl-412807.
Full textAbstract:
Automatic layouts for diagram drawing is described in this paper. Major methods, algorithms, metrics for automatic layouts are introduced in theretical part. Practical part of this work was developing algorithms for automatic layouts of organizational structures and business process model diagrams.
41
Han, Sheng, Jianzhong Jiang, Yanshan Huang, Yanping Tang, Jing Cao, Dongqing Wu, and Xinliang Feng. "Hierarchical TiO₂–SnO₂–graphene aerogels for enhanced lithium storage." Royal Society of Chemistry, 2015. https://tud.qucosa.de/id/qucosa%3A36375.
Full textAbstract:
Three-dimensional (3D) TiO₂–SnO₂–graphene aerogels (TTGs)were built up from the graphene oxide nanosheets supported with both TiO₂ and SnO₂ nanoparticles (NPs) via a facile hydrothermal assembly process. The resulting TTGs exhibit a 3D hierarchical porous architecture with uniform distribution of SnO₂ and TiO₂ NPs on the graphene surface, which not only effectively prevents the agglomeration of SnO₂ NPs, but also facilitates the fast ion/electron transport in 3D pathways. As the anode materials in lithium ion batteries (LIBs), TTGs manifest a high reversible capacity of 750 mA h g⁻¹ at 0.1 A g⁻¹ for 100 cycles. Even at a high current density of 1 A g⁻¹, a reversible capacity of 470mA h g⁻¹ can still be achieved from the TTG based LIB anode over 150 cycles.
42
Pock, Michael. "A Hierarchical Modelling and Evaluation Technique for Safety Critical Systems." Thesis, Université de Lorraine, 2012. http://www.theses.fr/2012LORR0103/document.
Full textAbstract:
Cette thèse présente une nouvelle approche pour la modélisation des systèmes de sécurité fonctionnelle qui prend en compte plusieurs modes de défaillance pour les composants et le système global. Les diagrammes de flux d'information (IFDs) ont été initialement développé dans un thèse précédent. Dans ce travail, l'évaluation si l'approche flux d'information être rendue plus efficace par utiliser les diagrammes de décision binaires (BDD).Cette thèse sera d'expliquer pourquoi ce modèle est nécessaire et pratique, suivie d'une explication détaillée des IFDs. Cela inclut sa structure hiérarchique et comment ce modèle peut être appliqué.La prochaine étape est la formalisation du modèle IFD original pour permettre l'utilisation des techniques d'évaluation plus efficaces. Il sera expliqué pourquoi ces étapes de formalisation ont été prises et les avantages de leur utilisation.Ensuite une explication détaillée des algorithmes développés est présenté. Ces algorithmes sont basés sur une combinaison de différentes techniques de BDD. Zero Suppressed BDDs (ZBDDs) sont combinées avec des Boolean Expression Diagrams (BEDs). En outre, la structure des IFD est utilisé pour construire un BDD global sur plusieurs petits BDDs. Cela augmente l'efficacité du processus d'évaluation.Les techniques présentées sont évaluées par l'analyse de plusieurs cas d'utilisation qui sont expliqués dans ce travailThis thesis presents a novel approach for modelling safety critical systems which takes into account several failure modes both for components and the global system. The so called Information Flow Diagrams (IFDs) were originally developed in a previous PhD-thesis. In this work, the evaluation if the IFD-approach should be made more efficient by using Binary Decision Diagrams (BDDs).This thesis will explain why such a model is necessary and practical, followed by a detailed explanation of the IFD-model. This includes its hierarchical structure and how this model can be applied. The next step is to formalise the original IFD-model in order to enable more efficient evaluation techniques. It will be explained why these formalisation steps were taken and what was gained by using them. Afterwards a detailed explanation of the developed algorithms is presented. These algorithms are based on a combination of different BDD-techniques. Zero Suppressed BDDs (ZBDDs) are combined with Boolean Expression Diagrams (BEDs). Furthermore, the structure of the IFDs is used in order to construct a large BDD out of several smaller BDDs. This increases the efficiency of the evaluation process.The presented techniques are evaluated by analysing several use cases which are explained in this work
43
MITSUMATSU, Sawako, Takeshi FURUHASHI, Tomohiro YOSHIKAWA, Akira ITO, 佐和子 光松, 武. 古橋, 大弘 吉川, and 晃. 伊藤. "階層的可視化手法を用いたアソシエーション分析によるプロファイリング." 日本感性工学会, 2011. http://hdl.handle.net/2237/20697.
Full text
44
Zini, Roger. "Placement, routage conjoints et hierarchiques de reseaux prediffuses." Paris 6, 1987. http://www.theses.fr/1987PA066116.
Full textAbstract:
Cette these propose un algorithme original de construction hierarchique d'arbres de steiner ainsi qu'une technique d'estimation de longueur au fur et a mesure de cette construction. Deux algorithmes de partitionnement d'hypergraphes, de maniere gloutonne ou par recuit simule sans rejets, y sont exposes. Elle introduit enfin un concept de directions d'attraction permettant d'effectuer un placement routage de circuits vlsi, a implanter sur des reseaux prediffuses, sous forme de systeme regule par retroaction entre le placement, le routage et l'analyse temporelle, afin d'obtenir du circuit, par un placement-routage adequat, les performances temporelles souhaitees
45
Jang, Justin. "Subset selection in hierarchical recursive pattern assemblies and relief feature instancing for modeling geometric patterns." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/33821.
Full textAbstract:
This thesis is concerned with modeling geometric patterns.
Specifically, a clear and practical definition for regular patterns is proposed.
Based on this definition, this thesis proposes the following modeling setting to describe the semantic transfer of a model between various forms of pattern regularity: (1) recognition or identification of patterns in digital models of 3D assemblies and scenes, (2) pattern regularization, (3) pattern modification and editing by varying the repetition parameters, and (4) establishing exceptions (designed irregularities) in regular patterns.
In line with this setting, this thesis describes a representation and approach for designing and editing hierarchical assemblies based on grouped, nested, and recursively nested patterns. Based on this representation, this thesis presents the OCTOR approach for specifying, recording, and producing exceptions in regular patterns.
To support editing of free-form shape patterns on surfaces, this thesis also presents the imprint-mapping approach which can be used to identify, extract, process, and apply relief features on surfaces. Pattern regularization, modification, and exceptions are addressed for the case of relief features on surfaces.
46
Chang, Ran. "Effective Graph-Based Content--Based Image Retrieval Systems for Large-Scale and Small-Scale Image Databases." DigitalCommons@USU, 2013. https://digitalcommons.usu.edu/etd/2123.
Full textAbstract:
This dissertation proposes two novel manifold graph-based ranking systems for Content-Based Image Retrieval (CBIR). The two proposed systems exploit the synergism between relevance feedback-based transductive short-term learning and semantic feature-based long-term learning to improve retrieval performance. Proposed systems first apply the active learning mechanism to construct users' relevance feedback log and extract high-level semantic features for each image. These systems then create manifold graphs by incorporating both the low-level visual similarity and the high-level semantic similarity to achieve more meaningful structures for the image space. Finally, asymmetric relevance vectors are created to propagate relevance scores of labeled images to unlabeled images via manifold graphs. The extensive experimental results demonstrate two proposed systems outperform the other state-of-the-art CBIR systems in the context of both correct and erroneous users' feedback.
47
Cunningham, James. "Efficient, Parameter-Free Online Clustering." The Ohio State University, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=osu1606762403895603.
Full text
48
Rodríguez, Sánchez Fernando. "Impact of technology readiness in the development of automotive systems when incorporating new styling : a graph theory approach to OPM hierarchical decomposition of the system's architecture." Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/107345.
Full textAbstract:
Thesis: S.M. in Engineering and Management, Massachusetts Institute of Technology, School of Engineering, Institute for Data, Systems, and Society, System Design and Management Program, 2014.Cataloged from PDF version of thesis.
Includes bibliographical references (page 55).
This thesis addresses to find whether technology readiness, while developing a system of new derivative vehicles, has an influence on the time required to design a part that involves styling and engineering activities. For doing so Styling Level and Technology Readiness were identified as independent variables, whereas Styling Iterations and Styling Iterations Time were designated as the dependent variables. In this case, the tools used to confirm correlation among variables were simple and multiple linear regressions. As it will be further detailed, Styling Iterations Time had the highest response to Technology Readiness while the rest of variables had no significant correlation on time duration for Studio and Engineering design activities. Based on hypothesis results and using OPM hierarchical decomposition, relations between processes and objects were analyzed at a given design state in order to evaluate complete matching relying on bipartite graphs and Hall's Marriage theorem. In addition, it was outlined how to identify delayed processes that fail to coexist due to a low technology readiness at a given design state using the Four-Colour theorem and elaborating about the application of chromatic number and polynomials to the OPM system's architecture. The system of interest was the headlamps system developed under Ford Global Product Development System (GPDS) using the Global Exterior Lighting Plan (PDP).
by Fernando Rodríguez Sánchez.
S.M. in Engineering and Management
49
Randrianasoa, Tianatahina Jimmy Francky. "Représentation d'images hiérarchique multi-critère." Thesis, Reims, 2017. http://www.theses.fr/2017REIMS040/document.
Full textAbstract:
La segmentation est une tâche cruciale en analyse d’images. L’évolution des capteurs d’acquisition induit de nouvelles images de résolution élevée, contenant des objets hétérogènes. Il est aussi devenu courant d’obtenir des images d’une même scène à partir de plusieurs sources. Ceci rend difficile l’utilisation des méthodes de segmentation classiques. Les approches de segmentation hiérarchiques fournissent des solutions potentielles à ce problème. Ainsi, l’Arbre Binaire de Partitions (BPT) est une structure de données représentant le contenu d’une image à différentes échelles. Sa construction est généralement mono-critère (i.e. une image, une métrique) et fusionne progressivement des régions connexes similaires. Cependant, la métrique doit être définie a priori par l’utilisateur, et la gestion de plusieurs images se fait en regroupant de multiples informations issues de plusieurs bandes spectrales dans une seule métrique. Notre première contribution est une approche pour la construction multicritère d’un BPT. Elle établit un consensus entre plusieurs métriques, permettant d’obtenir un espace de segmentation hiérarchique unifiée. Par ailleurs, peu de travaux se sont intéressés à l’évaluation de ces structures hiérarchiques. Notre seconde contribution est une approche évaluant la qualité des BPTs en se basant sur l’analyse intrinsèque et extrinsèque, suivant des exemples issus de vérités-terrains. Nous discutons de l’utilité de cette approche pour l’évaluation d’un BPT donné mais aussi de la détermination de la combinaison de paramètres adéquats pour une application précise. Des expérimentations sur des images satellitaires mettent en évidence la pertinence de ces approches en segmentation d’imagesSegmentation is a crucial task in image analysis. Novel acquisition devices bring new images with higher resolutions, containing more heterogeneous objects. It becomes also easier to get many images of an area from different sources. This phenomenon is encountered in many domains (e.g. remote sensing, medical imaging) making difficult the use of classical image segmentation methods. Hierarchical segmentation approaches provide solutions to such issues. Particularly, the Binary Partition Tree (BPT) is a hierarchical data-structure modeling an image content at different scales. It is built in a mono-feature way (i.e. one image, one metric) by merging progressively similar connected regions. However, the metric has to be carefully thought by the user and the handling of several images is generally dealt with by gathering multiple information provided by various spectral bands into a single metric. Our first contribution is a generalized framework for the BPT construction in a multi-feature way. It relies on a strategy setting up a consensus between many metrics, allowing us to obtain a unified hierarchical segmentation space. Surprisingly, few works were devoted to the evaluation of hierarchical structures. Our second contribution is a framework for evaluating the quality of BPTs relying both on intrinsic and extrinsic quality analysis based on ground-truth examples. We also discuss about the use of this evaluation framework both for evaluating the quality of a given BPT and for determining which BPT should be built for a given application. Experiments using satellite images emphasize the relevance of the proposed frameworks in the context of image segmentation
50
Triestino, Michele. "La dynamique des difféomorphismes du cercle selon le point de vue de la mesure." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2014. http://tel.archives-ouvertes.fr/tel-01065468.
Full textAbstract:
Les travaux de ma thèse s'articulent en trois parties distinctes.Dans la première partie j'étudie les mesures de Malliavin-Shavguldize sur les difféomorphismes du cercle et de l'intervalle. Il s'agit de mesures de type " Haar " pour ces groupes de dimension infinie : elles furent introduites il a une vingtaine d'années pour permettre une étude de leur théorie des représentations. Un premier chapitre est dédié à recueillir les résultats présents dans la littérature et et les représenter dans une forme plus étendue, avec un regard particulier sur les propriétés de quasi-invariance de ces mesures. Ensuite j'étudie de problèmes de nature plus dynamique : quelle est la dynamique qu'on doit s'attendre d'un difféomorphisme choisi uniformément par rapport à une mesure de Malliavin-Shavguldize ? Je démontre en particulier qu'il y a une forte présence des difféomorphismes de type Morse-Smale.La partie suivante vient de mon premier travail publié, obtenu en collaboration avec Andrés Navas. Inspirés d'un théorème récent de Avila et Kocsard sur l'unicité des distributions invariantes par un difféomorphisme lisse minimal du cercle, nous analysons le même problème en régularité faible, avec des argument plus géométriques.La dernière partie est constituée des résultats récemment obtenus avec Mikhail Khristoforov et Victor Kleptsyn. Nous abordons les problèmes reliés à la gravité quantique de Liouville en étudiant des espaces auto-similaires qui sont la limite de graphes finis. Nous démontrons qu'il est possible de trouver des distances aléatoires non-triviales sur ces espaces qui sont compatibles avec la structure auto-similaire.