Dissertations / Theses on the topic 'Relation Graphs'
To see the other types of publications on this topic, follow the link: Relation 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 'Relation 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
Mercier, Pierre-Adelin. "Graphages à type d'isomorphisme prescrit." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2012. http://tel.archives-ouvertes.fr/tel-00751265.
Full textAbstract:
On considère R une relation d'équivalence borélienne standard de type I I1 sur un espace de probabilités (X, µ). On étudie une certaine propriété d'homogénéité pour un graphage fixé de la relation R : on suppose que les feuilles du graphage sont toutes isomorphes à un certain graphe transitif (connexe, infini, localement fini) Γ. Que peut-on dire sur la relation ? Dans ce cas, en considérant une action "à la Mackey", on montre qu'il existe (Z ,η) un revêtement standard probabilisé de (X, µ), une action libre (qui préserve η) sur Z du groupe G (localement compact, à base dénombrable d'ouverts) des automorphismes du graphe et un isomorphisme stable des groupoïdes mesurés associés. On fait le lien entre les propriétés du groupe G et celles de la relation de départ ; en particulier la propriété (T), (H) et la moyennabilité "passent" du graphe à la relation et réciproquement. On déduit aussi de la construction quelques couplages d'équivalence mesurée (ou plus généralement des "randembeddings") entre certains sous-groupes des automorphismes de Γ et tout groupe qui contient orbitalement la relation R. Dans un deuxième chapitre, on aborde le cas particulier de la propriété (T) relative pour les paires de groupes (ΓxZ^2, Z^2), où Γ est un sous-groupe non moyennable de SL(2,Z). Cette propriété a d'abord été prouvée par Marc Burger, puis "re-démontrée" plus "visuellement" quelques années plus tard dans le cas de SL(2,Z)xZ^2 par Y. Shalom, en utilisant des découpages du plan. On reprend cette technique dans le cas général du théorème de Burger afin d'obtenir par un algorithme des constantes de Kazhdan explicites pour toute paire (ΓxZ^2, Z^2).
2
Byrne, Kate. "Populating the Semantic Web : combining text and relational databases as RDF graphs." Thesis, University of Edinburgh, 2009. http://hdl.handle.net/1842/3781.
Full textAbstract:
The Semantic Web promises a way of linking distributed information at a granular level by interconnecting compact data items instead of complete HTML pages. New data is gradually being added to the Semantic Web but there is a need to incorporate existing knowledge. This thesis explores ways to convert a coherent body of information from various structured and unstructured formats into the necessary graph form. The transformation work crosses several currently active disciplines, and there are further research questions that can be addressed once the graph has been built. Hybrid databases, such as the cultural heritage one used here, consist of structured relational tables associated with free text documents. Access to the data is hampered by complex schemas, confusing terminology and difficulties in searching the text effectively. This thesis describes how hybrid data can be unified by assembly into a graph. A major component task is the conversion of relational database content to RDF. This is an active research field, to which this work contributes by examining weaknesses in some existing methods and proposing alternatives. The next significant element of the work is an attempt to extract structure automatically from English text using natural language processing methods. The first claim made is that the semantic content of the text documents can be adequately captured as a set of binary relations forming a directed graph. It is shown that the data can then be grounded using existing domain thesauri, by building an upper ontology structure from these. A schema for cultural heritage data is proposed, intended to be generic for that domain and as compact as possible. Another hypothesis is that use of a graph will assist retrieval. The structure is uniform and very simple, and the graph can be queried even if the predicates (or edge labels) are unknown. Additional benefits of the graph structure are examined, such as using path length between nodes as a measure of relatedness (unavailable in a relational database where there is no equivalent concept of locality), and building information summaries by grouping the attributes of nodes that share predicates. These claims are tested by comparing queries across the original and the new data structures. The graph must be able to answer correctly queries that the original database dealt with, and should also demonstrate valid answers to queries that could not previously be answered or where the results were incomplete.
3
Bouakaz, Adnan. "Real-time scheduling of dataflow graphs." Phd thesis, Université Rennes 1, 2013. http://tel.archives-ouvertes.fr/tel-00945453.
Full textAbstract:
The ever-increasing functional and nonfunctional requirements in real-time safety-critical embedded systems call for new design flows that solve the specification, validation, and synthesis problems. Ensuring key properties, such as functional determinism and temporal predictability, has been the main objective of many embedded system design models. Dataflow models of computation (such as KPN, SDF, CSDF, etc.) are widely used to model stream-based embedded systems due to their inherent functional determinism. Since the introduction of the (C)SDF model, a considerable effort has been made to solve the static-periodic scheduling problem. Ensuring boundedness and liveness is the essence of the proposed algorithms in addition to optimizing some nonfunctional performance metrics (e.g. buffer minimization, throughput maximization, etc.). However, nowadays real-time embedded systems are so complex that real-time operating systems are used to manage hardware resources and host real-time tasks. Most of real-time operating systems rely on priority-driven scheduling algorithms (e.g. RM, EDF, etc.) instead of static schedules which are inflexible and difficult to maintain. This thesis addresses the real-time scheduling problem of dataflow graph specifications; i.e. transformation of the dataflow specification to a set of independent real-time tasks w.r.t. a given priority-driven scheduling policy such that the following properties are satisfied: (1) channels are bounded and overflow/underflow-free; (2) the task set is schedulable on a given uniprocessor (or multiprocessor) architecture. This problem requires the synthesis of scheduling parameters (e.g. periods, priorities, processor allocation, etc.) and channel capacities. Furthermore, the thesis considers two performance optimization problems: buffer minimization and throughput maximization.
4
Eichler, Kathrin [Verfasser], and Josef van [Akademischer Betreuer] Genabith. "Generating and applying textual entailment graphs for relation extraction and email categorization / Kathrin Eichler ; Betreuer: Josef van Genabith." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2018. http://d-nb.info/1162892242/34.
Full text
5
Capshaw, Riley. "Relation Classification using Semantically-Enhanced Syntactic Dependency Paths : Combining Semantic and Syntactic Dependencies for Relation Classification using Long Short-Term Memory Networks." Thesis, Linköpings universitet, Interaktiva och kognitiva system, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-153877.
Full textAbstract:
Many approaches to solving tasks in the field of Natural Language Processing (NLP) use syntactic dependency trees (SDTs) as a feature to represent the latent nonlinear structure within sentences. Recently, work in parsing sentences to graph-based structures which encode semantic relationships between words—called semantic dependency graphs (SDGs)—has gained interest. This thesis seeks to explore the use of SDGs in place of and alongside SDTs within a relation classification system based on long short-term memory (LSTM) neural networks. Two methods for handling the information in these graphs are presented and compared between two SDG formalisms. Three new relation extraction system architectures have been created based on these methods and are compared to a recent state-of-the-art LSTM-based system, showing comparable results when semantic dependencies are used to enhance syntactic dependencies, but with significantly fewer training parameters.
6
Benkoussas, Chahinez. "Approches non supervisées pour la recommandation de lectures et la mise en relation automatique de contenus au sein d'une bibliothèque numérique." Thesis, Aix-Marseille, 2016. http://www.theses.fr/2016AIXM4379/document.
Full textAbstract:
Cette thèse s’inscrit dans le domaine de la recherche d’information (RI) et la recommandation de lecture. Elle a pour objets :— La création de nouvelles approches de recherche de documents utilisant des techniques de combinaison de résultats, d’agrégation de données sociales et de reformulation de requêtes ;— La création d’une approche de recommandation utilisant des méthodes de RI et les graphes entre les documents. Deux collections de documents ont été utilisées. Une collection qui provient de l’évaluation CLEF (tâche Social Book Search - SBS) et la deuxième issue du domaine des sciences humaines et sociales (OpenEdition, principalement Revues.org). La modélisation des documents de chaque collection repose sur deux types de relations :— Dans la première collection (CLEF SBS), les documents sont reliés avec des similarités calculées par Amazon qui se basent sur plusieurs facteurs (achats des utilisateurs, commentaires, votes, produits achetés ensemble, etc.) ;— Dans la deuxième collection (OpenEdition), les documents sont reliés avec des relations de citations (à partir des références bibliographiques).Le manuscrit est structuré en deux parties. La première partie «état de l’art» regroupe une introduction générale, un état de l’art sur la RI et sur les systèmes de recommandation. La deuxième partie «contributions» regroupe un chapitre sur la détection de comptes rendus de lecture au sein de la collection OpenEdition (Revues.org), un chapitre sur les méthodes de RI utilisées sur des requêtes complexes et un dernier chapitre qui traite l’approche de recommandation proposée qui se base sur les graphesThis thesis deals with the field of information retrieval and the recommendation of reading. It has for objects:— The creation of new approach of document retrieval and recommendation using techniques of combination of results, aggregation of social data and reformulation of queries;— The creation of an approach of recommendation using methods of information retrieval and graph theories.Two collections of documents were used. First one is a collection which is provided by CLEF (Social Book Search - SBS) and the second from the platforms of electronic sources in Humanities and Social Sciences OpenEdition.org (Revues.org). The modelling of the documents of every collection is based on two types of relations:— For the first collection (SBS), documents are connected with similarity calculated by Amazon which is based on several factors (purchases of the users, the comments, the votes, products bought together, etc.);— For the second collection (OpenEdition), documents are connected with relations of citations, extracted from bibliographical references.We show that the proposed approaches bring in most of the cases gain in the performances of research and recommendation. The manuscript is structured in two parts. The first part "state of the art" includes a general introduction, a state of the art of informationretrieval and recommender systems. The second part "contributions" includes a chapter on the detection of reviews of books in Revues.org; a chapter on the methods of IR used on complex queries written in natural language and last chapter which handles the proposed approach of recommendation which is based on graph
7
Ravelo, Jesus N. "Relations, graphs and programs." Thesis, University of Oxford, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.299107.
Full text
8
Atto, Muhsin. "Implementing Order Relations on Graphs." Thesis, Uppsala University, Department of Information Technology, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-101170.
Full textAbstract:
The design of automatic verification methods for programs manipulating dynamic data structures is a challenging problem. We consider programs that operate on a data structures with one next-pointer, such as singly linked lists and circular lists. We refer to such data structures as heaps. We represent a heap as a graph, where vertices in the graph represent cells in the heap. To test that a program is safe, we should check that the out put of this program is well formed and is sorted. The aim of this project is to design a number of algorithms to test the different orderings between graphs which arise when including heaps. More precisely, given two graphs, G1 and G2, we check that G1 can be included in G2, using different type of orderings.
9
Lucas, Claire. "Trois essais sur les relations entre les invariants structuraux des graphes et le spectre du Laplacien sans signe." Phd thesis, Ecole Polytechnique X, 2013. http://pastel.archives-ouvertes.fr/pastel-00956183.
Full textAbstract:
Le spectre du Laplacien sans signe a fait l'objet de beaucoup d'attention dans la communauté scientifique ces dernières années. La principale raison est l'intuition, basée sur une étude des petits graphes et sur des propriétés valides pour des graphes de toutes tailles, que plus de graphes sont déterminés par le spectre de cette matrice que par celui de la matrice d'adjacence et du Laplacien. Les travaux présentés dans cette thèse ont apporté des éléments nouveaux sur les informations contenues dans le spectre cette matrice. D'une part, on y présente des relations entre les invariants de structure et une valeur propre du Laplacien sans signe. D'autre part, on présente des familles de graphes extrêmes pour deux de ses valeurs propres, avec et sans contraintes additionnelles sur la forme de graphe. Il se trouve que ceux-ci sont très similaires à ceux obtenus dans les mêmes conditions avec les valeurs propres de la matrice d'adjacence. Cela aboutit à la définition de familles de graphes pour lesquelles, le spectre du Laplacien sans signe ou une de ses valeurs propres, le nombre de sommets et un invariant de structure suffisent à déterminer le graphe. Ces résultats, par leur similitude avec ceux de la littérature viennent confirmer l'idée que le Laplacien sans signe détermine probablement aussi bien les graphes que la matrice d'adjacence.
10
Haugeard, Jean-Emmanuel. "Extraction et reconnaissance de primitives dans les façades de Paris à l'aide d'appariement de graphes." Thesis, Cergy-Pontoise, 2010. http://www.theses.fr/2010CERG0497.
Full textAbstract:
Cette dernière décennie, la modélisation des villes 3D est devenue l'un des enjeux de la recherche multimédia et un axe important en reconnaissance d'objets. Dans cette thèse nous nous sommes intéressés à localiser différentes primitives, plus particulièrement les fenêtres, dans les façades de Paris. Dans un premier temps, nous présentons une analyse des façades et des différentes propriétés des fenêtres. Nous en déduisons et proposons ensuite un algorithme capable d'extraire automatiquement des hypothèses de fenêtres. Dans une deuxième partie, nous abordons l'extraction et la reconnaissance des primitives à l'aide d'appariement de graphes de contours. En effet une image de contours est lisible par l'oeil humain qui effectue un groupement perceptuel et distingue les entités présentes dans la scène. C'est ce mécanisme que nous avons cherché à reproduire. L'image est représentée sous la forme d'un graphe d'adjacence de segments de contours, valué par des informations d'orientation et de proximité des segments de contours. Pour la mise en correspondance inexacte des graphes, nous proposons plusieurs variantes d'une nouvelle similarité basée sur des ensembles de chemins tracés sur les graphes, capables d'effectuer les groupements des contours et robustes aux changements d'échelle. La similarité entre chemins prend en compte la similarité des ensembles de segments de contours et la similarité des régions définies par ces chemins. La sélection des images d'une base contenant un objet particulier s'effectue à l'aide d'un classifieur SVM ou kppv. La localisation des objets dans l'image utilise un système de vote à partir des chemins sélectionnés par l'algorithme d'appariementThis last decade, modeling of 3D city became one of the challenges of multimedia search and an important focus in object recognition. In this thesis we are interested to locate various primitive, especially the windows, in the facades of Paris. At first, we present an analysis of the facades and windows properties. Then we propose an algorithm able to extract automatically window candidates. In a second part, we discuss about extraction and recognition primitives using graph matching of contours. Indeed an image of contours is readable by the human eye, which uses perceptual grouping and makes distinction between entities present in the scene. It is this mechanism that we have tried to replicate. The image is represented as a graph of adjacency of segments of contours, valued by information orientation and proximity to edge segments. For the inexact matching of graphs, we propose several variants of a new similarity based on sets of paths, able to group several contours and robust to scale changes. The similarity between paths takes into account the similarity of sets of segments of contours and the similarity of the regions defined by these paths. The selection of images from a database containing a particular object is done using a KNN or SVM classifier
11
Ricatte, Thomas. "Hypernode graphs for learning from binary relations between sets of objects." Thesis, Lille 3, 2015. http://www.theses.fr/2015LIL30001/document.
Full text
12
Ezzeddine, Diala. "A contribution to topological learning and its application in Social Networks." Thesis, Lyon 2, 2014. http://www.theses.fr/2014LYO22011/document.
Full textAbstract:
L'Apprentissage Supervisé est un domaine populaire de l'Apprentissage Automatique en progrès constant depuis plusieurs années. De nombreuses techniques ont été développées pour résoudre le problème de classification, mais, dans la plupart des cas, ces méthodes se basent sur la présence et le nombre de points d'une classe donnée dans des zones de l'espace que doit définir le classifieur. Á cause de cela la construction de ce classifieur est dépendante de la densité du nuage de points des données de départ. Dans cette thèse, nous montrons qu'utiliser la topologie des données peut être une bonne alternative lors de la construction des classifieurs. Pour cela, nous proposons d'utiliser les graphes topologiques comme le Graphe de Gabriel (GG) ou le Graphes des Voisins Relatifs (RNG). Ces dernier représentent la topologie de données car ils sont basées sur la notion de voisinages et ne sont pas dépendant de la densité. Pour appliquer ce concept, nous créons une nouvelle méthode appelée Classification aléatoire par Voisinages (Random Neighborhood Classification (RNC)). Cette méthode utilise des graphes topologiques pour construire des classifieurs. De plus, comme une Méthodes Ensemble (EM), elle utilise plusieurs classifieurs pour extraire toutes les informations pertinentes des données. Les EM sont bien connues dans l'Apprentissage Automatique. Elles génèrent de nombreux classifieurs à partir des données, puis agrègent ces classifieurs en un seul. Le classifieur global obtenu est reconnu pour être très eficace, ce qui a été montré dans de nombreuses études. Cela est possible car il s'appuie sur des informations obtenues auprès de chaque classifieur qui le compose. Nous avons comparé RNC à d'autres méthodes de classification supervisées connues sur des données issues du référentiel UCI Irvine. Nous constatons que RNC fonctionne bien par rapport aux meilleurs d'entre elles, telles que les Forêts Aléatoires (RF) et Support Vector Machines (SVM). La plupart du temps, RNC se classe parmi les trois premières méthodes en terme d'eficacité. Ce résultat nous a encouragé à étudier RNC sur des données réelles comme les tweets. Twitter est un réseau social de micro-blogging. Il est particulièrement utile pour étudier l'opinion à propos de l'actualité et sur tout sujet, en particulier la politique. Cependant, l'extraction de l'opinion politique depuis Twitter pose des défis particuliers. En effet, la taille des messages, le niveau de langage utilisé et ambiguïté des messages rend très diffcile d'utiliser les outils classiques d'analyse de texte basés sur des calculs de fréquence de mots ou des analyses en profondeur de phrases. C'est cela qui a motivé cette étude. Nous proposons d'étudier les couples auteur/sujet pour classer le tweet en fonction de l'opinion de son auteur à propos d'un politicien (un sujet du tweet). Nous proposons une procédure qui porte sur l'identification de ces opinions. Nous pensons que les tweets expriment rarement une opinion objective sur telle ou telle action d'un homme politique mais plus souvent une conviction profonde de son auteur à propos d'un mouvement politique. Détecter l'opinion de quelques auteurs nous permet ensuite d'utiliser la similitude dans les termes employés par les autres pour retrouver ces convictions à plus grande échelle. Cette procédure à 2 étapes, tout d'abord identifier l'opinion de quelques couples de manière semi-automatique afin de constituer un référentiel, puis ensuite d'utiliser l'ensemble des tweets d'un couple (tous les tweets d'un auteur mentionnant un politicien) pour les comparer avec ceux du référentiel. L'Apprentissage Topologique semble être un domaine très intéressant à étudier, en particulier pour résoudre les problèmes de classificationSupervised Learning is a popular field of Machine Learning that has made recent progress. In particular, many methods and procedures have been developed to solve the classification problem. Most classical methods in Supervised Learning use the density estimation of data to construct their classifiers.In this dissertation, we show that the topology of data can be a good alternative in constructing classifiers. We propose using topological graphs like Gabriel graphs (GG) and Relative Neighborhood Graphs (RNG) that can build the topology of data based on its neighborhood structure. To apply this concept, we create a new method called Random Neighborhood Classification (RNC).In this method, we use topological graphs to construct classifiers and then apply Ensemble Methods (EM) to get all relevant information from the data. EM is well known in Machine Learning, generates many classifiers from data and then aggregates these classifiers into one. Aggregate classifiers have been shown to be very efficient in many studies, because it leverages relevant and effective information from each generated classifier. We first compare RNC to other known classification methods using data from the UCI Irvine repository. We find that RNC works very well compared to very efficient methods such as Random Forests and Support Vector Machines. Most of the time, it ranks in the top three methods in efficiency. This result has encouraged us to study the efficiency of RNC on real data like tweets. Twitter, a microblogging Social Network, is especially useful to mine opinion on current affairs and topics that span the range of human interest, including politics. Mining political opinion from Twitter poses peculiar challenges such as the versatility of the authors when they express their political view, that motivate this study. We define a new attribute, called couple, that will be very helpful in the process to study the tweets opinion. A couple is an author that talk about a politician. We propose a new procedure that focuses on identifying the opinion on tweet using couples. We think that focusing on the couples's opinion expressed by several tweets can overcome the problems of analysing each single tweet. This approach can be useful to avoid the versatility, language ambiguity and many other artifacts that are easy to understand for a human being but not automatically for a machine.We use classical Machine Learning techniques like KNN, Random Forests (RF) and also our method RNC. We proceed in two steps : First, we build a reference set of classified couples using Naive Bayes. We also apply a second alternative method to Naive method, sampling plan procedure, to compare and evaluate the results of Naive method. Second, we evaluate the performance of this approach using proximity measures in order to use RNC, RF and KNN. The expirements used are based on real data of tweets from the French presidential election in 2012. The results show that this approach works well and that RNC performs very good in order to classify opinion in tweets.Topological Learning seems to be very intersting field to study, in particular to address the classification problem. Many concepts to get informations from topological graphs need to analyse like the ones described by Aupetit, M. in his work (2005). Our work show that Topological Learning can be an effective way to perform classification problem
13
SACLE, JEAN-FRANCOIS. "Relations entre parametres de graphes." Paris 11, 1995. http://www.theses.fr/1995PA112543.
Full textAbstract:
Ce travail a pris sa source dans une liste de conjectures elaborees a partir du programme informatique denomme graffiti de s. Fajtlowicz. Ces conjectures mettent en relation deux ou plusieurs parametres de graphes apres avoir teste ces relations sur une bibliotheque de graphes de reference. Certaines conjectures peuvent ne concerner que des sous-familles, telles que la famille des graphes sans triangles. La premiere partie de l'etude concerne le parametre nomme residu, qui est intuitivement en correlation avec le nombre de stabilite du graphe. De fait, le principal resultat de cette partie montre que le residu est toujours au plus egal au nombre de stabilite. D'autres proprietes sont egalement donnees dans cette partie, autour du residu. Dans la deuxieme partie, nous faisons une courte etude de ce qu'on nomme le degre local moyen dans les graphes. On y adjoint quelques proprietes du parametre nomme deficience. Ces deux parametres concernent les voisinages des sommets dans le graphe. La troisieme partie fournit une introduction algebrique aux proprietes de base classiques du spectre de la matrice d'adjacence d'un graphe. Ensuite, on donne la preuve de certaines conjectures de graffiti, et des contre-exemples pour certaines autres, qui impliquent les valeurs propres de cette matrice dans leurs enonces. Beaucoup de ces proprietes resultent de resultats plus generaux etablis dans cette partie
14
Bowen, Brian A. "Augmenting the relational model with conceptual graphs." Thesis, Loughborough University, 1995. https://dspace.lboro.ac.uk/2134/10426.
Full textAbstract:
While the relational model for data storage is sufficient for the modelling and manipulation of a large number of application domains, a growing class of application domains are either difficult or impossible for the relational model to deal with efficiently. The realisation of this fact has led to a proliferation of data models that attempt to increase the complexity and semantic capture of the domains that they can model - the development of object-oriented databases and the various semantic data models are a result of this. The idea of using logic to define, manipulate and constrain data has given rise to large numbers of systems that interface - not always successfully - a database system and a logic processing system. Most such systems are based on Prolog or its derivations. This thesis describes the development and use of an object-oriented and semantically rich form of logic - conceptual graph theory - as a system for the definition, manipulation, and constraint of data. It describes a theoretical correspondence between conceptual graph theory and the relational model, and proceeds to develop an augmented, hybrid theory that is formally more expressive and as rigorous as those languages based on the relational algebra or calculus. This thesis also describes the design and implementation of a hybrid relational database - conceptual graph system, that has a cleaner and more principled system of semantic capture than other (for example, Prolog-based) systems, and that is also adaptive in nature - it automatically modifies its underlying storage structures in accordance with modifications made to the structures of the application domain over time. This completely shields the user from any responsibility for database design and maintenance, and so the user need only be concerned with application domain knowledge. Although the implementation described is incomplete, it can be extended to produce a deductive, object-oriented database system based on conceptual graphs.
15
Kim, Been. "Multiple relative pose graphs for cooperative mapping." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/59680.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2010.Cataloged from PDF version of thesis.
Includes bibliographical references (p. 75-78).
This thesis describes a new representation and algorithm for cooperative and persistent simultaneous localization and mapping (SLAM) using multiple robots. Recent pose graph representations have proven very successful for single robot mapping and localization. Among these methods, iSAM (incremental smoothing and mapping) gives an exact incremental solution to the SLAM problem by solving a full nonlinear optimization problem in real-time. In this paper, we present a novel extension to iSAM to facilitate multi-robot mapping based on multiple pose graphs. Our main contribution is a relative formulation of the relationship between multiple pose graphs. Our formulation avoids the initialization problem and leads to an efficient solution when compared to a completely global solution. Efficient access to covariances at any time for relative parameters is also provided, facilitating data association and loop closing. Each individual pose graph still uses a global parameterization, so that the overall system provides a globally consistent multi-robot solution. The performance of the technique is illustrated on a publicly available multi-robot data set as well as other data including a helicopter-ground robot combination.
by Been Kim.
S.M.
16
Chandra, Nagasai. "Node Classification on Relational Graphs using Deep-RGCNs." DigitalCommons@CalPoly, 2021. https://digitalcommons.calpoly.edu/theses/2265.
Full textAbstract:
Knowledge Graphs are fascinating concepts in machine learning as they can hold usefully structured information in the form of entities and their relations. Despite the valuable applications of such graphs, most knowledge bases remain incomplete. This missing information harms downstream applications such as information retrieval and opens a window for research in statistical relational learning tasks such as node classification and link prediction. This work proposes a deep learning framework based on existing relational convolutional (R-GCN) layers to learn on highly multi-relational data characteristic of realistic knowledge graphs for node property classification tasks. We propose a deep and improved variant, Deep-RGCNs, with dense and residual skip connections between layers. These skip connections are known to be very successful with popular deep CNN-architectures such as ResNet and DenseNet. In our experiments, we investigate and compare the performance of Deep-RGCN with different baselines on multi-relational graph benchmark datasets, AIFB and MUTAG, and show how the deep architecture boosts the performance in the task of node property classification. We also study the training performance of Deep-RGCNs (with N layers) and discuss the gradient vanishing and over-smoothing problems common to deeper GCN architectures.
17
Sun, Pak Kiu. "Incidence coloring : origins, developments and relation with other colorings." HKBU Institutional Repository, 2007. http://repository.hkbu.edu.hk/etd_ra/826.
Full text
18
Cavalheiro, Simone André da Costa. "Relational approach of graph grammars." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2010. http://hdl.handle.net/10183/25516.
Full textAbstract:
Gramática de grafos é uma linguagem formal bastante adequada para sistemas cujos estados possuem uma topologia complexa (que envolvem vários tipos de elementos e diferentes tipos de relações entre eles) e cujo comportamento é essencialmente orientado pelos dados, isto é, eventos são disparados por configurações particulares do estado. Vários sistemas reativos são exemplos desta classe de aplicações, como protocolos para sistemas distribuídos e móveis, simulação de sistemas biológicos, entre outros. A verificação de gramática de grafos através da técnica de verificação de modelos já é utilizada por diversas abordagens. Embora esta técnica constitua um método de análise bastante importante, ela tem como desvantagem a necessidade de construir o espaço de estados completo do sistema, o que pode levar ao problema da explosão de estados. Bastante progresso tem sido feito para lidar com esta dificuldade, e diversas técnicas têm aumentado o tamanho dos sistemas que podem ser verificados. Outras abordagens propõem aproximar o espaço de estados, mas neste caso não é possível a verificação de propriedades arbitrárias. Além da verificação de modelos, a prova de teoremas constitui outra técnica consolidada para verificação formal. Nesta técnica tanto o sistema quanto suas propriedades são expressas em alguma lógica matemática. O processo de prova consiste em encontrar uma prova a partir dos axiomas e lemas intermediários do sistema. Cada técnica tem argumentos pró e contra o seu uso, mas é possível dizer que a verificação de modelos e a prova de teoremas são complementares. A maioria das abordagens utilizam verificadores de modelos para analisar propriedades de computações, isto é, sobre a seqüência de passos de um sistema. Propriedades sobre estados alcançáveis só são verificadas de forma restrita. O objetivo deste trabalho é prover uma abordagem para a prova de propriedades de grafos alcançáveis de uma gramática de grafos através da técnica de prova de teoremas. Propõe-se uma tradução (da abordagem Single-Pushout) de gramática de grafos para uma abordagem lógica e relacional, a qual permite a aplicação de indução matemática para análise de sistemas com espaço de estados infinito. Definiu-se gramática de grafos utilizando estruturas relacionais e aplicações de regras com linguagens lógicas. Inicialmente considerou-se o caso de grafos (tipados) simples, e então se estendeu a abordagem para grafos com atributos e gramáticas com condições negativas de aplicação. Além disso, baseado nesta abordagem, foram estabelecidos padrões para a definição, codificação e reuso de especificações de propriedades. O sistema de padrões tem o objetivo de auxiliar e simplificar a tarefa de especificar requisitos de forma precisa. Finalmente, propõe-se implementar definições relacionais de gramática de grafos em estruturas de event-B, de forma que seja possível utilizar os provadores disponíveis para event-B para demonstrar propriedades de gramática de grafos.Graph grammars are a formal language well-suited to applications in which states have a complex topology (involving not only many types of elements, but also different types of relations between them) and in which behaviour is essentially data-driven, that is, events are triggered basically by particular configurations of the state. Many reactive systems are examples of this class of applications, such as protocols for distributed and mobile systems, simulation of biological systems, and many others. The verification of graph grammar models through model-checking is currently supported by various approaches. Although model-checking is an important analysis method, it has as disadvantage the need to build the complete state space, which can lead to the state explosion problem. Much progress has been made to deal with this difficulty, and many techniques have increased the size of the systems that may be verified. Other approaches propose to over- and/or under-approximate the state-space, but in this case it is not possible to check arbitrary properties. Besides model checking, theorem proving is another wellestablished approach for verification. Theorem proving is a technique where both the system and its desired properties are expressed as formulas in some mathematical logic. A logical description defines the system, establishing a set of axioms and inference rules. The process of verification consists of finding a proof of the required property from the axioms or intermediary lemmas of the system. Each verification technique has arguments for and against its use, but we can say that model-checking and theorem proving are complementary. Most of the existing approaches use model checkers to analyse properties of computations, that is, properties over the sequences of steps a system may engage in. Properties about reachable states are handled, if at all possible, only in very restricted ways. In this work, our main aim is to provide a means to prove properties of reachable graphs of graph grammar models using the theorem proving technique. We propose an encoding of (the Single-Pushout approach of) graph grammar specifications into a relational and logical approach which allows the application of the mathematical induction technique to analyse systems with infinite state-spaces. We have defined graph grammars using relational structures and used logical languages to model rule applications. We first consider the case of simple (typed) graphs, and then we extend the approach to the non-trivial case of attributed-graphs and grammars with negative application conditions. Besides that, based on this relational encoding, we establish patterns for the presentation, codification and reuse of property specifications. The pattern has the goal of helping and simplifying the task of stating precise requirements to be verified. Finally, we propose to implement relational definitions of graph grammars in event-B structures, such that it is possible to use the event-B provers to demonstrate properties of a graph grammar.
19
Rawlani, Praynaa. "Graph analytics on relational databases." Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/100670.
Full textAbstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 99-100).
Graph analytics has become increasing popular in the recent years. Conventionally, data is stored in relational databases that have been refined over decades, resulting in highly optimized data processing engines. However, the awkwardness of expressing iterative queries in SQL makes the relational query-processing model inadequate for graph analytics, leading to many alternative solutions. Our research explores the possibility of combining a more natural query model with relational databases for graph analytics. In particular, we bring together a graph-natural vertex-centric query interface to highly optimized column-oriented relational databases, thus providing the efficiency of relational engines and ease-of-use of new graph systems. Throughout the thesis, we used stochastic gradient descent, a loss-minimization algorithm applied in many machine learning and graph analytics queries, as the example iterative algorithm. We implemented two different approaches for emulating a vertex-centric interface on a leading column-oriented database, Vertica: disk-based and main-memory based. The disk-based solution stores data for each iteration in relational tables and allows for interleaving SQL queries with graph algorithms. The main-memory approach stores data in memory, allowing faster updates. We applied optimizations to both implementations, which included refining logical and physical query plans, applying algorithm-level improvements and performing system-specific optimizations. The experiments and results show that the two implementations provide reasonable performance in comparison with popular graph processing systems. We present a detailed cost analysis of the two implementations and study the effect of each individual optimization on the query performance.
by Praynaa Rawlani.
M. Eng.
20
Long, Yangjing. "Graph Relations and Constrained Homomorphism Partial Orders." Doctoral thesis, Universitätsbibliothek Leipzig, 2014. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-154281.
Full textAbstract:
We consider constrained variants of graph homomorphisms such as embeddings, monomorphisms, full homomorphisms,
surjective homomorpshims, and locally constrained homomorphisms.
We also introduce a new variation on this theme which derives from
relations between graphs and is related to multihomomorphisms.
This gives a generalization of surjective homomorphisms and naturally leads to notions of R-retractions, R-cores, and R-cocores of graphs. Both \\mbox{R-cores} and R-cocores of graphs are unique up to isomorphism and can be computed in polynomial time.
The theory of the graph homomorphism order is well developed, and from it we consider analogous notions defined for orders induced by constrained homomorphisms.
We identify corresponding cores, prove or disprove universality, characterize gaps and dualities. We give a new and significantly easier proof of the universality of the homomorphism order by showing that even the class of oriented cycles is universal. We provide a systematic approach to simplify the proofs of several earlier results in this area.
We explore in greater detail locally injective homomorphisms on connected graphs, characterize gaps and show universality. We also prove that for every $d\\geq 3$ the homomorphism order on the class of line graphs of graphs with maximum degree $d$ is universal.
21
Edström, August, and Johan Isaksson. "Inferring Dataset Relations using Knowledge Graph Metadata." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-414918.
Full textAbstract:
The web site dataportalen.se aims to increase the availability of Swedish open datasets. This is achieved by collecting metadata about the open datasets provided by Swedish organizations. At the time of writing, metadata from more than two thousand datasets reside in the portal, and this number is set to increase. As the number of datasets increases, browsing for relevant information becomes increasingly difficult and time-consuming. The web site supports searching using text and then filtering the results by theme, organization, file format och license. We believe that there exists potential to connect the datasets, thus making it easier to find a dataset of interest. The idea is to find common denominators in the metadata of the datasets. Furthermore, as no user data is available, the datasets had to be connected based solely on the metadata. The datasets are annotated with metadata, such as title,description, keywords, themes. By comparing metadata from different datasets, a measure of similarity could be computed. This measure can then be used to find the most relevant datasets for a specific dataset.The achieved results suggests that it is indeed possible to find similar datasets by only analyzing the metadata. By exploring various methods, we found it to be the case that text data holds useful information that can be used to find relations between datasets. Using a related workas a benchmark, we found that our results are as good if not better. Furthermore, the approach taken in this project is quite general, and should theoretically be applicable in other scenarios where textual data is available.Webbplatsen dataportalen.se syftar till att öka tillgängligheten av svensk öppna data. Detta görs genom att samla in metadata om de öppna datamängderna som tillhandahålls av svenska organisationer. I skrivande stund finns metadata från mer än två tusendatamängder i portalen, och detta antal kommer att öka. När antalet datamängder ökar blir genomsökandet av relevant information allt svårare och mer tidskrävande. För närvarande är det möjligt att genomsöka datamängderna med hjälp av sökning med text och sedan filtrering med tema, organisation, filformat eller licens. Vi tror att det finns mer potential att koppla samman datamängderna, vilket skulle göra det enklare att hitta datamängder av intresse. Idén är att hitta gemensamma nämnare i metadatat för datamängderna. Eftersom det inte finns någon användardata kommervi att undersöka i vilken utsträckning denna idé kan realiseras. Datamängderna kommenteras med metadata som titel, beskrivning, nyckelord, och tema. Genom att jämföra metadata från olika datamängder kan ett mått på likhet beräknas. Detta mått kan sedan användas för att hitta de mest relevanta datamängderna för en specifik datamängd. Resultaten av analysen av metadata är att liknande datamängder kan hittas. Genom att utforska olika metoder fann vi att textdata inneåaller användbar information som kan användas för att hitta relationer mellan datamängder. Genom att använda ett relaterat arbete som riktmärke fann vi att våra resultat är lika bra, om inte bättre. Resultaten visar att relaterade datamängder kan hittas med bara textdata, och vi anser att den identifierade metoden är tillräckligt generell för att ha potential att kunna användas i liknande problem där textdata är tillgänglig.
22
García, Durán Alberto. "Learning representations in multi-relational graphs : algorithms and applications." Thesis, Compiègne, 2016. http://www.theses.fr/2016COMP2271/document.
Full textAbstract:
Internet offre une énorme quantité d’informations à portée de main et dans une telle variété de sujets, que tout le monde est en mesure d’accéder à une énorme variété de connaissances. Une telle grande quantité d’information pourrait apporter un saut en avant dans de nombreux domaines (moteurs de recherche, réponses aux questions, tâches NLP liées) si elle est bien utilisée. De cette façon, un enjeu crucial de la communauté d’intelligence artificielle a été de recueillir, d’organiser et de faire un usage intelligent de cette quantité croissante de connaissances disponibles. Heureusement, depuis un certain temps déjà des efforts importants ont été faits dans la collecte et l’organisation des connaissances, et beaucoup d’informations structurées peuvent être trouvées dans des dépôts appelés Bases des Connaissances (BCs). Freebase, Entity Graph Facebook ou Knowledge Graph de Google sont de bons exemples de BCs. Un grand problème des BCs c’est qu’ils sont loin d’êtres complets. Par exemple, dans Freebase seulement environ 30% des gens ont des informations sur leur nationalité. Cette thèse présente plusieurs méthodes pour ajouter de nouveaux liens entre les entités existantes de la BC basée sur l’apprentissage des représentations qui optimisent une fonction d’énergie définie. Ces modèles peuvent également être utilisés pour attribuer des probabilités à triples extraites du Web. On propose également une nouvelle application pour faire usage de cette information structurée pour générer des informations non structurées (spécifiquement des questions en langage naturel). On pense par rapport à ce problème comme un modèle de traduction automatique, où on n’a pas de langage correct comme entrée, mais un langage structuré. Nous adaptons le RNN codeur-décodeur à ces paramètres pour rendre possible cette traductionInternet provides a huge amount of information at hand in such a variety of topics, that now everyone is able to access to any kind of knowledge. Such a big quantity of information could bring a leap forward in many areas if used properly. This way, a crucial challenge of the Artificial Intelligence community has been to gather, organize and make intelligent use of this growing amount of available knowledge. Fortunately, important efforts have been made in gathering and organizing knowledge for some time now, and a lot of structured information can be found in repositories called Knowledge Bases (KBs). A main issue with KBs is that they are far from being complete. This thesis proposes several methods to add new links between the existing entities of the KB based on the learning of representations that optimize some defined energy function. We also propose a novel application to make use of this structured information to generate questions in natural language
23
Majid, Nihad Abdel Jalil. "Morphologie de certaines relations binaires." Aix-Marseille 1, 1991. http://www.theses.fr/1991AIX11342.
Full textAbstract:
La these porte sur la morphologie des relations binaires finies. A savoir: determiner la forme generale d'une relation sachant qu'on interdit a certaines configurations d'apparaitre dans la relation. Les resultats concernent les relations (1)-monomorphes et les tournois. La reconstructibilite de ces relations est ensuite etudiee
24
Oliveira, Péricles Silva de, and 21-98498-9543. "Generation and Ranking of Candidate Networks of Relations for Keyword Search over Relational Databases." Universidade Federal do Amazonas, 2017. http://tede.ufam.edu.br/handle/tede/5806.
Full textAbstract:
Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-08-22T19:40:10Z
No. of bitstreams: 2
Tese - Péricles Silva de Oliveira.pdf: 1875380 bytes, checksum: 014ba89b7fe1929a1461c9d8d3959416 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-08-22T19:40:26Z (GMT) No. of bitstreams: 2 Tese - Péricles Silva de Oliveira.pdf: 1875380 bytes, checksum: 014ba89b7fe1929a1461c9d8d3959416 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-08-22T19:40:44Z (GMT) No. of bitstreams: 2 Tese - Péricles Silva de Oliveira.pdf: 1875380 bytes, checksum: 014ba89b7fe1929a1461c9d8d3959416 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Made available in DSpace on 2017-08-22T19:40:44Z (GMT). No. of bitstreams: 2 Tese - Péricles Silva de Oliveira.pdf: 1875380 bytes, checksum: 014ba89b7fe1929a1461c9d8d3959416 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-04-28
Several systems proposed for processing keyword queries over relational databases rely on the generation and evaluation of Candidate Networks (CNs), i.e., networks of joined database relations that, when processed as SQL queries, provide a relevant answer to the input keyword query. Although the evaluation of CNs has been extensively addressed in the literature, problems related to efficiently generating meaningful CNs have received much less attention. To generate useful CNs is necessary to automatically locating, given a handful of keywords, relations in the database that may contain relevant pieces of information, and determining suitable ways of joining these relations to satisfy the implicit information need expressed by a user when formulating her query. In this thesis, we present two main contributions related to the processing of Candidate Networks. As our first contribution, we present a novel approach for generating CNs, in which possible matchings of the query in database are efficiently enumerated at first. These query matches are then used to guide the CN generation process, avoiding the exhaustive search procedure used by current state-of-art approaches. We show that our approach allows the generation of a compact set of CNs that leads to superior quality answers, and that demands less resources in terms of processing time and memory. As our second contribution, we initially argue that the number of possible Candidate Networks that can be generated by any algorithm is usually very high, but that, in fact, only very few of them produce answers relevant to the user and are indeed worth processing. Thus, there is no point in wasting resources processing useless CNs. Then, based on such an argument, we present an algorithm for ranking CNs, based on their probability of producing relevant answers to the user. This relevance is estimated based on the current state of the underlying database using a probabilistic Bayesian model we have developed. By doing so we are able do discard a large number of CNs, ultimately leading to better results in terms of quality and performance. Our claims and proposals are supported by a comprehensive set of experiments we carried out using several query sets and datasets used in previous related work and whose results we report and analyse here.
Sem resumo.
25
El, Abri Marwa. "Probabilistic relational models learning from graph databases." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4019/document.
Full textAbstract:
Historiquement, les Modèles Graphiques Probabilistes (PGMs) sont une solution d’apprentissage à partir des données incertaines et plates, appelées aussi données propositionnelles ou représentations attribut-valeur. Au début des années 2000, un grand intérêt a été adressé au traitement des données relationnelles présentant un grand nombre d’objets participant à des différentes relations. Les Modèles Probabilistes Relationnels (PRMs) présentent une extension des PGMs pour le contexte relationnel. Avec l’évolution rapide issue de l’internet, des innovations technologiques et des applications web, les données sont devenues de plus en plus variées et complexes. D’où l’essor du Big Data. Plusieurs types de bases de données ont été créés pour s’adapter aux nouvelles caractéristiques des données, dont les plus utilisés sont les bases de données graphe. Toutefois, tous les travaux d’apprentissage des PRMs sont consacrés à apprendre à partir des données bien structurées et stockées dans des bases de données relationnelles. Les bases de données graphe sont non structurées et n’obéissent pas à un schéma bien défini. Les arcs entre les noeuds peuvent avoir des différentes signatures. En effet, les relations qui ne correspondent pas à un modèle ER peuvent exister dans l'instance de base de données. Ces relations sont considérées comme des exceptions. Dans ce travail de thèse, nous nous intéressons à ce type de bases de données. Nous étudions aussi deux types de PRMs à savoir, Direct Acyclic Probabilistic Entity Relationship (DAPER) et chaines de markov logiques (MLNs). Nous proposons deux contributions majeures. Premièrement, Une approche d’apprentissage des DAPERs à partir des bases de données graphe partiellement structurées. Une deuxième approche consiste à exploiter la logique de premier ordre pour apprendre les DAPERs en utilisant les MLNs pour prendre en considération les exceptions qui peuvent parvenir lors de l’apprentissage. Nous menons une étude expérimentale permettant de comparer nos méthodes proposées avec les approches déjà existantesHistorically, Probabilistic Graphical Models (PGMs) are a solution for learning from uncertain and flat data, also called propositional data or attributevalue representations. In the early 2000s, great interest was addressed to the processing of relational data which includes a large number of objects participating in different relations. Probabilistic Relational Models (PRMs) present an extension of PGMs to the relational context. With the rise of the internet, numerous technological innovations and web applications are driving the dramatic increase of various and complex data. Consequently, Big Data has emerged. Several types of data stores have been created to manage this new data, including the graph databases. Recently there has been an increasing interest in graph databases to model objects and interactions. However, all PRMs structure learning use wellstructured data that are stored in relational databases. Graph databases are unstructured and schema-free data stores. Edges between nodes can have various signatures. Since, relationships that do not correspond to an ER model could be depicted in the database instance. These relationships are considered as exceptions. In this thesis, we are interested by this type of data stores. Also, we study two kinds of PRMs namely, Direct Acyclic Probabilistic Entity Relationship (DAPER) and Markov Logic Networks (MLNs). We propose two significant contributions. First, an approach to learn DAPERs from partially structured graph databases. A second approach consists to benefit from first-order logic to learn DAPERs using MLN framework to take into account the exceptions that are dropped during DAPER learning. We are conducting experimental studies to compare our proposed methods with existing approaches
26
Dube, Matthew P. "An Embedding Graph for 9-Intersection Topological Spatial Relations." Fogler Library, University of Maine, 2009. http://www.library.umaine.edu/theses/pdf/DubeMP2009.pdf.
Full text
27
Richer, Émilie. "Relative hyperbolicity of graphs of free groups with cyclic edge groups." Thesis, McGill University, 2006. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=101170.
Full textAbstract:
We prove that any finitely generated group which splits as a graph of free groups with cyclic edge groups is hyperbolic relative to certain finitely generated subgroups, known as the peripheral subgroups. Each peripheral subgroup splits as a graph of cyclic groups. Any graph of free groups with cyclic edge groups is the fundamental group of a graph of spaces X where vertex spaces are graphs, edge spaces are cylinders and attaching maps are immersions. We approach our theorem geometrically using this graph of spaces.We apply a "coning-off" process to peripheral subgroups of the universal cover X̃ → X obtaining a space Cone(X̃) in order to prove that Cone (X̃) has a linear isoperimetric function and hence satisfies weak relative hyperbolicity with respect to peripheral subgroups.
We then use a recent characterisation of relative hyperbolicity presented by D.V. Osin to serve as a bridge between our linear isoperimetric function for Cone(X̃) and a complete proof of relative hyperbolicity. This characterisation allows us to utilise geometric properties of X in order to show that pi1( X) has a linear relative isoperimetric function. This property is known to be equivalent to relative hyperbolicity.
Keywords. Relative hyperbolicity; Graphs of free groups with cyclic edge groups, Relative isoperimetric function, Weak relative hyperbolicity.
28
Mapfumo, Emmanuel. "Grapevine root growth in relation to water uptake from soil." Title page, contents and summary only, 1994. http://web4.library.adelaide.edu.au/theses/09A/09am297.pdf.
Full text
29
Thomassé, Stéphan. "Catégoricité, belordre et décomposabilité des relations." Lyon 1, 1995. http://www.theses.fr/1995LYO10166.
Full textAbstract:
Cette these presente differents aspects de l'abritement entre relations. Lorsque r est une relation denombrable, nous y prouvons (et ce fil conducteur traverse les differentes notions abordees) la chaine d'implications suivante: les indecomposables abrites dans r sont de taille au plus n (2 pour les serie parallele ou les chaines). La classe des colorations de r en trois couleurs est belordonnee par abritement (laver le prouve pour les chaines et corominas pour les arbres. ) l'ensemble des parties de r qui abritent r est comaigre. L'ensemble des parties de r qui abritent r est de mesure non nulle. Ces proprietes sont ordonnees de la plus forte a la plus faible et ne sont pas equivalentes. Toutefois, et c'est l'objet du dernier chapitre, ces differentes notions se basent sur les extensions finies d'isomorphismes locaux. En effet, etiqueter un graphe en 2 couleurs peut representer l'ajout d'un sommet, tout indecomposable inclus dans un autre indecomposable peut s'etendre a toute partie finie en un indecomposable (ille), et enfin les preuves de categoricite et de mesurabilite se basent sur l'operation a de lusin appliquee a l'arbre des isomorphismes locaux. La notion d'alpha-morphisme de fraisse pourrait permettre de traduire ces differentes proprietes. Dans cette optique, nous montrons une facon de l'utiliser pour prouver le theoreme d'impartiabilite de pouzet qui jusqu'alors necessitait l'emploi de resultats topologiques
30
Chao, Tian-Jy. "Estimating temporary file sizes for query graphs in distributed relational database systems." Thesis, Virginia Polytechnic Institute and State University, 1985. http://hdl.handle.net/10919/90921.
Full textAbstract:
This thesis implements a part of the front-end software, the Optimizer, of the distributed database system being developed at Virginia Tech. The Optimizer generates a strategy for optimal query processing, and it presents and analyzes a given query by means of query trees and query graphs. This thesis develops PASCAL procedures that implement quantitative and qualitative rules to select query graphs requiring minimum communication costs. To develop the rules, the size of the temporary files generated after performing each required operation is estimated. The focus of this work is on the implementation of a new technique for estimating the temporary file sizes. Detailed discussion of this implementation is presented and illustrated with a complete example, followed by a comparison with one of the existing methods proposed by Dwyer.M.S.
31
Rahman, Md Rashedur. "Knowledge Base Population based on Entity Graph Analysis." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS092/document.
Full textAbstract:
Le peuplement de base de connaissance (KBP) est une tâche importante qui présente de nombreux défis pour le traitement automatique des langues. L'objectif de cette tâche est d'extraire des connaissances de textes et de les structurer afin de compléter une base de connaissances. Nous nous sommes intéressés à la reconnaissance de relations entre entités. L'extraction de relations (RE) entre une paire de mentions d'entités est une tâche difficile en particulier pour les relations en domaine ouvert. Généralement, ces relations sont extraites en fonction des informations lexicales et syntaxiques au niveau de la phrase. Cependant, l'exploitation d'informations globales sur les entités n'a pas encore été explorée. Nous proposons d'extraire un graphe d'entités du corpus global et de calculer des caractéristiques sur ce graphe afin de capturer des indices des relations entre paires d'entités. Pour évaluer la pertinence des fonctionnalités proposées, nous les avons testées sur une tâche de validation de relation dont le but est de décider l'exactitude de relations extraites par différents systèmes. Les résultats expérimentaux montrent que les caractéristiques proposées conduisent à améliorer les résultats de l'état de l'artKnowledge Base Population (KBP) is an important and challenging task specially when it has to be done automatically. The objective of KBP task is to make a collection of facts of the world. A Knowledge Base (KB) contains different entities, relationships among them and various properties of the entities. Relation extraction (RE) between a pair of entity mentions from text plays a vital role in KBP task. RE is also a challenging task specially for open domain relations. Generally, relations are extracted based on the lexical and syntactical information at the sentence level. However, global information about known entities has not been explored yet for RE task. We propose to extract a graph of entities from the overall corpus and to compute features on this graph that are able to capture some evidence of holding relationships between a pair of entities. In order to evaluate the relevance of the proposed features, we tested them on a task of relation validation which examines the correctness of relations that are extracted by different RE systems. Experimental results show that the proposed features lead to outperforming the state-of-the-art system
32
Ostermeier, Lydia. "(Relaxed) Product Structures of Graphs and Hypergraphs." Doctoral thesis, Universitätsbibliothek Leipzig, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-167934.
Full textAbstract:
In this thesis, we investigate graphs and hypergraphs that have (relaxed) product structures.
In the class of graphs, we discuss in detail \\emph{RSP-relations}, a relaxation of relations fulfilling the square property and therefore of the product relation $\\sigma$, that identifies the copies of the prime factors of a graph w.r.t. the Cartesian product. For $K_{2,3}$-free graphs finest RSP-relations can be computed in polynomial-time. In general, however, they are not unique and their number may even grow exponentially. Explicit constructions of such relations in complete and complete bipartite graphs are given.
Furthermore, we establish the close connection of (\\emph{well-behaved}) RSP-relations to \\mbox{(quasi-)covers} of graphs and equitable partitions. Thereby, we characterize the existence of non-trivial RSP-relations by means of the existence of spanning subgraphs that yield quasi-covers of the graph under investigation.
We show, how equitable partitions on the vertex set of a graph $G$ arise in a natural way from well-behaved RSP-relations on $E(G)$.
These partitions in turn give rise to quotient graphs that have rich product structure even if $G$ itself is prime. This product structure of the quotient graph is still retained even for RSP-relations that are not well-behaved. Furthermore, we will see that a (finest) RSP-relation of a product graph can be obtained easily from (finest) RSP-relations on the prime factors w.r.t. certain products and in what manner the quotient graphs of the product w.r.t. such an RSP-relation result from the quotient graphs of the factors and the respective product.
In addition, we examine relations on the edge sets of \\emph{hyper}graphs that satisfy the grid property, the hypergraph analog of the square property. We introduce the \\emph{strong} and the \\emph{relaxed} grid property as variations of the grid property, the latter generalizing the relaxed square property. We thereby show, that many, although not all results for graphs and the (relaxed) square property can be transferred to hypergraphs. Similar to the graph case,
any equivalence relation $R$ on the edge set of a hypergraph $H$ that satisfies the relaxed grid property induces a partition of the vertex set of $H$ which in turn determines quotient hypergraphs that have non-trivial product structures. Besides, we introduce the notion of \\emph{(Cartesian) hypergraph bundles}, the analog of (Cartesian) graph bundles and point out the connection between the grid property and hypergraph bundles.
Finally, we show that every connected thin hypergraph $H$ has a unique prime factorization with respect to the normal and strong (hypergraph) product. Both products coincide with the usual strong \\emph{graph} product whenever $H$ is a graph. We introduce the notion of the Cartesian skeleton of hypergraphs as a natural generalization of the Cartesian skeleton of graphs and prove that it is uniquely defined for thin hypergraphs. Moreover, we show that the Cartesian skeleton of thin hypergraphs and its PFD w.r.t. the strong and the normal product can be computed in polynomial time.
33
Muller, Christophe. "Relations structure-activité pour le métabolisme et la toxicité." Phd thesis, Université de Strasbourg, 2013. http://tel.archives-ouvertes.fr/tel-00834868.
Full textAbstract:
Prédire à l'avance quels composés seront toxiques chez l'homme ou non représente un réel challenge dans le monde pharmaceutique. En effet, les mécanismes à l'origine de la toxicité ne sont pas toujours bien connus, et à cela s'ajoute le fait qu'un composé peut devenir néfaste seulement après qu'il ait été métabolisé. Nous proposons ici une approche originale utilisant les graphes condensés de réactions afin de modéliser les réactions métaboliques et prédire le devenir des xénobiotiques dans l'organisme humain. Différentes formes de toxicité sont aussi prédites : la mutagénicité et l'hépatotoxicité. Pour cette seconde toxicité, l'approche utilisée est la première à notre connaissance à prédire avec succès les molécules toxiques décrites par des données autres que résultant d'observations in vivo.
34
Soussi, Rania. "Querying and extracting heterogeneous graphs from structured data and unstrutured content." Phd thesis, Ecole Centrale Paris, 2012. http://tel.archives-ouvertes.fr/tel-00740663.
Full textAbstract:
The present work introduces a set of solutions to extract graphs from enterprise data and facilitate the process of information search on these graphs. First of all we have defined a new graph model called the SPIDER-Graph, which models complex objects and permits to define heterogeneous graphs. Furthermore, we have developed a set of algorithms to extract the content of a database from an enterprise and to represent it in this new model. This latter representation allows us to discover relations that exist in the data but are hidden due to their poor compatibility with the classical relational model. Moreover, in order to unify the representation of all the data of the enterprise, we have developed a second approach which extracts from unstructured data an enterprise's ontology containing the most important concepts and relations that can be found in a given enterprise. Having extracted the graphs from the relational databases and documents using the enterprise ontology, we propose an approach which allows the users to extract an interaction graph between a set of chosen enterprise objects. This approach is based on a set of relations patterns extracted from the graph and the enterprise ontology concepts and relations. Finally, information retrieval is facilitated using a new visual graph query language called GraphVQL, which allows users to query graphs by drawing a pattern visually for the query. This language covers different query types from the simple selection and aggregation queries to social network analysis queries.
35
Joret, Gwenaël. "Entropy and stability in graphs." Doctoral thesis, Universite Libre de Bruxelles, 2007. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210605.
Full textAbstract:
Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité (défini comme la plus grande taille d'un stable), et les stables se classent certainement parmi les structures les plus simples et fondamentales en théorie des graphes.La thèse est divisée en deux parties, toutes deux liées à la notion de stables dans un graphe. Dans la première partie, nous étudions un problème de coloration de graphes, c'est à dire de partition en stables, où le but est de minimiser l'entropie de la partition. C'est une variante du problème classique de minimiser le nombre de couleurs utilisées. Nous considérons aussi une généralisation du problème aux couvertures d'ensembles. Ces deux problèmes sont appelés respectivement minimum entropy coloring et minimum entropy set cover, et sont motivés par diverses applications en théorie de l'information et en bioinformatique. Nous obtenons entre autres une caractérisation précise de la complexité de minimum entropy set cover :le problème peut être approximé à une constante lg e (environ 1.44) près, et il est NP-difficile de faire strictement mieux. Des résultats analogues sont prouvés concernant la complexité de minimum entropy coloring.
Dans la deuxième partie de la thèse, nous considérons les graphes dont le nombre de stabilité augmente dès qu'une arête est enlevée. Ces graphes sont dit être "alpha-critiques", et jouent un rôle important dans de nombreux domaines, comme la théorie extrémale des graphes ou la combinatoire polyédrique. Nous revisitons d'une part la théorie des graphes alpha-critiques, donnant à cette occasion de nouvelles démonstrations plus simples pour certains théorèmes centraux. D'autre part, nous étudions certaines facettes du polytope des ordres totaux qui peuvent être vues comme une généralisation de la notion de graphe alpha-critique. Nous étendons de nombreux résultats de la théorie des graphes alpha-critiques à cette famille de facettes.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
36
Kitanov, Ksenija [Verfasser], Peter [Akademischer Betreuer] Fiebig, and Stéphane [Gutachter] Gaussent. "Higher-order congruence relations on affine moment graphs / Ksenija Kitanov ; Gutachter: Stéphane Gaussent ; Peter Fiebig." Erlangen : Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), 2018. http://d-nb.info/1154595234/34.
Full text
37
Casellato, Claudio <1997>. "International Trade Modelling with Temporal Relational Graph Neural Networks." Master's Degree Thesis, Università Ca' Foscari Venezia, 2022. http://hdl.handle.net/10579/21414.
Full textAbstract:
Graph Neural Networks (GNN) are a powerful technique to model data on graph domains with neural networks. They are mainly used on static networks where nodes and edges do not change over time and only one type of edge is present between two nodes. To overcome this issue new models extended the GNN model to incorporate temporal data and relational data. The resulting model is defined as a Temporal Relational Graph Neural Networks (TRGNN). We use this novel technique to model the trade evolution of the International Trade Network (ITN) for different products. The nodes in the network represent the countries, encoded as a feature vector. The products are encoded as feature vectors and the edges represent the trade relations for each product between two countries, encoded as a relational feature vector. We then analyze the topological, statistical properties and predictive capabilities of the developed model. We then analyze and visualize the evolution of the feature embeddings of countries and relations between countries. We then evaluate the predictive performance on link prediction and reconstruction capabilities.
38
Zhou, Xinwei. "Reachability relations in selective regression testing." Thesis, London South Bank University, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.265281.
Full text
39
Yao, Liangjin. "Decompositions and representations of monotone operators with linear graphs." Thesis, University of British Columbia, 2007. http://hdl.handle.net/2429/2807.
Full textAbstract:
We consider the decomposition of a maximal monotone operator into the
sum of an antisymmetric operator and the subdifferential of a proper lower
semicontinuous convex function. This is a variant of the well-known decomposition of a matrix into its symmetric and antisymmetric part. We analyze in detail the case when the graph of the operator is a linear subspace. Equivalent conditions of monotonicity are also provided.
We obtain several new results on auto-conjugate representations including an explicit formula that is built upon the proximal average of the associated Fitzpatrick function and its Fenchel conjugate. These results are
new and they both extend and complement recent work by Penot, Simons
and Zălinescu. A nonlinear example shows the importance of the linearity
assumption. Finally, we consider the problem of computing the Fitzpatrick
function of the sum, generalizing a recent result by Bauschke, Borwein and
Wang on matrices to linear relations.
40
Viégas, Rafael Pedroni. "Aplicação de conceitos de bancos de dados de grafos e relacional na criação de proposta e análise comparativa de abordagens para armazenamento de processos." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2018. http://hdl.handle.net/10183/180130.
Full textAbstract:
Em busca da documentação e otimização de seus processos, a área de Business Process Management (BPM) vem cada vez mais atraindo o interesse do meio empresarial, por ser um importante método no auxílio ao ganho de resultados, como redução de custos e aumento de produtividade. Modelar processos, entretanto, não basta. É preciso que se atente para métodos eficientes de armazená-los, permitindo que as informações sejam manipuladas e utilizadas de maneira prática e inteligente. A presente dissertação propõe duas abordagens para armazenamento de modelos de processo, uma em bancos de dados relacionais e outra em bancos de dados orientados a grafos, comparando-os através de aspectos como desempenho na execução das operações e proximidade da abordagem de cada um deles com os modelos de processos. Enquanto os bancos de dados relacionais são mais populares, sendo utilizados na maior parte das aplicações atuais, os bancos de dados orientados a grafos possuem propriedades e representação gráfica semelhantes aos modelos de processos. Foram realizados testes que visam analisar o desempenho de ambas as abordagens, além da facilidade dos usuários em interagir com os modelos propostos. Os resultados deste estudo podem ser utilizados para a criação de repositórios que compartilhem processos de maneira eficiente, bem como incentivar o estudo de novas maneiras para o armazenamento de processos.Business Process Management (BPM) area has been increasingly attracted the interest of the business community because users are looking for documentation and optimization. These documents can be an important method in helping to gain results such as reduced costs and increased productivity. However, to model processes is not enough. It is necessary to pay attention to efficient storage methods, allowing information to be handled and used in a practical and intelligent way. The present article compares the use of relational databases and graph databases, considering aspects such as performance in the execution of operations and proximity of the approach of each of them with the process models. While relational databases are more popular, being used in most of the current applications, graph databases have properties and graphical representations similar to process models. The results of this study can be used to create repositories which can both share process efficiently, and encourage the study of new ways of storing processes.
41
Knight, Daniel William. "Reactor behavior and its relation to chemical reaction network structure." The Ohio State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=osu1438274630.
Full text
42
Caboche, Gilles. "Relation structure-dimensions des grains monocristallins : cas d'un matériau polaire, BaTi03." Dijon, 1991. http://www.theses.fr/1991DIJOS062.
Full textAbstract:
Les dimensions des grains de BaTiO#3 ont une influence sur les propriétés structurales, sur les transitions de phases, sur la réactivité de la matière pulvérulente et sur les propriétés électriques des céramiques issues de ces poudres. L’étude de ces influences implique la préparation de poudres à grains fins, la connaissance de leurs propriétés et la mise en œuvre de ces poudres fines. Des études antérieures, effectuées dans notre laboratoire, ont mis en évidence par diffraction des rayons X un défaut particulier lié aux dimensions des grains de BaTiO#3; il existerait une distribution des valeurs des paramètres de maille cristalline au sein des échantillons de BaTiO#3. La présente étude a eu pour but de localiser cette variation des paramètres cristallins qui, selon toute vraisemblance, serait située à l'intérieur des grains eux-mêmes. L’utilisation d'une large palette d'appareils de diffraction s'est révélée indispensable. Elle a permis de dégager les performances et les limites des instruments utilises sur le plan de la résolution, de la définition et de la statistique et d'apporter des éléments de réponse à la question posée. Une modélisation des profils des raies de diffraction est présentée; elle a permis de mettre en évidence une relation de cohérence, sur le plan de la diffraction, entre les domaines à 90° à l'intérieur des cristallites de ce matériau ferroélectrique. De plus, des interactions, lors de la mise en contact de la poudre avec le liant ou avec le solvant et également lors du passage, ont été mises en évidence par ces techniques de diffraction. Enfin, au niveau de la mise en œuvre de ces poudres fines, une ouverture a été entreprise vers la seule technique capable, aujourd'hui, de réussir à préserver les propriétés des grains fins, le pressage isostatique à chaud.
43
Binko, Petr. "Moderní plánovací algoritmy." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2010. http://www.nusl.cz/ntk/nusl-237146.
Full textAbstract:
This work describes graphplan, satplan and real-time adaptive A* planning algorithms. Through implementation of these algorithms, functionality and assumed attributes (real-time calculation, parallelism) are tested. These tests take place in nontrivial domains. Graphplan and satplan algorithms were tested in block-world, tire-world and bulldozer domains. Results of these tests were compared and displayed in graphs. Real-time adaptive A* algorithm was tested in tire-world domain. Results of these tests were compared with classic A* algorithm. Advantages and disadvantages of these algorithms are also described in this work.
44
Nguyen, Thi Kim Ngan. "Generalizing association rules in n-ary relations : application to dynamic graph analysis." Phd thesis, INSA de Lyon, 2012. http://tel.archives-ouvertes.fr/tel-00995132.
Full textAbstract:
Pattern discovery in large binary relations has been extensively studied. An emblematic success in this area concerns frequent itemset mining and its post-processing that derives association rules. In this case, we mine binary relations that encode whether some properties are satisfied or not by some objects. It is however clear that many datasets correspond to n-ary relations where n > 2. For example, adding spatial and/or temporal dimensions (location and/or time when the properties are satisfied by the objects) leads to the 4-ary relation Objects x Properties x Places x Times. Therefore, we study the generalization of association rule mining within arbitrary n-ary relations: the datasets are now Boolean tensors and not only Boolean matrices. Unlike standard rules that involve subsets of only one domain of the relation, in our setting, the head and the body of a rule can include arbitrary subsets of some selected domains. A significant contribution of this thesis concerns the design of interestingness measures for such generalized rules: besides a frequency measures, two different views on rule confidence are considered. The concept of non-redundant rules and the efficient extraction of the non-redundant rules satisfying the minimal frequency and minimal confidence constraints are also studied. To increase the subjective interestingness of rules, we then introduce disjunctions in their heads. It requires to redefine the interestingness measures again and to revisit the redundancy issues. Finally, we apply our new rule discovery techniques to dynamic relational graph analysis. Such graphs can be encoded into n-ary relations (n ≥ 3). Our use case concerns bicycle renting in the Vélo'v system (self-service bicycle renting in Lyon). It illustrates the added-value of some rules that can be computed thanks to our software prototypes.
45
Chan, Ming-Yuen. "Quality enhancement and relation-aware exploration pipeline for volume visualization /." View abstract or full-text, 2009. http://library.ust.hk/cgi/db/thesis.pl?CSED%202009%20CHANM.
Full text
46
Maturana, Miranda Francisco Ramón Javier. "Le système des villes moyennes du sud du Chili, vers la construction de nouveaux espaces de relations ?" Thesis, Paris 4, 2012. http://www.theses.fr/2012PA040082.
Full textAbstract:
La question des villes moyennes ou intermédiaires a été largement débattue, en raison de la difficulté à établir leur définition. Un système de villes moyennes particulier est situé au sud du Chili, constitué par les régions de La Araucanía, Los Ríos et Los Lagos. Ce système présente une configuration spatiale plutôt monocentrique, où les interactions entre villes sont développées à l'intérieur de chaque région et, par conséquence, les liens transfrontaliers sont faibles voire inexistants. Les centres urbains à l'intérieur de chaque région développent différents types de configuration spatiale, tant à un niveau régional et que local. Cette thèse a cherché à comprendre les concepts de ville intermédiaire ou moyenne et à les stabiliser, pour pouvoir mieux comprendre le système de villes moyennes du sud du Chili à partir d'une analyse de réseau et du degré de cohésion des différentes villes. Le réseau qui organise ce système est déterminé principalement par les relations hiérarchiques et de type vertical. Ainsi, il existe un élevé degré de dépendance à l'égard des capitales régionales, ce qui organise un réseau monocentrique à l'intérieur de chaque espace régional, où il serait encore possible de trouver des villes isolées. Le degré de polycentrisme pour l'ensemble du système a été estimé moyen à faible. Cette situation est encore plus dramatique au sein de chaque espace régional. Les relations spatiales entre centres urbains se réalisent à deux échelles. Dans la première, trois types d'organisation spatiale se mettent en place et dans la deuxième, trois types d'organisation spatiale ont lieu entre des paires de nœuds du réseauMedium-size cities have been the subject of profound debate given their complexity in order to define them. A particular system consisting of this type of cities is located in southern Chile, an area which comprises the regions of La Araucania, Los Ríos and Los Lagos. This system seems to have a monocentric configuration, where interactions between population centers would be arranged within each region and therefore trans-border links would be weak or not present. In addition to that, urban centers that compose the system would have differentiated spatial patterns, both at a regional and local scale. In this sense, this thesis tries to understand the concept of medium-size and intermediate cities and stabilize it, to understand the system of cities of southern Chile thanks to a network approach and the analysis of the cohesion degree in urban centers. The network that organizes this system is determined largely by relations of hierarchical and vertical type, having a high degree of dependency of small cities within a region to each of the regional capitals, which organizes a moncentric network within each regional area, including identifying isolated towns. The degree of polycentrism for the entire system is low and this situation is even deeper within each regional area. The spatial relationships between urban centers are in two scales, first to set up three types of spatial organization and second presents three types of spatial organization that develop between pairs of nodes in the network
47
Flindt, Natalie Lorraine. "Exploring the relation between basic reading proficiency and reading comprehension across grades /." view abstract or download file of text, 2007. http://proquest.umi.com/pqdweb?did=1404348961&sid=2&Fmt=2&clientId=11238&RQT=309&VName=PQD.
Full textAbstract:
Thesis (Ph. D.)--University of Oregon, 2007.Typescript. Includes vita and abstract. Includes bibliographical references (leaves 105-108). Also available for download via the World Wide Web; free to University of Oregon users.
48
McPhee, Jillian Dawn. "Endomorphisms of Fraïssé limits and automorphism groups of algebraically closed relational structures." Thesis, University of St Andrews, 2012. http://hdl.handle.net/10023/3358.
Full textAbstract:
Let Ω be the Fraïssé limit of a class of relational structures. We seek to answer the following semigroup theoretic question about Ω. What are the group H-classes, i.e. the maximal subgroups, of End(Ω)? Fraïssé limits for which we answer this question include the random graph R, the random directed graph D, the random tournament T, the random bipartite graph B, Henson's graphs G[subscript n] (for n greater or equal to 3) and the total order Q. The maximal subgroups of End(Ω) are closely connected to the automorphism groups of the relational structures induced by the images of idempotents from End(Ω). It has been shown that the relational structure induced by the image of an idempotent from End(Ω) is algebraically closed. Accordingly, we investigate which groups can be realised as the automorphism group of an algebraically closed relational structure in order to determine the maximal subgroups of End(Ω) in each case. In particular, we show that if Γ is a countable graph and Ω = R,D,B, then there exist 2[superscript aleph-naught] maximal subgroups of End(Ω) which are isomorphic to Aut(Γ). Additionally, we provide a complete description of the subsets of Q which are the image of an idempotent from End(Q). We call these subsets retracts of Q and show that if Ω is a total order and f is an embedding of Ω into Q such that im f is a retract of Q, then there exist 2[superscript aleph-naught] maximal subgroups of End(Q) isomorphic to Aut(Ω). We also show that any countable maximal subgroup of End(Q) must be isomorphic to Zⁿ for some natural number n. As a consequence of the methods developed, we are also able to show that when Ω = R,D,B,Q there exist 2[superscript aleph-naught] regular D-classes of End(Ω) and when Ω = R,D,B there exist 2[superscript aleph-naught] J-classes of End(Ω). Additionally we show that if Ω = R,D then all regular D-classes contain 2[superscript aleph-naught] group H-classes. On the other hand, we show that when Ω = B,Q there exist regular D-classes which contain countably many group H-classes.
49
Lauer, Joseph. "Cubulating one-relator groups with torsion." Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=101861.
Full textAbstract:
Let
50
Trissl, Silke. "Cost-based optimization of graph queries in relational database management systems." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2012. http://dx.doi.org/10.18452/16544.
Full textAbstract:
Graphen sind in vielen Bereichen des Lebens zu finden, wobei wir speziell an Graphen in der Biologie interessiert sind. Knoten in solchen Graphen sind chemische Komponenten, Enzyme, Reaktionen oder Interaktionen, die durch Kanten miteinander verbunden sind. Eine effiziente Ausführung von Graphanfragen ist eine Herausforderung. In dieser Arbeit präsentieren wir GRIcano, ein System, das die effiziente Ausführung von Graphanfragen erlaubt. Wir nehmen an, dass Graphen in relationalen Datenbankmanagementsystemen (RDBMS) gespeichert sind. Als Graphanfragesprache schlagen wir eine erweiterte Version der Pathway Query Language (PQL) vor. Der Hauptbestandteil von GRIcano ist ein kostenbasierter Anfrageoptimierer. Diese Arbeit enthält Beiträge zu allen drei benötigten Komponenten des Optimierers, der relationalen Algebra, Implementierungen und Kostenmodellen. Die Operatoren der relationalen Algebra sind nicht ausreichend, um Graphanfragen auszudrücken. Daher stellen wir zuerst neue Operatoren vor. Wir schlagen den Erreichbarkeits-, Distanz-, Pfadlängen- und Pfadoperator vor. Zusätzlich geben wir Regeln für die Umformung von Ausdrücken an. Des Weiteren präsentieren wir Implementierungen für jeden vorgeschlagenen Operator. Der Hauptbeitrag ist GRIPP, eine Indexstruktur, die die effiziente Ausführung von Erreichbarkeitsanfragen auf sehr großen Graphen erlaubt. Wir zeigen, wie GRIPP und die rekursive Anfragestrategie genutzt werden können, um Implementierungen für alle Operatoren bereitzustellen. Die dritte Komponente von GRIcano ist das Kostenmodell, das Kardinalitätsabschätzungen der Operatoren und Kostenfunktionen für die Implementierungen benötigt. Basierend auf umfangreichen Experimenten schlagen wir in dieser Arbeit Funktionen dafür vor. Der neue Ansatz unserer Kostenmodelle ist, dass die Funktionen nur Kennzahlen der Graphen verwenden. Abschließend zeigen wir die Wirkungsweise von GRIcano durch Beispielanfragen auf echten biologischen Graphen.Graphs occur in many areas of life. We are interested in graphs in biology, where nodes are chemical compounds, enzymes, reactions, or interactions that are connected by edges. Efficiently querying these graphs is a challenging task. In this thesis we present GRIcano, a system that efficiently executes graph queries. For GRIcano we assume that graphs are stored and queried using relational database management systems (RDBMS). We propose an extended version of the Pathway Query Language PQL to express graph queries. The core of GRIcano is a cost-based query optimizer. This thesis makes contributions to all three required components of the optimizer, the relational algebra, implementations, and cost model. Relational algebra operators alone are not sufficient to express graph queries. Thus, we first present new operators to rewrite PQL queries to algebra expressions. We propose the reachability, distance, path length, and path operator. In addition, we provide rewrite rules for the newly proposed operators in combination with standard relational algebra operators. Secondly, we present implementations for each proposed operator. The main contribution is GRIPP, an index structure that allows us to answer reachability queries on very large graphs. GRIPP has advantages over other existing index structures, which we review in this work. In addition, we show how to employ GRIPP and the recursive query strategy as implementation for all four proposed operators. The third component of GRIcano is the cost model, which requires cardinality estimates for operators and cost functions for implementations. Based on extensive experimental evaluation of our proposed algorithms we present functions to estimate the cardinality of operators and the cost of executing a query. The novelty of our approach is that these functions only use key figures of the graph. We finally present the effectiveness of GRIcano using exemplary graph queries on real biological networks.