Dissertations / Theses: 'Base de données graphes'

1

Castelltort, Arnaud. "Historisation de données dans les bases de données NoSQLorientées graphes." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20076.

Full text

Abstract:

Cette thèse porte sur l'historisation des données dans les bases de données graphes. La problématique des données en graphes existe depuis longtemps mais leur exploitation par des moteurs de système de gestion de bases de données, principalement dans les moteurs NoSQL, est récente. Cette apparition est notamment liée à l'émergence des thématiques Big Data dont les propriétés intrinsèques, souvent décrites à l'aide des propriétés 3V (variété, volume, vélocité), ont révélé les limites des bases de données relationnelles classiques. L'historisation quant à elle, est un enjeu majeur des SI qui a été longtemps abordé seulement pour des raisons techniques de sauvegarde, de maintenance ou plus récemment pour des raisons décisionnelles (suites applicatives de Business Intelligence). Cependant, cet aspect s'avère maintenant prendre une place prédominante dans les applications de gestion. Dans ce contexte, les bases de données graphes qui sont de plus en plus utilisées n'ont que très peu bénéficié des apports récents de l'historisation. La première contribution consiste à étudier le nouveau poids des données historisées dans les SI de gestion. Cette analyse repose sur l'hypothèse selon laquelle les applications de gestion intègrent de plus en plus en leur sein les enjeux d'historisation. Nous discutons ce positionnement au regard de l'analyse de l'évolution des SI par rapport à cette problématique. La deuxième contribution vise, au-delà de l'étude de l'évolution des sytèmes d'information, à proposer un modèle innovant de gestion de l'historisation dans les bases de données NoSQL en graphes. Cette proposition consiste d'une part en l'élaboration d'un système unique et générique de représentation de l'historique au sein des BD NoSQL en graphes et d'autre part à proposer des modes d'interrogation (requêtes). Nous montrons qu'il est possible d'utiliser ce système aussi bien pour des requêtes simples (c'est-à-dire correspondant à ce que l'on attend en première intention d'un système d'historisation~: récupérer les précédentes versions d'une donnée) mais aussi de requêtes plus complexes qui permettent de tirer parti aussi bien de la notion d'historisation que des possibilités offertes par les bases de données graphes (par exemple, la reconnaissance de motifs dans le temps)
This thesis deals with data historization in the context of graphs. Graph data have been dealt with for many years but their exploitation in information systems, especially in NoSQL engines, is recent. The emerging Big Data and 3V contexts (Variety, Volume, Velocity) have revealed the limits of classical relational databases. Historization, on its side, has been considered for a long time as only linked with technical and backups issues, and more recently with decisional reasons (Business Intelligence). However, historization is now taking more and more importance in management applications.In this framework, graph databases that are often used have received little attention regarding historization. Our first contribution consists in studying the impact of historized data in management information systems. This analysis relies on the hypothesis that historization is taking more and more importance. Our second contribution aims at proposing an original model for managing historization in NoSQL graph databases.This proposition consists on the one hand in elaborating a unique and generic system for representing the history and on the other hand in proposing query features.We show that the system can support both simple and complex queries.Our contributions have been implemented and tested over synthetic and real databases

APA, Harvard, Vancouver, ISO, and other styles

2

Ingalalli, Vijay. "Querying and Mining Multigraphs." Thesis, Montpellier, 2017. http://www.theses.fr/2017MONTS080/document.

Full text

Abstract:

Avec des volumes de données et d’informations de plus en plus importants, des données de plus en plus complexes et fortement inter-reliées, l’extraction de connaissances reste un véritable défi. Les graphes offrent actuellement un support de représentation efficace pour représenter ces données. Parmi les approches existantes, les multi-graphes ont montré que leur pouvoir d’expression était particulièrement adapté pour manipuler des données complexes possédant de nombreux types de relations entre elles. Cette thèse aborde deux aspects principaux liés aux multigraphes : la recherche de sous graphes et la fouille de sous graphes fréquents dans des multigraphes.Elle propose trois propositions dans le domaines du requêtage et de la fouille de données.La première contribution s’inscrit dans la recherche de sous graphes et concerne l’isomorphisme de sous graphes dans des multigraphes. Cette approche peut, par exemple, être appliquée dans de nombreux domaines d’applications comme l’analyse d’images satellites ou de réseaux sociaux. Dans la seconde, nous nous intéressons aux graphes de connaissances et abordons la problématique de l’homorphisme de graphes dans des multigraphes RDF. Dans les deux contributions, nous proposons de nouvelles techniques d’indexations pour représenter efficacement les informations contenues dans les multigraphes. La recherche des sous graphes tire avantage de ces nouveaux index et différentes heuristiques et optimisations sont également proposées pour garantir de bonnes performances lors de l’exécution des requêtes. La seconde contribution s’inscrit dans le domaine de la fouille de données et nous proposons un algorithme efficace pour extraire les multigraphes fréquents. Etant donné l’espace de recherche à considérer, la recherche de motifs fréquents dans des graphes est un problème difficile en fouille de données. Pour parcourir efficacement l’espace de recherche encore plus volumineux pour les multigraphes, nous proposons de nouvelles techniques et méthodes pour le traverser efficacement notamment en éliminant des candidats où détectant à l’avance les motifs non fréquents. Pour chacune de ces propositions de nombreuses expérimentations sont réalisées pour valider à la fois leurs performances et exactitudes en les comparant avec les approches existantes. Finalement, nous proposons une étude de cas sur des jeux de données issues d’images satellites modélisées sous la forme de multigraphe et montrons que l’application de nos propositions permet de mettre en évidence de nouvelles connaissances utiles
With the ever-increasing growth of data and information, extracting the right knowledge has become a real challenge.Further, the advanced applications demand the analysis of complex, interrelated data which cannot be adequately described using a propositional representation. The graph representation is of great interest for the knowledge extraction community, since graphs are versatile data structures and are one of the most general forms of data representation. Among several classes of graphs, textit{multigraphs} have been captivating the attention in the recent times, thanks to their inherent property of succinctly representing the entities by allowing the rich and complex relations among them.The focus of this thesis is streamlined into two themes of knowledge extraction; one being textit{knowledge retrieval}, where we focus on the subgraph query matching aspects in multigraphs, and the other being textit{knowledge discovery}, where we focus on the problem of frequent pattern mining in multigraphs.This thesis makes three main contributions in the field of query matching and data mining.The first contribution, which is very generic, addresses querying subgraphs in multigraphs that yields isomorphic matches, and this problem finds potential applications in the domains of remote sensing, social networks, bioinformatics, chemical informatics. The second contribution, which is focussed on knowledge graphs, addresses querying subgraphs in RDF multigraphs that yield homomorphic matches. In both the contributions, we introduce efficient indexing structures that capture the multiedge information. The query matching processes introduced have been carefully optimized, w.r.t. the time performance and the heuristics employed assure robust performance.The third contribution is in the field of data mining, where we propose an efficient frequent pattern mining algorithm for multigraphs. We observe that multigraphs pose challenges while exploring the search space, and hence we introduce novel optimization techniques and heuristic search methods to swiftly traverse the search space.For each proposed approach, we perform extensive experimental analysis by comparing with the existing state-of-the-art approaches in order to validate the performance and correctness of our approaches.In the end, we perform a case study analysis on a remote sensing dataset. Remote sensing dataset is modelled as a multigraph, and the mining and query matching processes are employed to discover some useful knowledge

APA, Harvard, Vancouver, ISO, and other styles

3

Tung, Tony. "Indexation 3D de bases de données d'objets par graphes de Reeb améliorés." Paris, ENST, 2005. http://www.theses.fr/2005ENST0013.

Full text

Abstract:

La rapide avancée de la technologique numérique a permis d'améliorer les méthodes d'acquisition et de rendu de modèles 3D. On peut constater qu'aujourd'hui les bases de données d'objets 3D sont présentes dans beaucoup de domaines, qu'ils soient ludiques (jeux, multimédia) ou scientifiques (applications médicales, industrielles, héritage culturel, etc. ). La facilité d'acquisition et de reconstruction des modèles 3D, ainsi que leur modélisation permettent de créer de grandes bases de données, et il devient difficile de naviguer dans ces bases pour retrouver des informations. L'indexation des objets 3D apparaît donc comme une solution nécessaire et prometteuse pour gérer ce nouveau type de données. Notre étude s'insérant dans le cadre du projet européen SCULPTEUR IST-2001-35372 dont des partenaires étaient des musées, nous avons donc travaillé avec des bases de données de modèles 3D muséologiques. L'indexation des éléments d'une base de données consiste à définir une méthode permettant d'effectuer des comparaisons parmi les composants de cette base. Actuellement, une des principales applications consiste à effectuer des requêtes de similarité : étant donné une "clé'' de recherche, on extrait de la base de données les éléments ayant la clé la plus similaire. Nous présentons dans ce mémoire une méthode d'indexation de modèles 3D appliquée aux recherches par similarité de forme et d'aspect dans des bases de données d'objets 3D. L'approche repose sur la méthode d'appariement de graphes de Reeb multirésolution proposée par [Hilaga et al, 01]. Dans le cadre de notre étude, nous travaillons avec des maillages de modèles 3D de géométrie plus ou moins complexes, à différents niveaux
The strong development of numerical technologies has lead to efficient 3D acquisition of real objects and rendering of 3D methods. Nowadays 3D object databases appear in various areas for leisure (games, multimedia) as well as for scientific applications (medical, industrial part catalogues, cultural heritage, etc. ). Large database can be nowadays quickly populated using 3D mesh acquisition and reconstruction tools which have become easy to use, and with new ergonomic 3D design tools which have become very popular. As database size is growing, tools to retrieve information become more and more important. 3D object indexing appears to be a useful and very promising way to manage this new kind of data. As our study took place in the framework of the european project SCULPTEUR IST-2001-35372 which involved museums, we worked with museological 3D model databases. Database indexing consists on defining a method able to perform comparisons between the database elements. Similarity retrieval is one of the main application: using a research “key”, a subset of elements with the most similar keys are extracted from the database. This manuscript presents a 3D shape matching method for 3D mesh models applied to content-based search in database of 3D objects. The approach is based on the multiresolution Reeb graph (MRG) proposed by [Hilaga et al, 01]. MRG provides a rich representation of shapes able in particular to embed the object topology. In our framework, we consider 3D mesh models of various geometrical complexity, of different resolution, and when available with color texture map. The original approach, mainly based on the 3D object topology, is not accurate enough to obtain

APA, Harvard, Vancouver, ISO, and other styles

4

Ghazal, Moultazem. "Contribution à la gestion des données géographiques : Modélisation et interrogation par croquis." Phd thesis, Université Paul Sabatier - Toulouse III, 2010. http://tel.archives-ouvertes.fr/tel-00504944.

Full text

Abstract:

Les Systèmes d'Information Géographiques (SIG) réclament des besoins particuliers de gestion de leur contenu, parce qu'ils manipulent des données dont les structures sont complexes et hétérogènes. Ces données sont souvent difficiles à décrire par des requêtes classiques ou des prédicats basés sur des attributs. Le croquis à main levée (sketch) est une veille forme de présentation qui a été employée pour visualiser, échanger et enregistrer l'information graphique. Il semble être ainsi facilement adaptable pour présenter et interroger d'une manière flexible les données des SIG

APA, Harvard, Vancouver, ISO, and other styles

5

Douar, Brahim. "Fouille de sous-graphes fréquents à base d'arc consistance." Thesis, Montpellier 2, 2012. http://www.theses.fr/2012MON20108/document.

Full text

Abstract:

Avec la croissance importante du besoin d'analyser une grande masse de données structurées tels que les composés chimiques, les structures de protéines ou même les réseaux sociaux, la fouille de sous-graphes fréquents est devenue un défi réel en matière de fouille de données. Ceci est étroitement lié à leur nombre exponentiel ainsi qu'à la NP-complétude du problème d'isomorphisme d'un sous-graphe général. Face à cette complexité, et pour gérer cette taille importante de l'espace de recherche, les méthodes classiques de fouille de graphes ont exploré des heuristiques de recherche basées sur le support, le langage de description des exemples (limitation aux chemins, aux arbres, etc.) ou des hypothèses (recherche de sous-arborescence communes, de chemins communs, etc.). Dans le cadre de cette thèse, nous nous basons sur une méthode d'appariement de graphes issue du domaine de la programmation par contraintes, nommée AC-projection, qui a le mérite d'avoir une complexité polynomiale. Nous introduisons des approches de fouille de graphes permettant d'améliorer les approches existantes pour ce problème. En particulier, nous proposons deux algorithmes, FGMAC et AC-miner, permettant de rechercher les sous-graphes fréquents à partir d'une base de graphes. Ces deux algorithmes profitent, différemment, des propriétés fortes intéressantes de l'AC-projection. En effet, l'algorithme FGMAC adopte un parcours en largeur de l'espace de recherche et exploite l'approche par niveau introduite dans Apriori, tandis que l'algorithme AC-miner parcourt l'espace en profondeur par augmentation de motifs, assurant ainsi une meilleure mise à l'échelle pour les grands graphes. Ces deux approches permettent l'extraction d'un type particulier de graphes, il s'agit de celui des sous-graphes AC-réduits fréquents. Dans un premier temps, nous prouvons, théoriquement, que l'espace de recherche de ces sous-graphes est moins important que celui des sous-graphes fréquents à un isomorphisme près. Ensuite, nous menons une série d'expérimentations permettant de prouver que les algorithmes FGMAC et AC-miner sont plus efficients que ceux de l'état de l'art. Au même temps, nous prouvons que les sous-graphes AC-réduits fréquents, en dépit de leur nombre sensiblement réduit, ont le même pouvoir discriminant que les sous-graphes fréquents à un isomorphisme près. Cette étude est menée en se basant sur une évaluation expérimentale de la qualité des sous-graphes AC-réduits fréquents dans un processus de classification supervisée de graphes
With the important growth of requirements to analyze large amount of structured data such as chemical compounds, proteins structures, social networks, to cite but a few, graph mining has become an attractive track and a real challenge in the data mining field. Because of the NP-Completeness of subgraph isomorphism test as well as the huge search space, frequent subgraph miners are exponential in runtime and/or memory use. In order to alleviate the complexity issue, existing subgraph miners have explored techniques based on the minimal support threshold, the description language of the examples (only supporting paths, trees, etc.) or hypothesis (search for shared trees or common paths, etc.). In this thesis, we are using a new projection operator, named AC-projection, which exhibits nice complexity properties as opposed to the graph isomorphism operator. This operator comes from the constraints programming field and has the advantage of a polynomial complexity. We propose two frequent subgraph mining algorithms based on the latter operator. The first one, named FGMAC, follows a breadth-first order to find frequent subgraphs and takes advantage of the well-known Apriori levelwise strategy. The second is a pattern-growth approach that follows a depth-first search space exploration strategy and uses powerful pruning techniques in order to considerably reduce this search space. These two approaches extract a set of particular subgraphs named AC-reduced frequent subgraphs. As a first step, we have studied the search space for discovering such frequent subgraphs and proved that this one is smaller than the search space of frequent isomorphic subgraphs. Then, we carried out experiments in order to prove that FGMAC and AC-miner are more efficient than the state-of-the-art algorithms. In the same time, we have studied the relevance of frequent AC-reduced subgraphs, which are much fewer than isomorphic ones, on classification and we conclude that we can achieve an important performance gain without or with non-significant loss of discovered pattern's quality

APA, Harvard, Vancouver, ISO, and other styles

6

Ben, Dhia Imen. "Gestion des grandes masses de données dans les graphes réels." Electronic Thesis or Diss., Paris, ENST, 2013. http://www.theses.fr/2013ENST0087.

Full text

Abstract:

De nos jours, un grand nombre d’applications utilisent de grands graphes pour la modélisation de données du monde réel. Nous avons assisté, ces dernières années, à une très rapide croissance de ces graphes dans divers contextes ; à savoir, les réseaux sociaux, la bioinformatique, le web sémantique, les systèmes de gestion des données géographiques, etc. La gestion, l’analyse et l’interrogation de ces données constituent un enjeu très important et ont suscité un vaste intérêt dans la communauté des Bases de Données. L’objectif de cette thèse est de fournir des algorithmes efficaces pour l’indexation et l’interrogation des données dans les grands graphes. Nous avons proposé EUQLID, une technique d’indexation qui permet de répondre efficacement aux requêtes de calcul de distance dans les grands graphes orientés. L’efficacité de cette technique est dûe au fait qu’elle exploite des propriétés intéressantes des graphes du monde réel. En effet, nous proposons un algorithme basé sur une variante efficace du fameux algorithme 2-hop. Les résultats obtenus montrent que notre algorithme surpassent les approches existantes en terme de temps d’indexation, ainsi qu’en temps de réponse. En effet, il permet de calculer la distance entre deux noeuds en quelques centaines de millisecondes sur de très grands graphes. Nous proposons également un modèle de contrôle d’accès pour les réseaux sociaux qui permet aux utlisateurs de spécifier leurs poltiques de contrôle d’accès en se basant sur leurs relations sociales, et qui peut utiliser EUQLID pour passer à l’échelle. Nous décrivons Primates comme étant un prototype appliquant le modèle proposé
In the last few years, we have been witnessing a rapid growth of networks in a wide range of applications such as social networking, bio-informatics, semantic web, road maps, etc. Most of these networks can be naturally modeled as large graphs. Managing, analyzing, and querying such data has become a very important issue, and, has inspired extensive interest within the database community. In this thesis, we address the problem of efficiently answering distance queries in very large graphs. We propose EUQLID, an efficient algorithm to answer distance queries on very large directed graphs. This algorithm exploits some interesting properties that real-world graphs exhibit. It is based on an efficient variant of the seminal 2-hop algorithm. We conducted an extensive set of experiments against state-of-the-art algorithms which show that our approach outperforms existing approaches and that distance queries can be processed within hundreds of milliseconds on very large real-world directed graphs. We also propose an access control model for social networks which can make use of EUQLID to scale on very large graphs. This model allows users to specify fine-grained privacy policies based on their relations with other users in the network. We describe and demonstrate Primates as a prototype which enforces the proposed access control model and allows users to specify their privacy preferences via a graphical user-friendly interface

APA, Harvard, Vancouver, ISO, and other styles

7

Buron, Maxime. "Raisonnement efficace sur des grands graphes hétérogènes." Thesis, Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAX061.

Full text

Abstract:

Le Web sémantique propose des représentations de connaissances, qui permettent d'intégrer facilement des données hétérogènes issues de plusieurs sources en une base de connaissances unifiée. Dans cette thèse, nous étudions des techniques d'interrogation de telles bases de connaissances.La première partie est dédiée à des techniques de réponse à des requêtes sur une base de connaissances représentée par un graphe RDF sous des contraintes ontologiques. Les connaissances implicites produites par le raisonnement, à partir des règles de déduction RDFS, doivent être prises en compte pour répondre correctement à de telles requêtes.Pour commencer, nous présentons un algorithme de reformulation de requêtes dites Basic Graph Pattern (BGP), qui exploite une partition des règles de déduction en des règles sur les assertions et sur les contraintes. Puis nous introduisons une nouvelle disposition du stockage des graphes RDF, qui combine deux dispositions connues. Pour ces deux contributions, des expérimentations permettent de valider nos résultats théoriques et algorithmiques.Dans la deuxième partie, nous considérons le problème d'interrogation, par des requêtes BGP, de sources de données hétérogènes intégrées en un graphe RDF. Nous introduisons un cadre d'intégration de données sous des contraintes ontologiques RDFS, utilisant une spécification d'intégration basée sur des mappings Global-Local-As-View, rarement considérée jusqu'ici dans la littérature. Nous présentons plusieurs stratégies de réponse à des requêtes, qui, soit matérialisent les données en un graphe RDF, soit laissent ce graphe virtuel. Ces stratégies diffèrent sur quand et comment le raisonnement RDFS est supporté. Nous avons implémenté ces stratégies dans une plate-forme et mené des expérimentations qui démontrent l'intérêt particulier d'une des stratégies basée sur la saturation des mappings. Finalement, nous montrons que cette dernière technique peut être étendue au delà des règles de déduction RDFS au raisonnement défini par un sous-ensemble des règles existentielles
The Semantic Web offers knowledge representations, which allow to integrate heterogeneous data from several sources into a unified knowledge base. In this thesis, we investigate techniques for querying such knowledge bases.The first part is devoted to query answering techniques on a knowledge base, represented by an RDF graph subject to ontological constraints. Implicit information entailed by the reasoning, enabled by the set of RDFS entailment rules, has to be taken into account to correctly answer such queries. First, we present a sound and complete query reformulation algorithm for Basic Graph Pattern queries, which exploits a partition of RDFS entailment rules into assertion and constraint rules. Second, we introduce a novel RDF storage layout, which combines two well-known layouts. For both contributions, our experiments assess our theoretical and algorithmic results.The second part considers the issue of querying heterogeneous data sources integrated into an RDF graph, using BGP queries. Following the Ontology-Based Data Access paradigm, we introduce a framework of data integration under an RDFS ontology, using the Global-Local-As-View mappings, rarely considered in the literature.We present several query answering strategies, which may materialize the integrated RDF graph or leave it virtual, and differ on how and when RDFS reasoning is handled. We implement these strategies in a platform, in order to conduct experiments, which demonstrate the particular interest of one of the strategies based on mapping saturation. Finally, we show that mapping saturation can be extended to reasoning defined by a subset of existential rules

APA, Harvard, Vancouver, ISO, and other styles

8

Ben, Dhia Imen. "Gestion des grandes masses de données dans les graphes réels." Thesis, Paris, ENST, 2013. http://www.theses.fr/2013ENST0087/document.

Full text

Abstract:

De nos jours, un grand nombre d’applications utilisent de grands graphes pour la modélisation de données du monde réel. Nous avons assisté, ces dernières années, à une très rapide croissance de ces graphes dans divers contextes ; à savoir, les réseaux sociaux, la bioinformatique, le web sémantique, les systèmes de gestion des données géographiques, etc. La gestion, l’analyse et l’interrogation de ces données constituent un enjeu très important et ont suscité un vaste intérêt dans la communauté des Bases de Données. L’objectif de cette thèse est de fournir des algorithmes efficaces pour l’indexation et l’interrogation des données dans les grands graphes. Nous avons proposé EUQLID, une technique d’indexation qui permet de répondre efficacement aux requêtes de calcul de distance dans les grands graphes orientés. L’efficacité de cette technique est dûe au fait qu’elle exploite des propriétés intéressantes des graphes du monde réel. En effet, nous proposons un algorithme basé sur une variante efficace du fameux algorithme 2-hop. Les résultats obtenus montrent que notre algorithme surpassent les approches existantes en terme de temps d’indexation, ainsi qu’en temps de réponse. En effet, il permet de calculer la distance entre deux noeuds en quelques centaines de millisecondes sur de très grands graphes. Nous proposons également un modèle de contrôle d’accès pour les réseaux sociaux qui permet aux utlisateurs de spécifier leurs poltiques de contrôle d’accès en se basant sur leurs relations sociales, et qui peut utiliser EUQLID pour passer à l’échelle. Nous décrivons Primates comme étant un prototype appliquant le modèle proposé
In the last few years, we have been witnessing a rapid growth of networks in a wide range of applications such as social networking, bio-informatics, semantic web, road maps, etc. Most of these networks can be naturally modeled as large graphs. Managing, analyzing, and querying such data has become a very important issue, and, has inspired extensive interest within the database community. In this thesis, we address the problem of efficiently answering distance queries in very large graphs. We propose EUQLID, an efficient algorithm to answer distance queries on very large directed graphs. This algorithm exploits some interesting properties that real-world graphs exhibit. It is based on an efficient variant of the seminal 2-hop algorithm. We conducted an extensive set of experiments against state-of-the-art algorithms which show that our approach outperforms existing approaches and that distance queries can be processed within hundreds of milliseconds on very large real-world directed graphs. We also propose an access control model for social networks which can make use of EUQLID to scale on very large graphs. This model allows users to specify fine-grained privacy policies based on their relations with other users in the network. We describe and demonstrate Primates as a prototype which enforces the proposed access control model and allows users to specify their privacy preferences via a graphical user-friendly interface

APA, Harvard, Vancouver, ISO, and other styles

9

Dalleau, Kevin. "Une approche stochastique à base d’arbres aléatoires pour le calcul de dissimilarités : application au clustering pour diverses structures de données." Electronic Thesis or Diss., Université de Lorraine, 2021. http://www.theses.fr/2021LORR0181.

Full text

Abstract:

La notion de distance, et plus généralement de dissimilarité, est une notion importante en fouille de données, tout particulièrement dans les approches non supervisées. Les algorithmes de cette classe de méthodes visant à regrouper de manière homogène des objets, nombre d’entre eux s’appuient sur une notion de dissimilarité, afin de quantifier la proximité entre objets. Le choix des algorithmes ainsi que celui des dissimilarités n’est cependant pas trivial. Plusieurs éléments peuvent motiver ces choix, tels que le type de données – données homogènes ou non –, leur représentation – vecteurs d’attributs, graphes –, ou encore certaines de leurs caractéristiques – fortement corrélées, bruitées, etc. –. Bien que de nombreuses mesures existent, leur choix peut devenir complexe dans certains cadres spécifiques. Ceci entraîne une complexité supplémentaire dans les tâches d’exploration et de fouille des données. Nous présentons dans cette thèse une nouvelle approche permettant le calcul de dissimilarités, basée sur des arbres aléatoires. Il s’agit d’une approche originale dont nous montrons plusieurs avantages, parmi lesquels l’on retrouve une grande versatilité. En effet, par le biais de différents modules de calcul de dissimilarités que nous accolons à la méthode, il devient possible de l’appliquer dans divers cadres. Nous présentons notamment dans ce document deux modules, permettant le calcul de dissimilarités — et, in fine, le clustering — sur des données structurées sous forme de vecteur d’attributs, et sur des données sous forme de graphes. Nous discutons des résultats très prometteurs obtenus par cette approche, ainsi que des nombreuses perspectives ouvertes par cette dernière, telle que le calcul de dissimilarité dans le cadre des graphes attribués, par le biais d’une approche unifiée
The notion of distance, and more generally of dissimilarity, is an important one in data mining, especially in unsupervised approaches. The algorithms belonging to this class of methods aim at grouping objects in an homogeneous way, and many of them rely on a notion of dissimilarity, in order to quantify the proximity between objects. The choice of algorithms as well as that of dissimilarities is not trivial. Several elements can motivate these choices, such as the type of data – homogeneous data or not –, their representation – feature vectors, graphs –, or some of their characteristics – highly correlated, noisy, etc. –. Although many measures exist, their choice can become complex in some specific settings. This leads to additional complexity in data mining tasks. In this thesis, we present a new approach for computing dissimilarities based on random trees. It is an original approach, which has several advantages such as a great versatility. Indeed, using different dissimilarity calculation modules that we can plug to the method, it becomes possible to apply it in various settings. In particular, we present in this document two modules, enabling the computation of dissimilarities - and, in fine, clustering - on data structured as feature vectors, and on data in the form of graphs. We discuss the very promising results obtained by this approach, as well as the numerous perspectives that it opens, such as the computation of dissimilarity in the framework of attributed graphs, through a unified approach

APA, Harvard, Vancouver, ISO, and other styles

10

Fallouh, Fouad. "Données complexes et relation universelle avec inclusions : une aide à la conception et à l'interrogation des bases de données." Lyon 1, 1994. http://www.theses.fr/1994LYO10217.

Full text

Abstract:

Notre travail est a la frontiere des modeles semantiques de donnees et des donnees complexes ; il repose sur le modele relation universelle avec inclusions. Dans cette these nous montrons d'abord que les dependances d'inclusion permettent de definir des contraintes d'integrite plus generales que l'integrite referentielle concernant une, deux ou plus de deux relations et nous presentons comment les controler dans les sgbd relationnels actuels. La suite de la these s'est attachee a cumuler les avantages du modele relation universelle avec inclusions et des donnees complexes. Nous voulons recuperer la simplicite de description lors d'une conception par donnees complexes et leur adaptation aux traitements prevus. Nous donnons le principe de l'editeur graphique, appele lacsi-complexe, que nous avons construit et developpe en utilisant l'atelier de genie logiciel graphtalk. Cet editeur est capable de capter simplement la connaissance de l'analyste ou de l'utilisateur, de profiter de la faculte visionnaire d'utilisateurs ou d'administrateurs d'applications et de reprendre l'acquit de fichiers ou de bases de donnees non relationnelles existantes. Lacsi-complexe permet de specifier un schema de donnees appele foret complexe qui est: ? un ensemble de donnees complexes avec des sommets values ou non, des arcs totalement ou partiellement definis, monovalues ou multivalues, des cles et des attributs de rupture, complete par ? des dependances fonctionnelles, des composantes de jointure et des dependances d'inclusion. Il en deduit, en vue d'une implantation relationnelle, un graphe semantique normalise. Pour cela il represente les structures de liste, d'ensemble ordonne et d'amas, en s'aidant d'attributs rang et identifiant. Cependant ainsi la semantique des traitements susceptible d'etre representee par les donnees complexes disparait. Nous montrons que le modele foret complexe s'il peut, par duplication d'attributs a l'interieur d'une donnee complexe ou par attributs communs entre donnees complexes, representer la semantique des donnees, perd de sa lisibilite. En consequence, nous proposons un schema de donnees compact et quasi-unique intermediaire entre le graphe semantique normalise et la foret complexe: le graphe semantique normalise arbore. Ce graphe est un ensemble de donnees complexes sans attributs non racines dupliques et liees par des dependances d'inclusion. Il est une aide a la conception des bases de donnees oriente objet. Le graphe semantique normalise arbore est aussi un support privilegie pour l'interrogation graphique. En effet, nous etendons l'interface d'interrogation ruitalk, reposant sur le graphe semantique normalise, aux donnees complexes. Nous adjoignons aussi un mecanisme de jointures implicites

APA, Harvard, Vancouver, ISO, and other styles

11

Zneika, Mussab. "Interrogation du web sémantique à l'aide de résumés de graphes de données." Thesis, Cergy-Pontoise, 2019. http://www.theses.fr/2019CERG1010.

Full text

Abstract:

La quantité de données RDF disponibles augmente rapidement à la fois en taille et en complexité, les Bases de Connaissances (Knowledge Bases – KBs) contenant des millions, voire des milliards de triplets étant aujourd’hui courantes. Plus de 1000 sources de données sont publiées au sein du nuage de Données Ouvertes et Liées (Linked Open Data – LOD), qui contient plus de 62 milliards de triplets, formant des graphes de données RDF complexes et de grande taille. L’explosion de la taille, de la complexité et du nombre de KBs et l’émergence des sources LOD ont rendu difficile l’interrogation, l’exploration, la visualisation et la compréhension des données de ces KBs, à la fois pour les utilisateurs humains et pour les programmes. Pour traiter ce problème, nous proposons une méthode pour résumer de grandes KBs RDF, basée sur la représentation du graphe RDF en utilisant les (meilleurs) top-k motifs approximatifs de graphe RDF. La méthode, appelée SemSum+, extrait l’information utile des KBs RDF et produit une description d’ensemble succincte de ces KBs. Elle extrait un type de schéma RDF ayant divers avantages par rapport aux schémas RDF classiques, qui peuvent être respectés seulement partiellement par les données de la KB. A chaque motif approximatif extrait est associé le nombre d’instances qu’il représente ; ainsi, lors de l’interrogation du graphe RDF résumé, on peut facilement déterminer si l’information nécessaire est présente et en quantité significative pour être incluse dans le résultat d’une requête fédérée. Notre méthode ne demande pas le schéma initial de la KB et marche aussi bien sans information de schéma du tout, ce qui correspond aux KBs modernes, construites soit ad-hoc, soit par fusion de fragments en provenance d’autres KBs. Elle fonctionne aussi bien sur des graphes RDF homogènes (ayant la même structure) ou hétérogènes (ayant des structures différentes, pouvant être le résultat de données décrites par des schémas/ontologies différentes).A cause de la taille et de la complexité des graphes RDF, les méthodes qui calculent le résumé en chargeant tout le graphe en mémoire ne passent pas à l’échelle. Pour éviter ce problème, nous proposons une approche générale parallèle, utilisable par n’importe quel algorithme approximatif de fouille de motifs. Elle nous permet de disposer d’une version parallèle de notre méthode, qui passe à l’échelle et permet de calculer le résumé de n’importe quel graphe RDF, quelle que soit sa taille.Ce travail nous a conduit à la problématique de mesure de la qualité des résumés produits. Comme il existe dans la littérature divers algorithmes pour résumer des graphes RDF, il est nécessaire de comprendre lequel est plus approprié pour une tâche spécifique ou pour une KB RDF spécifique. Il n’existe pas dans la littérature de critères d’évaluation établis ou des évaluations empiriques extensives, il est donc nécessaire de disposer d’une méthode pour comparer et évaluer la qualité des résumés produits. Dans cette thèse, nous définissons une approche complète d’évaluation de la qualité des résumés de graphes RDF, pour répondre à ce manque dans l’état de l’art. Cette approche permet une compréhension plus profonde et plus complète de la qualité des différents résumés et facilite leur comparaison. Elle est indépendante de la façon dont l’algorithme produisant le résumé RDF fonctionne et ne fait pas de suppositions concernant le type ou la structure des entrées ou des résultats. Nous proposons un ensemble de métriques qui aident à comprendre non seulement si le résumé est valide, mais aussi comment il se compare à d’autre résumés par rapport aux caractéristiques de qualité spécifiées. Notre approche est capable (ce qui a été validé expérimentalement) de mettre en évidence des différences très fines entre résumés et de produire des métriques capables de mesurer cette différence. Elle a été utilisée pour produire une évaluation expérimentale approfondie et comparative de notre méthode
The amount of RDF data available increases fast both in size and complexity, making available RDF Knowledge Bases (KBs) with millions or even billions of triples something usual, e.g. more than 1000 datasets are now published as part of the Linked Open Data (LOD) cloud, which contains more than 62 billion RDF triples, forming big and complex RDF data graphs. This explosion of size, complexity and number of available RDF Knowledge Bases (KBs) and the emergence of Linked Datasets made querying, exploring, visualizing, and understanding the data in these KBs difficult both from a human (when trying to visualize) and a machine (when trying to query or compute) perspective. To tackle this problem, we propose a method of summarizing a large RDF KBs based on representing the RDF graph using the (best) top-k approximate RDF graph patterns. The method is named SemSum+ and extracts the meaningful/descriptive information from RDF Knowledge Bases and produces a succinct overview of these RDF KBs. It extracts from the RDF graph, an RDF schema that describes the actual contents of the KB, something that has various advantages even compared to an existing schema, which might be partially used by the data in the KB. While computing the approximate RDF graph patterns, we also add information on the number of instances each of the patterns represents. So, when we query the RDF summary graph, we can easily identify whether the necessary information is present and if it is present in significant numbers whether to be included in a federated query result. The method we propose does not require the presence of the initial schema of the KB and works equally well when there is no schema information at all (something realistic with modern KBs that are constructed either ad-hoc or by merging fragments of other existing KBs). Additionally, the proposed method works equally well with homogeneous (having the same structure) and heterogeneous (having different structure, possibly the result of data described under different schemas/ontologies) RDF graphs.Given that RDF graphs can be large and complex, methods that need to compute the summary by fitting the whole graph in the memory of a (however large) machine will not scale. In order to overcome this problem, we proposed, as part of this thesis, a parallel framework that allows us to have a scalable parallel version of our proposed method. This will allow us to compute the summaries of any RDF graph regardless of size. Actually, we generalized this framework so as to be usable by any approximate pattern mining algorithm that needs parallelization.But working on this problem, introduced us to the issue of measuring the quality of the produced summaries. Given that in the literature exist various algorithms that can be used to summarize RDF graphs, we need to understand which one is better suited for a specific task or a specific RDF KB. In the literature, there is a lack of widely accepted evaluation criteria or an extensive empirical evaluation. This leads to the necessity of a method to compare and evaluate the quality of the produced summaries. So, in this thesis, we provide a comprehensive Quality Framework for RDF Graph Summarization to cover the gap that exists in the literature. This framework allows a better, deeper and more complete understanding of the quality of the different summaries and facilitates their comparison. It is independent of the way RDF summarization algorithms work and makes no assumptions on the type or structure neither of the input nor of the final results. We provide a set of metrics that help us understand not only if this is a valid summary but also how a summary compares to another in terms of the specified quality characteristic(s). The framework has the ability, which was experimentally validated, to capture subtle differences among summaries and produce metrics that depict that and was used to provide an extensive experimental evaluation and comparison of our method

APA, Harvard, Vancouver, ISO, and other styles

12

Francis, Nadime. "Vues et requêtes sur les graphes de données : déterminabilité et réécritures." Thesis, Université Paris-Saclay (ComUE), 2015. http://www.theses.fr/2015SACLN015/document.

Full text

Abstract:

Les graphes de données sont naturellement utilisés dans de nombreux contextes incluant par exemple les réseaux sociaux ou le Web sémantique. L'information contenue dans la base de données se trouve alors aussi bien dans les données mêmes que dans la topologie du graphe, c'est-à-dire dans la manière dont les données sont connectées. Cela implique donc de considérer les questions traditionnelles en théorie des bases de données pour des langages de requêtes capables de parler des chemins connectant les nœuds du graphe. Nous nous intéressons en particulier aux problèmes de la déterminabilité et de la réécriture d'une requête à l'aide de vues. Il s'agit alors de décider si une vue de la base de données contient suffisamment d'information pour répondre entièrement à une requête sans consulter la base de données directement, et dans ce cas, d'exprimer explicitement la réponse à la requête à partir de la vue. Ce cadre rencontre de nombreuses applications, notamment pour l'intégration de données et l'optimisation de requêtes. Nous commençons par comparer ces deux questions aux autres problèmes de décision classiques dans ce contexte : calcul des réponses certaines, test de cohérence et mise à jour d'une instance de vue. Nous améliorons ensuite ces résultats dans deux cas spécifiques. Tout d'abord, nous montrons que pour les requêtes régulières de chemin, l'existence d'une réécriture monotone coïncide avec l'existence d'une réécriture dans Datalog. Puis, nous montrons que pour des vues s'intéressant uniquement aux longueurs des chemins du graphe, une notion plus faible de déterminabilité, appelée déterminabilité asymptotique, est décidable et résulte en des réécritures du premier ordre
Graph databases appear naturally in various scenarios, such as social networks and the semantic Web. In these cases, the information contained in the database lies as much in the data itself as in the topology of the graph, that is, in how the data points are linked together. This leads to considering traditional database theory questions for query languages that return data nodes based on the paths of the graph connecting them. We focus our attention on the view-based query determinacy and rewriting problems. They ask the question whether a view of the database contains enough information to fully answer a query without accessing the database directly. If so, we then want to express the answer to the query directly with regards to the view. This setting occurs in many applications, such as data integration and query optimization. We start by comparing these two tasks to other common task in this setting: computing certain answers, checking consistency of a view instance and updating it. We then build on these results in two specific cases. First, we show that for regular path queries, the existence of a monotone rewriting coincides with the existence of a rewriting expressible in Datalog. Then, we show that for views that only consider the lengths of the path in the graph, we can decide a weaker form of determinacy, called asymptotic determinacy, and produce first-order rewritings for the queries that are asymptotically determined

APA, Harvard, Vancouver, ISO, and other styles

13

Lutz, Quentin. "Graph-based contributions to machine-learning." Electronic Thesis or Diss., Institut polytechnique de Paris, 2022. http://www.theses.fr/2022IPPAT010.

Full text

Abstract:

Un graphe est un objet mathématique permettant de représenter des relations entre des entités (appelées nœuds) sous forme d’arêtes. Les graphes sont depuis longtemps un objet d’étude pour différents problèmes allant d’Euler au PageRank en passant par les problèmes de plus courts chemins. Les graphes ont plus récemment trouvé des usages pour l’apprentissage automatique.Avec l’avènement des réseaux sociaux et du web, de plus en plus de données sont représentées sous forme de graphes. Ces graphes sont toujours plus gros, pouvant contenir des milliards de nœuds et arêtes. La conception d’algorithmes efficaces s’avère nécessaire pour permettre l’analyse de ces données. Cette thèse étudie l’état de l’art et propose de nouveaux algorithmes pour la recherche de communautés et le plongement de nœuds dans des données massives. Par ailleurs, pour faciliter la manipulation de grands graphes et leur appliquer les techniques étudiées, nous proposons Scikit-network, une librairie libre développée en Python dans le cadre de la thèse. De nombreuses tâches, telles que le calcul de centralités et la classification de nœuds, peuvent être accomplies à l’aide de Scikit-network.Nous nous intéressons également au problème d’annotation de données. Les techniques supervisées d’apprentissage automatique nécessitent des données annotées pour leur entrainement. La qualité de ces données influence directement la qualité des prédictions de ces techniques une fois entrainées. Cependant, obtenir ces données ne peut pas se faire uniquement à l’aide de machines et requiert une intervention humaine. Nous étudions le problème d’annotation, sous un formalisme utilisant des graphes, avec pour but de décrire les solutions qui limitent cette intervention de façon optimale. Nous caractérisons ces solutions et illustrons comment elles peuvent être appliquées
A graph is a mathematical object that makes it possible to represent relationships (called edges) between entities (called nodes). Graphs have long been a focal point in a number of problems ranging from work by Euler to PageRank and shortest-path problems. In more recent times, graphs have been used for machine learning.With the advent of social networks and the world-wide web, more and more datasets can be represented using graphs. Those graphs are ever bigger, sometimes with billions of edges and billions of nodes. Designing efficient algorithms for analyzing those datasets has thus proven necessary. This thesis reviews the state of the art and introduces new algorithms for the clustering and the embedding of the nodes of massive graphs. Furthermore, in order to facilitate the handling of large graphs and to apply the techniques under study, we introduce Scikit-network, a free and open-source Python library which was developed during the thesis. Many tasks, such as the classification or the ranking of the nodes using centrality measures, can be carried out thanks to Scikit-network.We also tackle the problem of labeling data. Supervised machine learning techniques require labeled data to be trained. The quality of this labeled data has a heavy influence on the quality of the predictions of those techniques once trained. However, building this data cannot be achieved through the sole use of machines and requires human intervention. We study the data labeling problem in a graph-based setting, and we aim at describing the solutions that require as little human intervention as possible. We characterize those solutions and illustrate how they can be applied in real use-cases

APA, Harvard, Vancouver, ISO, and other styles

14

Ettaleb, Mohamed. "Approche de recommandation à base de fouille de données et de graphes étiquetés multi-couches : contributions à la RI sociale." Electronic Thesis or Diss., Aix-Marseille, 2020. http://www.theses.fr/2020AIXM0588.

Full text

Abstract:

D’une manière générale, l’objectif d’un système de recommandation est d’assister les utilisateurs dans le choix d’éléments pertinents parmi un ensemble vaste d’éléments. Dans le contexte actuel de l’explosion du nombre de publications académiques disponibles (livres, articles, etc.) en ligne, fournir un service de recommandations personnalisées devient une nécessité. En outre, la recommandation automatique de livres à partir d’une requête est un thème émergent avec de nombreux verrous scientifiques. Il combine plusieurs problématiques liées à la recherche d’information et la fouille de données pour l’estimation du degré d’opportunité de recommander un livre. Cette estimation doit être effectuée en tenant compte de la requête mais aussi du profil de l’utilisateur (historique de lecture, centres d’intérêts, notes et commentaires associés à ses lectures précédentes) et de l’ensemble de la collection à laquelle appartient le document. Deux grandes pistes ont été abordés dans cette thèse pour traiter le problème de la recommandation automatique des livres : - Identification des intentions de l’utilisateur à partir d’une requête. - Recommandation des livres pertinents selon les besoins de l’utilisateur
In general, the purpose of a recommendation system is to assist users in selecting relevant elements from a wide range of elements. In the context of the explosion in the number of academic publications available (books, articles, etc.) online, providing a personalized recommendation service is becoming a necessity. In addition, automatic book recommendation based on a query is an emerging theme with many scientific locks. It combines several issues related to information retrieval and data mining for the assessment of the degree of opportunity to recommend a book. This assessment must be made taking into account the query but also the user profile (reading history, interest, notes and comments associated with previous readings) and the entire collection to which the document belongs. Two main avenues have been addressed in this paper to deal with the problem of automatic book recommendation : - Identification of the user’s intentions from a query. - Recommendation of relevant books according to the user’s needs

APA, Harvard, Vancouver, ISO, and other styles

15

Cuenca, Pauta Erick. "Visualisation de données dynamiques et complexes : des séries temporelles hiérarchiques aux graphes multicouches." Thesis, Montpellier, 2018. http://www.theses.fr/2018MONTS054/document.

Full text

Abstract:

L'analyse de données de plus en plus complexes, volumineuses et issues de différentes sources (e.g. internet, médias sociaux, etc.) est une tâche difficile. Elle reste cependant cruciale dans de très nombreux domaines d'application. Elle implique, pour pouvoir en extraire des connaissances, de mieux comprendre la nature des données, leur évolution ou les nombreuses relations complexes qu'elles peuvent contenir. La visualisation d'informations s'intéresse aux méthodes de représentations visuelles et interactives permettant d'aider un utilisateur à extraire des connaissances. C'est dans ce contexte que se situe le travail présenté dans ce mémoire. Dans un premier temps, nous nous intéressons à la visualisation de longues séries temporelles hiérarchiques. Après avoir analysé les différentes approches existantes, nous présentons le système MultiStream permettant de visualiser, explorer et comparer l'évolution de séries organisées dans une structure hiérarchique. Nous illustrons son utilisation par deux exemples d'utilisation : émotions exprimées dans des médias sociaux et évolution des genres musicaux. Dans un second temps nous abordons la problématique de données complexes modélisées sous la forme de graphes multicouches (différentes types d'arêtes peuvent relier les n÷uds). Plus particulièrement nous nous intéressons au requêtage visuel de graphes volumineux en présentant VERTIGo un système qui permet de construire des requêtes, d'interroger un moteur spécifique, de visualiser/explorer les résultats à différentes niveaux de détail et de suggérer de nouvelles extensions de requêtes. Nous illustrons son utilisation à l'aide d'un graphe d'auteurs provenant de différentes communautés
The analysis of data that is increasingly complex, large and from different sources (e.g. internet, social medias, etc.) is a dificult task. However, it remains crucial for many fields of application. It implies, in order to extract knowledge, to better understand the nature of the data, its evolution or the many complex relationships it may contain. Information visualization is about visual and interactive representation methods to help a user to extract knowledge. The work presented in this document takes place in this context. At first, we are interested in the visualization of large hierarchical time series. After analyzing the different existing approaches, we present the MultiStream system for visualizing, exploring and comparing the evolution of the series organized into a hierarchical structure. We illustrate its use by two examples: emotions expressed in social media and the evolution of musical genres. In a second time, we tackle the problem of complex data modeled in the form of multilayer graphs (different types of edges can connect the nodes). More specifically, we are interested in the visual querying of large graphs and we present VERTIGo, a system which makes it possible to build queries, to launch them on a specific engine, to visualize/explore the results at different levels of details and to suggest new query extensions. We illustrate its use with a graph of co-authors from different communities

APA, Harvard, Vancouver, ISO, and other styles

16

Pech, Palacio Manuel Alfredo. "Spatial data modeling and mining using a graph-based representation." Lyon, INSA, 2005. http://theses.insa-lyon.fr/publication/2005ISAL0118/these.pdf.

Full text

Abstract:

Est proposé un unique modèle basé sur des graphes pour représenter des données spatiales, les données non-spatiales et les relations entre les objets spatiaux. Ainsi un graphe est généré à partir de ces trois éléments. On considère que l'outil de fouille de données basé sur les graphes peut découvrir des patterns incluant ces trois éléments, selon trois types de relation spatiale (topologique, cardinale et de distance). Dans notre modèle, les données spatiales, non-spatiales (attributs non-spatiaux), et les relations spatiales représentent une collections d'un ou plusieurs graphes orientés. Les sommets représentent soit les objets spatiaux, soit les relations spatiales entre deux objets spatiaux, ou les attributs non-spatiaux. De plus, un sommet peut représenter soit un attribut, soit le nom d'une relation spatiale. Les noms des attributs peuvent référencer des objets spatiaux ou non-spatiaux. Les arcs orientés sont utilisés pour représenter des informations directionnelles sur les relations entre les éléments, et pour décrire les attributs des objets. On a adopté SUBDUE comme un outil de fouille de graphes. Une caractéristique particulière dite de recouvrement joue un rôle important dans la découverte de patterns. Cependant, elle peut-être implémentée pour recouvrir la totalité du graphe, ou bien ne considérer aucun sommet. En conséquence, nous proposons une troisième piste nommée recouvrement limité, laquelle donne à l'utilisateur la capacité de choisir le recouvrement. On analyse directement trois caractéristiques de l'algorithme proposé, la réduction de l'espace de recherche, la réduction du temps de calcul, et la découverte de patterns grâce à ce type de recouvrement
We propose a unique graph-based model to represent spatial data, non-spatial data and the spatial relations among spatial objects. We will generate datasets composed of graphs with a set of these three elements. We consider that by mining a dataset with these characteristics a graph-based mining tool can search patterns involving all these elements at the same time improving the results of the spatial analysis task. A significant characteristic of spatial data is that the attributes of the neighbors of an object may have an influence on the object itself. So, we propose to include in the model three relationship types (topological, orientation, and distance relations). In the model the spatial data (i. E. Spatial objects), non-spatial data (i. E. Non-spatial attributes), and spatial relations are represented as a collection of one or more directed graphs. A directed graph contains a collection of vertices and edges representing all these elements. Vertices represent either spatial objects, spatial relations between two spatial objects (binary relation), or non-spatial attributes describing the spatial objects. Edges represent a link between two vertices of any type. According to the type of vertices that an edge joins, it can represent either an attribute name or a spatial relation name. The attribute name can refer to a spatial object or a non-spatial entity. We use directed edges to represent directional information of relations among elements (i. E. Object x touches object y) and to describe attributes about objects (i. E. Object x has attribute z). We propose to adopt the Subdue system, a general graph-based data mining system developed at the University of Texas at Arlington, as our mining tool. A special feature named overlap has a primary role in the substructures discovery process and consequently a direct impact over the generated results. However, it is currently implemented in an orthodox way: all or nothing. Therefore, we propose a third approach: limited overlap, which gives the user the capability to set over which vertices the overlap will be allowed. We visualize directly three motivations issues to propose the implementation of the new algorithm: search space reduction, processing time reduction, and specialized overlapping pattern oriented search

APA, Harvard, Vancouver, ISO, and other styles

17

Castets, Mathieu. "Pavages réguliers et modélisation des dynamiques spatiales à base de graphes d'interaction : conception, implémentation, application." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS241/document.

Full text

Abstract:

La modélisation et la simulation de dynamiques spatiales, en particulier pour l'étude de l'évolution de paysages ou de problématiques environnementales pose la question de l'intégration des différentes formes de représentation de l'espace au sein d'un même modèle. Ocelet est une approche de modélisation de dynamiques spatiales basée sur le concept original de graphe d'interaction. Le graphe porte à la fois la structure d'une relation entre entités d’un modèle et la sémantique décrivant son évolution. Les relations entre entités spatiales sont ici traduites en graphes d'interactions et ce sont ces graphes que l'on fait évoluer lors d'une simulation. Les concepts à la base d'Ocelet peuvent potentiellement manipuler les deux formes de représentation spatiale connues, celle aux contours définis (format vecteur) ou la discrétisation en grille régulière (format raster). Le format vecteur est déjà intégré dans la première version d'Ocelet. L'intégration du format raster et la combinaison des deux restaient à étudier et à réaliser. L'objectif de la thèse est d'abord étudier les problématiques liées à l'intégration des champs continus et leur représentation discrétisée en pavage régulier, à la fois dans le langage Ocelet et dans les concepts sur lesquels il repose. Il a fallu notamment prendre en compte les aspects dynamiques de cette intégration, et d'étudier les transitions entre données géographiques de différentes formes et graphe d'interactions à l'aide de concepts formalisés. Il s'est agi ensuite de réaliser l'implémentation de ces concepts dans la plateforme de modélisation Ocelet, en adaptant à la fois son compilateur et son moteur d'exécution. Enfin, ces nouveaux concepts et outils ont été mis à l'épreuve dans trois cas d'application très différents : deux modèles sur l’île de la Réunion, le premier simulant le ruissellement dans le bassin versant de la Ravine Saint Gilles s'écoulant vers la Côte Ouest de l'île, l’autre simulant la diffusion de plantes invasives dans les plaines des hauts à l'intérieur du Parc National de La Réunion. Le dernier cas décrit la spatialisation d'un modèle de culture et est appliqué ici pour simuler les rendements de cultures céréalières sur l’ensemble de l’Afrique de l’Ouest, dans le contexte d'un système d'alerte précoce de suivi des cultures à l'échelle régionale
The modelling and simulation of spatial dynamics, particularly for studying landscape changes or environmental issues, raises the question of integrating different forms of spatial representation within the same model. Ocelet is an approach for modelling spatial dynamics based on the original concept of interaction graph. Such a graph holds both the structure of a relation between entities of a model and the semantics describing its evolution. The relationships between spatial entities are here translated into interaction graphs and these graphs are made to evolve during a simulation. The concepts on which Ocelet is based can potentially handle two known forms of spatial representation: shapes with contours (vector format) or regular grid cells (raster). The vector format is already integrated in the first version of Ocelet. The integration of raster and the combination of the two remained to be studied and carried out. The aim of the thesis is to first study the issues related to the integration of continuous fields and their representation by regular tiling, both in the Ocelet language and the concepts on which it is based. The dynamic aspects of this integration had to be taken into account and transitions between different forms of geographic data and interaction graphs had to be studied in the light of the concepts formalized. The concepts were then implemented in the Ocelet modelling platform, with the adaptation of both its compiler and runtime. Finally, these new concepts and tools were tested in three very different cases: two models on Reunion Island, the first simulating runoff in Ravine Saint Gilles watershed in the West Coast of the island, the other simulating the spread of invasive plants in the high plains inside the Reunion National Park. The last case describes the spatialisation of a crop model and is applied here to simulate the cereal crop yields in West Africa, in the context of an early warning system for regional crop monitoring

APA, Harvard, Vancouver, ISO, and other styles

18

Hiot, Nicolas. "Construction automatique de bases de données pour le domaine médical : Intégration de texte et maintien de la cohérence." Electronic Thesis or Diss., Orléans, 2024. http://www.theses.fr/2024ORLE1026.

Full text

Abstract:

La construction automatique de bases de données dans le domaine médical représente un défi majeur pour garantir une gestion efficace de l'information et faciliter les prises de décision. Ce projet de recherche se concentre sur l'utilisation des bases de données graphes, une approche qui offre une représentation dynamique et une interrogation efficace des données et en particulier de leur topologie. Notre projet explore la convergence entre les bases de données et le traitement automatique du langage, avec deux objectifs centraux. Tout d'abord, notre attention se porte sur le maintien de la cohérence au sein des bases de données graphes lors des mises à jour, en particulier avec des données incomplètes et des règles métiers spécifiques. Maintenir la cohérence lors des mises à jour permet de garantir un niveau de qualité de données uniforme pour tous les utilisateurs et de faciliter l'analyse. Dans un monde en constante évolution, nous donnons la priorité aux mises à jour, qui peuvent impliquer des modifications de l'instance pour accueillir de nouvelles informations. Mais comment gérer efficacement ces mises à jour successives au sein d'un système de gestion de base de données graphes ? Dans un second temps, nous nous concentrons sur l'intégration des informations extraites de documents textuels, une source de données majeure dans le domaine médical. En particulier, nous examinons les cas cliniques et de pharmacovigilance, un domaine crucial pour identifier les risques et les effets indésirables associés à l'utilisation des médicaments. Comment détecter l'information dans les textes ? Comment intégrer ces données non structurées de manière efficace dans une base de données graphe ? Comment les structurer automatiquement ? Et enfin, qu'est-ce qu'une structure valide dans ce contexte ? On s'intéresse en particulier à favoriser la recherche reproductible en adoptant une démarche transparente et documentée pour permettre la vérification et la validation indépendante de nos résultats
The automatic construction of databases in the medical field represents a major challenge for guaranteeing efficient information management and facilitating decision-making. This research project focuses on the use of graph databases, an approach that offers dynamic representation and efficient querying of data and its topology. Our project explores the convergence between databases and automatic language processing, with two central objectives. In one hand, our focus is on maintaining consistency within graph databases during updates, particularly with incomplete data and specific business rules. Maintaining consistency during updates ensures a uniform level of data quality for all users and facilitates analysis. In a world of constant change, we give priority to updates, which may involve modifying the instance to accommodate new information. But how can we effectively manage these successive updates within a graph database management system? In a second hand, we focus on the integration of information extracted from text documents, a major source of data in the medical field. In particular, we are looking at clinical cases and pharmacovigilance, a crucial area for identifying the risks and adverse effects associated with the use of drugs. But, how can we detect information in texts? How can this unstructured data be efficiently integrated into a graph database? How can it be structured automatically? And finally, what is a valid structure in this context? We are particularly interested in encouraging reproducible research by adopting a transparent and documented approach to enable independent verification and validation of our results

APA, Harvard, Vancouver, ISO, and other styles

19

Acosta, Francisco. "Les arbres balances : spécification, performances et contrôle de concurrence." Montpellier 2, 1991. http://www.theses.fr/1991MON20201.

Full text

Abstract:

Dans le cadre de la gestion d'une base de donnees, nous etudions les problemes relatifs a la specification, aux performances des operations d'acces et au partage des donnees. Dans la premiere partie de l'etude nous introduisons les notions de base pour la specification de donnees et nous etudions les methodes classiques d'acces aux donnees; cette etude montre que les arbres balances (les b-arbres et leurs variations) sont une solution interessante pour la gestion de donnees stockees sur disque. Nous etudions ensuite la specification algebrique des arbres balances, afin de degager leurs caracteristiques intrinseques. Nous definissons les classes b(k, m) des b-arbres, dans lesquelles les parametres k et m permettent de controler de facon simple le rapport espace-temps de leur complexite. Cette proposition generalise, a l'aide du parametre k, les variations les plus classiques de ces arbres, telles que les arbres b*. Dans la seconde partie de l'etude, nous exposons les concepts de base du controle de concurrence. Nous etudions par la suite le modele d'execution concurrente sur les arbres de recherche de shasha et goodman, puis les methodes de controle de concurrence pour ces arbres. Finalement, nous degageons les principes d'une methode originale dans laquelle le controle s'exerce au meilleur moment de l'execution des operations

APA, Harvard, Vancouver, ISO, and other styles

20

David, Romain. "De la conception d'un système d'observation à large échelle au déploiement et à l'exploitation de son système d'information : application à l'observation des habitats coralligènes et à la colonisation de récifs artificiels (ARMS)." Thesis, Aix-Marseille, 2018. http://www.theses.fr/2018AIXM0215/document.

Full text

Abstract:

Dans le domaine marin, des protocoles d’observation développés dans de nombreux cadres produisent un grand volume de données hétérogènes, difficiles à agréger et à utiliser. Ce travail propose i) des méthodes, protocoles et recommandations pour construire et/ou soutenir la mise en place de réseaux de suivis multi-usagers,) des utilisations novatrices des données.Deux cas d’étude ont été choisis : les habitats coralligènes à l’échelle de la Méditerranée et la colonisation de récifs artificiels dans différentes mers régionales.L’expérimentation à large échelle se base sur des méthodes de mesures les plus simples possibles, décrites très explicitement dans des termes standardisés, sur des opérateurs intercalibrés et une méthode de traitement des données. Un mécanisme de couplage de données de différentes origines reposant sur la requalification des facteurs descriptifs hétérogènes et une méthode d’analyse et de fouille de données basé sur la théorie des graphes sont proposées
In the marine domain, observation protocols developed in many settings produce a large volume of heterogeneous data that are difficult to aggregate and use. This work proposes to develop i) methods, protocols and recommendations to build and / or support the establishment of multi-user monitoring networks, ii) innovative uses of data.Two case studies were chosen: coralligenous habitats at the Mediterranean scale and the colonisation of artificial reefs in different regional seas.Large-scale experimentation is based on the simplest possible measurement methods, described very explicitly in standardised terms, on intercalibrated operators and a method of data processing. A mechanism for coupling data from different origins based on the requalification of heterogeneous descriptive factors and a method for analysis and data mining based on graph theory is also proposed

APA, Harvard, Vancouver, ISO, and other styles

21

Kamal-Idrissi, Assia. "Optimisation des réseaux aériens : analyse et sélection de nouveaux marchés." Thesis, Université Côte d'Azur, 2020. https://tel.archives-ouvertes.fr/tel-03177526.

Full text

Abstract:

Les problèmes rencontrés dans l’industrie aérienne sont divers et compliqués. Leur résolution réduit les coûts et maximise les revenus tout en améliorant la qualité de service, par exemple, en capturant de nouveaux passagers sur des vols existants ou sur de nouveaux marchés. La sélection des nouveaux marchés permet de définir la structure du réseau à opérer, et d’estimer le flux des passagers, leurs choix d’itinéraires ainsi que les revenus et les coûts impliqués par ces décisions. Nos travaux concernent l’amélioration du calculateur de parts de marché dans l’application PlanetOptim de la startup Milanamos. Cet outil permet aux décideurs des aéroports et des compagnies aériennes d’analyser l’historique des données et de simuler des marchés afin de trouver une opportunité économique. Ces travaux sont orientés vers les niveaux de décision stratégiques et tactiques. Grâce à une analyse poussée des données, le réseau aérien a pu être modélisé par un graphe indépendant du temps stocké dans une base de données orientée grapheNeo4j. Nous avons alors défini le Flight Radius Problem dont la résolution permet de déterminer un sous-réseau centré autour d’un vol pour lequel les parts de marchés du vol sont non négligeables. Plusieurs méthodes de résolution ont été proposées basées sur des requêtes ou des algorithmes de plus courts chemins couplés à des techniques d’accélération et de parallélisme. Nos algorithmes identifient rapidement un ensemble de marchés prometteurs centré sur un vol. L’intégration de la théorie des graphes dans les bases de données ouvre de nouvelles perspectives pour l’analyse et la compréhension de grands réseaux
In the airline industry, problems are various and complicated. Solving these problems aims at reducing costs and maximizing revenues. Revenues can be increased while improving the quality of service. For example, one way is to catch new passengers on existing flight connections or on new markets. The selection of new markets consists in determining network structure to operate, and to estimate passengers flow, their choice of itineraries as well as incomes and costs incurred by these decisions. Our research is about improving market planner engine. Milanamos develops an application for the analysis and simulation of markets intended for air-ports and airlines. It offers its customers a decision-making tool to analyze historical data andto simulate markets in order to find an economic opportunity. This project takes place earlierin the decision process. Thanks to a thorough data analysis, the air transport network could be modelized as a time-independent graph and stored in the Neo4j graph database. We then defined the Flight Radius problem which resolution allows to determine a sub-network centered around a flight for which market shares of the flight are meaningful. Several methods have beenproposed based on queries or on shortest path algorithms combined with acceleration and parallelism techniques. Our algorithms identify some new markets for a flight. Combining graph theory with databases offers new opportunities for analyzing and studying large networks

APA, Harvard, Vancouver, ISO, and other styles

22

Delanaux, Rémy. "Intégration de données liées respectueuse de la confidentialité." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1303.

Full text

Abstract:

La confidentialité des données personnelles est un souci majeur et un problème peu étudié pour la publication de données dans le Web des données ouvertes (ou LOD cloud, pour Linked Open Data cloud) . Ce nuage formé par le LOD est un réseau d'ensembles de données interconnectés et accessibles publiquement sous la forme de graphes de données modélisés dans le format RDF, et interrogés via des requêtes écrites dans le langage SPARQL. Ce cadre très standardisé est très utilisé de nos jours par des organismes publics et des entreprises. Mais certains acteurs notamment du secteur privé sont toujours réticents à la publication de leurs données, découragés par des soucis potentiels de confidentialité. Pour pallier cela, nous présentons et développons un cadre formel déclaratif pour la publication de données liées respectant la confidentialité, dans lequel les contraintes de confidentialité et d'utilité des données sont spécifiées sous forme de politiques (des ensembles de requêtes SPARQL). Cette approche est indépendante des données et du graphe considéré, et consiste en l'analyse statique d'une politique de confidentialité et d'une politique d'utilité pour déterminer des séquences d'opérations d'anonymization à appliquer à n'importe quel graphe RDF pour satisfaire les politiques fournies. Nous démontrons la sûreté de nos algorithmes et leur efficacité en terme de performance via une étude expérimentale. Un autre aspect à prendre en compte est qu'un nouveau graphe publié dans le nuage LOD est évidemment exposé à des failles de confidentialité car il peut être relié à des données déjà publiées dans d'autres données liées. Dans le second volet de cette thèse, nous nous concentrons donc sur le problème de construction d'anonymisations *sûres* d'un graphe RDF garantissant que relier le graphe anonymisé à un graphe externe quelconque ne causera pas de brèche de confidentialité. En prenant un ensemble de requêtes de confidentialité en entrée, nous étudions le problème de sûreté indépendamment des données du graphe, et la construction d'une séquence d'opérations d'anonymisation permettant d'assurer cette sûreté. Nous détaillons des conditions suffisantes sous lesquelles une instance d'anonymisation est sûre pour une certaine politique de confidentialité fournie. Par ailleurs, nous montrons que nos algorithmes sont robustes même en présence de liens de type sameAs (liens d'égalité entre entités en RDF), qu'ils soient explicites ou inférés par de la connaissance externe. Enfin, nous évaluons l'impact de cette contribution assurant la sûreté de données en la testant sur divers graphes. Nous étudions notamment la performance de cette solution et la perte d'utilité causée par nos algorithmes sur des données RDF réelles comme synthétiques. Nous étudions d'abord les diverses mesures d'utilité existantes et nous en choisissons afin de comparer le graphe original et son pendant anonymisé. Nous définissons également une méthode pour générer de nouvelles politiques de confidentialité à partir d'une politique de référence, via des modifications incrémentales. Nous étudions le comportement de notre contribution sur 4 graphes judicieusement choisis et nous montrons que notre approche est efficace avec un temps très faible même sur de gros graphes (plusieurs millions de triplets). Cette approche est graduelle : le plus spécifique est la politique de confidentialité, le plus faible est son impact sur les données. Pour conclure, nous montrons via différentes métriques structurelles (adaptées aux graphes) que nos algorithmes ne sont que peu destructeurs, et cela même quand les politiques de confidentialité couvrent une grosse partie du graphe
Individual privacy is a major and largely unexplored concern when publishing new datasets in the context of Linked Open Data (LOD). The LOD cloud forms a network of interconnected and publicly accessible datasets in the form of graph databases modeled using the RDF format and queried using the SPARQL language. This heavily standardized context is nowadays extensively used by academics, public institutions and some private organizations to make their data available. Yet, some industrial and private actors may be discouraged by potential privacy issues. To this end, we introduce and develop a declarative framework for privacy-preserving Linked Data publishing in which privacy and utility constraints are specified as policies, that is sets of SPARQL queries. Our approach is data-independent and only inspects the privacy and utility policies in order to determine the sequence of anonymization operations applicable to any graph instance for satisfying the policies. We prove the soundness of our algorithms and gauge their performance through experimental analysis. Another aspect to take into account is that a new dataset published to the LOD cloud is indeed exposed to privacy breaches due to the possible linkage to objects already existing in the other LOD datasets. In the second part of this thesis, we thus focus on the problem of building safe anonymizations of an RDF graph to guarantee that linking the anonymized graph with any external RDF graph will not cause privacy breaches. Given a set of privacy queries as input, we study the data-independent safety problem and the sequence of anonymization operations necessary to enforce it. We provide sufficient conditions under which an anonymization instance is safe given a set of privacy queries. Additionally, we show that our algorithms are robust in the presence of sameAs links that can be explicit or inferred by additional knowledge. To conclude, we evaluate the impact of this safety-preserving solution on given input graphs through experiments. We focus on the performance and the utility loss of this anonymization framework on both real-world and artificial data. We first discuss and select utility measures to compare the original graph to its anonymized counterpart, then define a method to generate new privacy policies from a reference one by inserting incremental modifications. We study the behavior of the framework on four carefully selected RDF graphs. We show that our anonymization technique is effective with reasonable runtime on quite large graphs (several million triples) and is gradual: the more specific the privacy policy is, the lesser its impact is. Finally, using structural graph-based metrics, we show that our algorithms are not very destructive even when privacy policies cover a large part of the graph. By designing a simple and efficient way to ensure privacy and utility in plausible usages of RDF graphs, this new approach suggests many extensions and in the long run more work on privacy-preserving data publishing in the context of Linked Open Data

APA, Harvard, Vancouver, ISO, and other styles

23

Cori, Marcel. "Modèles pour la représentation et l'interrogation de données textuelles et de connaissances." Paris 7, 1987. http://www.theses.fr/1987PA077047.

Full text

Abstract:

Ces modèles combinent à des réseaux sémantiques des bases de connaissances formées de règles. Les données sont représentées par des graphes sans circuit, ordonnés ou semi-ordonnés, ainsi que par des grammaires de graphes. La recherche de la réponse à une question se ramène à la recherche de morphismes entre structures. Les réprésentations sont construites automatiquement par l'appel à des règles de réécriture de graphes

APA, Harvard, Vancouver, ISO, and other styles

24

Lebrun, Justine. "Appariement inexact de graphes appliqué à la recherche d'image et d'objet 3D." Phd thesis, Université de Cergy Pontoise, 2011. http://tel.archives-ouvertes.fr/tel-00643534.

Full text

Abstract:

Les graphes sont des modèles de représentation qui permettent de modéliser un grand nombre de type de documents. Dans cette thèse, nous nous intéressons à leur utilisation pour la recherche dans des bases de données multimédia. Nous commençons par présenter la théorie autour des graphes ainsi qu'un aperçu des méthodes qui ont été proposées pour leur mise en correspondance. Puis, nous nous intéressons plus particulièrement à leur utilisation pour la reconnaissance des formes et l'indexation multimédia. Dans le but de répondre de la manière la plus générique possible aux différents problèmes de recherche, nous proposons de travailler dans le cadre des fonctions noyaux. Ce cadre permet de séparer les problèmes liées à la nature des documents de ceux apportés par les différents types de recherche. Ainsi, toute notre énergie est consacrée à la conception de fonctions de mise en correspondance, mais en gardant à l'esprit qu'elles doivent respecter un certain nombre de propriétés mathématiques. Dans ce cadre, nous proposons de nouvelles solutions qui permettent de mieux répondre aux caractéristiques particulières des graphes issus de primitives et descripteurs visuels. Nous présentons aussi les algorithmes qui permettent d'évaluer rapidement ces fonctions. Enfin, nous présentons des expériences qui mettent en lumière ces différentes caractéristiques, ainsi que des expériences qui montrent les avantages qu'offrent nos modèles vis à vis de la littérature.

APA, Harvard, Vancouver, ISO, and other styles

25

Pennerath, Frédéric. "Méthodes d'extraction de connaissances à partir de données modélisables par des graphes : Application à des problèmes de synthèse organique." Phd thesis, Université Henri Poincaré - Nancy I, 2009. http://tel.archives-ouvertes.fr/tel-00436568.

Full text

Abstract:

Des millions de réactions chimiques sont décrites dans des bases de données sous la forme de transformations de graphes moléculaires. Cette thèse propose différentes méthodes de fouille de donnés pour extraire des motifs pertinents contenus dans ces graphes et ainsi aider les chimistes à améliorer leurs connaissances des réactions chimiques et des molécules. Ainsi on commence par montrer comment le problème central de la recherche des schémas de réactions fréquents peut se résoudre à l'aide de méthodes existantes de recherche de sous-graphes fréquents. L'introduction du modèle général des motifs les plus informatifs permet ensuite de restreindre l'analyse de ces motifs fréquents à un nombre réduit de motifs peu redondants et représentatifs des données. Si l'application du modèle aux bases de réactions permet d'identifier de grandes familles de réactions, le modèle est inadapté pour extraire les schémas caractéristiques de méthodes de synthèse (schémas CMS) dont la fréquence est trop faible. Afin de surmonter cet obstacle, est ensuite introduite une méthode de recherche heuristique fondée sur une contrainte d'intervalle entre graphes et adaptée à l'extraction de motifs de très faible fréquence. Cette méthode permet ainsi de déterminer à partir d'exemples de réactions et sous certaines conditions le schéma CMS sous-jacent à une réaction donnée. La même approche est ensuite utilisée pour traiter le problème de la classification supervisée de sommets ou d'arêtes fondée sur leurs environnements puis exploitée pour évaluer la formabilité des liaisons d'une molécule. Les résultats produits ont pu être analysés par des experts de la synthèse organique et sont très encourageants.

APA, Harvard, Vancouver, ISO, and other styles

26

Ngo, Duy Hoa. "Amélioration de l'alignement d'ontologies par les techniques d'apprentissage automatique, d'appariement de graphes et de recherche d'information." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2012. http://tel.archives-ouvertes.fr/tel-00767318.

Full text

Abstract:

Ces dernières années, les ontologies ont suscité de nombreux travaux dans le domaine du web sémantique. Elles sont utilisées pour fournir le vocabulaire sémantique permettant de rendre la connaissance du domaine disponible pour l'échange et l'interprétation au travers des systèmes d'information. Toutefois, en raison de la nature décentralisée du web sémantique, les ontologies sont très hétérogènes. Cette hétérogénéité provoque le problème de la variation de sens ou ambiguïté dans l'interprétation des entités et, par conséquent, elle empêche le partage des connaissances du domaine. L'alignement d'ontologies, qui a pour but la découverte des correspondances sémantiques entre des ontologies, devient une tâche cruciale pour résoudre ce problème d'hétérogénéité dans les applications du web sémantique. Les principaux défis dans le domaine de l'alignement d'ontologies ont été décrits dans des études récentes. Parmi eux, la sélection de mesures de similarité appropriées ainsi que le réglage de la configuration de leur combinaison sont connus pour être des problèmes fondamentaux que la communauté doit traiter. En outre, la vérification de la cohérence sémantique des correspondances est connue pour être une tâche importante. Par ailleurs, la difficulté du problème augmente avec la taille des ontologies. Pour faire face à ces défis, nous proposons dans cette thèse une nouvelle approche, qui combine différentes techniques issues des domaines de l'apprentissage automatique, d'appariement de graphes et de recherche d'information en vue d'améliorer la qualité de l'alignement d'ontologies. En effet, nous utilisons des techniques de recherche d'information pour concevoir de nouvelles mesures de similarité efficaces afin de comparer les étiquettes et les profils d'entités de contexte au niveau des entités. Nous appliquons également une méthode d'appariement de graphes appelée propagation de similarité au niveau de la structure qui découvre effectivement des correspondances en exploitant des informations structurelles des entités. Pour combiner les mesures de similarité au niveau des entités, nous transformons la tâche de l'alignement d'ontologie en une tâche de classification de l'apprentissage automatique. Par ailleurs, nous proposons une méthode dynamique de la somme pondérée pour combiner automatiquement les correspondances obtenues au niveau des entités et celles obtenues au niveau de la structure. Afin d'écarter les correspondances incohérentes, nous avons conçu une nouvelle méthode de filtrage sémantique. Enfin, pour traiter le problème de l'alignement d'ontologies à large échelle, nous proposons deux méthodes de sélection des candidats pour réduire l'espace de calcul. Toutes ces contributions ont été mises en œuvre dans un prototype nommé YAM++. Pour évaluer notre approche, nous avons utilisé des données du banc d'essai de la compétition OAEI : Benchmark, Conference, Multifarm, Anatomy, Library and Large Biomedical Ontologies. Les résultats expérimentaux montrent que les méthodes proposées sont très efficaces. De plus, en comparaison avec les autres participants à la compétition OAEI, YAM++ a montré sa compétitivité et a acquis une position de haut rang.

APA, Harvard, Vancouver, ISO, and other styles

27

Oshurko, Ievgeniia. "Knowledge representation and curation in hierarchies of graphs." Thesis, Lyon, 2020. http://www.theses.fr/2020LYSEN024.

Full text

Abstract:

L'extraction automatique des intuitions et la construction de modèles computationnels à partir de connaissances sur des systèmes complexes repose largement sur le choix d'une représentation appropriée. Ce travail s'efforce de construire un cadre adapté pour la représentation de connaissances fragmentées sur des systèmes complexes et sa curation semi-automatisé.Un système de représentation des connaissances basé sur des hiérarchies de graphes liés à l'aide d'homomorphismes est proposé. Les graphes individuels représentent des fragments de connaissances distincts et les homomorphismes permettent de relier ces fragments. Nous nous concentrons sur la conception de mécanismes mathématiques,basés sur des approches algébriques de la réécriture de graphes, pour la transformation de graphes individuels dans des hiérarchies qui maintient des relations cohérentes entre eux.De tels mécanismes fournissent une piste d'audit transparente, ainsi qu'une infrastructure pour maintenir plusieurs versions des connaissances.La théorie développée est appliquée à la conception des schémas pour les bases de données orientée graphe qui fournissent des capacités de co-évolution schémas-données.Ensuite, cette théorie est utilisée dans la construction du cadre KAMI, qui permet la curation des connaissances sur la signalisation dans les cellules. KAMI propose des mécanismes pour une agrégation semi-automatisée de faits individuels sur les interactions protéine-protéine en corpus de connaissances, la réutilisation de ces connaissances pour l'instanciation de modèles de signalisation dans différents contextes cellulaires et la génération de modèles exécutables basés sur des règles
The task of automatically extracting insights or building computational models fromknowledge on complex systems greatly relies on the choice of appropriate representation.This work makes an effort towards building a framework suitable for representation offragmented knowledge on complex systems and its semi-automated curation---continuouscollation, integration, annotation and revision.We propose a knowledge representation system based on hierarchies of graphs relatedwith graph homomorphisms. Individual graphs situated in such hierarchies representdistinct fragments of knowledge and the homomorphisms allow relating these fragments.Their graphical structure can be used efficiently to express entities and their relations. Wefocus on the design of mathematical mechanisms, based on algebraic approaches to graphrewriting, for transformation of individual graphs in hierarchies that maintain consistentrelations between them. Such mechanisms provide a transparent audit trail, as well as aninfrastructure for maintaining multiple versions of knowledge.We describe how the developed theory can be used for building schema-aware graphdatabases that provide schema-data co-evolution capabilities. The proposed knowledgerepresentation framework is used to build the KAMI (Knowledge Aggregation and ModelInstantiation) framework for curation of cellular signalling knowledge. The frameworkallows for semi-automated aggregation of individual facts on protein-protein interactionsinto knowledge corpora, reuse of this knowledge for instantiation of signalling models indifferent cellular contexts and generation of executable rule-based models

APA, Harvard, Vancouver, ISO, and other styles

28

Abbaci, Katia. "Contribution à l'interrogation flexible et personnalisée d'objets complexes modélisés par des graphes." Thesis, Rennes 1, 2013. http://www.theses.fr/2013REN1S105/document.

Full text

Abstract:

Plusieurs domaines d'application traitent des objets et des données complexes dont la structure et la sémantique de leurs composants sont des informations importantes pour leur manipulation et leur exploitation. La structure de graphe a été bien souvent adoptée, comme modèles de représentation, dans ces domaines. Elle permet de véhiculer un maximum d'informations, liées à la structure, la sémantique et au comportement de ces objets, nécessaires pour assurer une meilleure représentation et une manipulation eﬃcace. Ainsi, lors d'une comparaison entre deux objets complexes, l'opération d'appariement est appliquée entre les graphes les modélisant. Nous nous sommes intéressés dans cette thèse à l'appariement approximatif qui permet de sélectionner les graphes les plus similaires au graphe d'une requête. L'objectif de notre travail est de contribuer à l'interrogation ﬂexible et personnalisée d'objets complexes modélisés sous forme de graphes pour identiﬁer les graphes les plus pertinents aux besoins de l'utilisateur, exprimés d'une manière partielle ou imprécise. Dans un premier temps, nous avons proposé un cadre de sélection de services Web modélisés sous forme de graphes qui permet (i) d'améliorer le processus d'appariement en intégrant les préférences des utilisateurs et l'aspect structurel des graphes comparés, et (ii) de retourner les services les plus pertinents. Une deuxième méthode d'évaluation de requêtes de recherche de graphes par similarité a également été présentée pour calculer le skyline de graphes d'une requête utilisateur en tenant compte de plusieurs mesures de distance de graphes. Enﬁn, des approches de raﬃnement ont été déﬁnies pour réduire la taille, souvent importante, du skyline. Elles ont pour but d'identiﬁer et d'ordonner les points skyline qui répondent le mieux à la requête de l'utilisateur
Several application domains deal with complex objects whose structure and semantics of their components are crucial for their handling. For this, graph structure has been adopted, as a model of representation, in these areas to capture a maximum of information, related to the structure, semantics and behavior of such objects, necessary for eﬀective representation and processing. Thus, when comparing two complex objects, a matching technique is applied between their graph structures. In this thesis, we are interested in approximate matching techniques which constitute suitable tools to automatically ﬁnd and select the most similar graphs to user graph query. The aim of our work is to develop methods to personalized and ﬂexible querying of repositories of complex objects modeled thanks to graphs and then to return the graphs results that ﬁt best the users ’needs, often expressed partially and in an imprecise way. In a ﬁrst time, we propose a ﬂexible approach for Web service retrieval that relies both on preference satisﬁability and structural similarity between process model graphs. This approach allows (i) to improve the matching process by integrating user preferences and the graph structural aspect, and (ii) to return the most relevant services. A second method for evaluating graph similarity queries is also presented. It retrieves graph similarity skyline of a user query by considering a vector of several graph distance measures instead of a single measure. Thus, graphs which are maximally similar to graph query are returned in an ordered way. Finally, reﬁnement methods have been developed to reduce the size of the skyline when it is of a signiﬁcant size. They aim to identify and order skyline points that match best the user query

APA, Harvard, Vancouver, ISO, and other styles

29

Groz, Benoît. "XML security views : queries, updates and schemas." Thesis, Lille 1, 2012. http://www.theses.fr/2012LIL10143/document.

Full text

Abstract:

Les évolutions technologiques ont consacré l'émergence des services web et du stockage des données en ligne, en complément des bases de données traditionnelles. Ces évolutions facilitent l'accès aux données, mais en contrepartie soulèvent de nouvelles problématiques de sécurité. La mise en œuvre de politiques de contrôle d'accès appropriées est une des approches permettant de réduire ces risques. Nous étudions ici les politiques de contrôle d'accès au niveau d'un document XML, politiques que nous modélisons par des vues de sécurité XML (non matérialisées) à l'instar de Fan et al. Ces vues peuvent être représentées facilement par des alignements d'arbres grâce à l'absence d'opérateurs arithmétiques ou de restructuration. Notre objectif est par conséquent d'examiner comment manipuler efficacement ce type de vues, à l'aide des méthodes formelles, et plus particulièrement des techniques de réécriture de requêtes et la théorie des automates d'arbres. Trois directions principales ont orienté nos recherches: nous avons tout d'abord élaboré des algorithmes pour évaluer l'expressivité d'une vue, en fonction des requêtes qui peuvent être exprimées à travers cette vue. Il s'avère que l'on ne peut décider en général si une vue permet d'exprimer une requête particulière, mais cela devient possible lorsque la vue satisfait des hypothèses générales. En second lieu, nous avons considéré les problèmes soulevés par la mises à jour du document à travers une vue. Enfin, nous proposons des solutions pour construire automatiquement un schéma de la vue. En particulier, nous présentons différentes techniques pour représenter de façon approchée l'ensemble des documents au moyen d'une DTD
The evolution of web technologies and social trends fostered a shift from traditional enterprise databases to web services and online data. While making data more readily available to users, this evolution also raises additional security concerns regarding the privacy of users and more generally the disclosure of sensitive information. The implementation of appropriate access control models is one of the approaches to mitigate the threat. We investigate an access control model based on (non-materialized) XML views, as presented among others by Fan et al. The simplicity of such views, and in particular the absence of arithmetic features and restructuring, facilitates their modelization with tree alignments. Our objective is therefore to investigate how to manipulate efficiently such views, using formal methods, and especially query rewriting and tree automata. Our research follows essentially three directions: we first develop new algorithms to assess the expressivity of views, in terms of determinacy, query rewriting and certain answers. We show that those problems, although undecidable in our most general setting, can be decided under reasonable restrictions. Then we address the problem of handling updates in the security view framework. And last, we investigate the classical issues raised by schemata, focusing on the specific "determinism'' requirements of DTDs and XML Schemata. In particular, we survey some techniques to approximate the set of all possible view documents with a DTD, and we provide new algorithms to check if the content models of a DTD are deterministic

APA, Harvard, Vancouver, ISO, and other styles

30

Vigny, Alexandre. "Query enumeration and nowhere dense graphs." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC211.

Full text

Abstract:

Les travaux présentés dans ma thèse se situent à l’interface entre complexité, algorithmique et logique. Plus particulièrement, on s’intéresse à la complexité d'évaluation de requêtes.Plus précisément, étant donné G un graphe fini. Une requête q définit un sous ensemble de k-uplets de sommets de G que l'on note q(G). On appelle k l'arité de q et on se essaye alors d'effectuer efficacement les taches suivantes :1) décider si l'ensemble q(G) est vide ou non.2) décider si un k-uplet donné appartient à l'ensemble des solutions q(G).3) calculer le nombre de solutions.4) énumérer les éléments de q(G).En ce qui concerne la 4ème tache, un algorithme qui va énumérer les solutions sera décomposé en deux parties. La première est appelé le pré-calcul et sert à préparer l’énumération. Idéalement cette étape de requière qu’un temps linéaire en la taille du graphe. La deuxième étape est ensuite l’énumération des solutions. Le temps nécessaire pour obtenir une nouvelle solution est appelé le délai. Idéalement on souhaite que le délai de dépende pas de la taille du graphes mais uniquement de la taille de la requête. On parle alors d’énumération à délai constant après pré-calcul linéaire.Au début de cette thèse, une grand part des interrogations au sujet des classes de graphes pour lesquelles une énumération à délai constant serait possible semblait se trouver au niveau des classes de graphes nulle-part dense. Le résultat principal de cette thèse est de montrer qu’il est possible d’énumérer les solutions des requêtes du premier ordre sur les graphes nulle-part dense avec un délai constant après un pré-calcul pseudo linéaire
The topic of my thesis lies between complexity, algorithmic and logic. In particular, we are interested in the complexity of evaluating query.More precisely, given G a finite graph. A query q defines a subset of k-tuples of vertices of G that we note q(G). We call k the arity of q and we then try to efficiently perform the following tasks:1) decide whether the set q G) is empty.2) decide whether a given k-tuplet belongs to the set of solutions q(G).3) calculate the number of solutions.4) enumerate the elements of q(G).Regarding the 4th task, an algorithm that will enumerate the solutions can be decomposed into two steps. The first is called preprocessing and is used to prepare the enumeration. Ideally this step only requires a time linear in the size of the graph. The second step is the enumeration properly speaking. The time needed to get a new solution is called the delay. Ideally we want the delay to not depend on the size of the graph but only on the size of the query. We then talk about constant delay enumeration after linear preprocessing.At the beginning of this thesis, a large part of the interrogations about classes of graphs for which a constant delay enumeration is possible seemed to be located around the classes of nowhere dense graphs

APA, Harvard, Vancouver, ISO, and other styles

31

Pradel, Camille. "D'un langage de haut niveau à des requêtes graphes permettant d'interroger le web sémantique." Toulouse 3, 2013. http://thesesups.ups-tlse.fr/2237/.

Full text

Abstract:

Les modèles graphiques sont de bons candidats pour la représentation de connaissances sur le Web, où tout est graphes : du graphe de machines connectées via Internet au "Giant Global Graph" de Tim Berners-Lee, en passant par les triplets RDF et les ontologies. Dans ce contexte, le problème crucial de l'interrogation ontologique est le suivant : est-ce qu'une base de connaissances composée d'une partie terminologique et d'une partie assertionnelle implique la requête, autrement dit, existe-t-il une réponse à la question ? Ces dernières années, des logiques de description ont été proposées dans lesquelles l'expressivité de l'ontologie est réduite de façon à rendre l'interrogation calculable (familles DL-Lite et EL). OWL 2 restreint OWL-DL dans ce sens en se fondant sur ces familles. Nous nous inscrivons dans le contexte d'utilisation de formalismes graphiques pour la représentation (RDF, RDFS et OWL) et l'interrogation (SPARQL) de connaissances. Alors que les langages d'interrogation fondés sur des graphes sont présentés par leurs promoteurs comme étant naturels et intuitifs, les utilisateurs ne pensent pas leurs requêtes en termes de graphes. Les utilisateurs souhaitent des langages simples, proches de la langue naturelle, voire limités à des mots-clés. Nous proposons de définir un moyen générique permettant de transformer une requête exprimée en langue naturelle vers une requête exprimée dans le langage de graphe SPARQL, à l'aide de patrons de requêtes. Le début de ce travail coïncide avec les actions actuelles du W3C visant à préparer une nouvelle version de RDF, ainsi qu'avec le processus de standardisation de SPARQL 1. 1 gérant l'implication dans les requêtes
Graph models are suitable candidates for KR on the Web, where everything is a graph, from the graph of machines connected to the Internet, the "Giant Global Graph" as described by Tim Berners-Lee, to RDF graphs and ontologies. In that context, the ontological query answering problem is the following: given a knowledge base composed of a terminological component and an assertional component and a query, does the knowledge base implies the query, i. E. Is there an answer to the query in the knowledge base? Recently, new description logic languages have been proposed where the ontological expressivity is restricted so that query answering becomes tractable. The most prominent members are the DL-Lite and the EL families. In the same way, the OWL-DL language has been restricted and this has led to OWL2, based on the DL-Lite and EL families. We work in the framework of using graph formalisms for knowledge representation (RDF, RDF-S and OWL) and interrogation (SPARQL). Even if interrogation languages based on graphs have long been presented as a natural and intuitive way of expressing information needs, end-users do not think their queries in terms of graphs. They need simple languages that are as close as possible to natural language, or at least mainly limited to keywords. We propose to define a generic way of translating a query expressed in a high-level language into the SPARQL query language, by means of query patterns. The beginning of this work coincides with the current activity of the W3C that launches an initiative to prepare a possible new version of RDF and is in the process of standardizing SPARQL 1. 1 with entailments

APA, Harvard, Vancouver, ISO, and other styles

32

Conde, Cespedes Patricia. "Modélisations et extensions du formalisme de l'analyse relationnelle mathématique à la modularisation des grands graphes." Paris 6, 2013. http://www.theses.fr/2013PA066654.

Full text

Abstract:

Un graphe étant un ensemble d'objets liés par une certaine relation typée, le problème de "modularisation" des grands graphes (qui revient à leur partitionnement en classes) peut, alors, être modélisé mathématiquement en utilisant l'Analyse Relationnelle. Cette modélisation permet de comparer sur les mêmes bases un certain nombre de critères de découpage de graphe c'est-à-dire de modularisation. Nous proposons une réécriture Relationnelle des critères de modularisation connus tels le critère de Newman-Girvan, Zahn-Condorcet, Owsinski-Zadrozny, Condorcet pondéré, Demaine-Immorlica, Wei-Cheng, la Différence de profils et Michalski-Goldberg. Nous introduisons trois critères : la Modularité équilibrée, l'écart à l'Indétermination et l'écart à l'Uniformité. Nous identifions les propriétés vérifiées par ces critères et pour certains critères, notamment les critères linéaires, nous caractérisons les partitions obtenues via leur optimisation dans le but de faciliter leur compréhension et d'interpréter plus clairement leurs finalités en y associant la preuve de leur utilité dans certains contextes pratiques. Les résultats trouvés sont testés sur des graphes réels de tailles différentes avec l'algorithme de Louvain générique
Graphs are the mathematical representation of networks. Since a graph is a special type of binary relation, graph clustering (or modularization), can be mathematically modelled using the Mathematical Relational analysis. This modelling allows to compare numerous graph clustering criteria on the same type of formal representation. We give through a relational coding, the way of comparing different modularization criteria such as: Newman-Girvan, Zahn-Condorcet, Owsinski-Zadrozny, Demaine-Immorlica, Wei-Cheng, Profile Difference et Michalski-Goldberg. We introduce three modularization criteria: the Balanced Modularity, the deviation to Indetermination and the deviation to Uniformity. We identify the properties verified by those criteria and for some of those criteria, specially linear criteria, we characterize the partitions obtained by the optimization of these criteria. The final goal is to facilitate their understanding and their usefulness in some practical contexts, where their purposes become easily interpretable and understandable. Our results are tested by modularizing real networks of different sizes with the generalized Louvain algorithm

APA, Harvard, Vancouver, ISO, and other styles

33

Kooli, Nihel. "Rapprochement de données pour la reconnaissance d'entités dans les documents océrisés." Thesis, Université de Lorraine, 2016. http://www.theses.fr/2016LORR0108/document.

Full text

Abstract:

Cette thèse traite de la reconnaissance d'entités dans les documents océrisés guidée par une base de données. Une entité peut être, par exemple, une entreprise décrite par son nom, son adresse, son numéro de téléphone, son numéro TVA, etc. ou des méta-données d'un article scientifique tels que son titre, ses auteurs et leurs affiliations, le nom de son journal, etc. Disposant d'un ensemble d'entités structurées sous forme d'enregistrements dans une base de données et d'un document contenant une ou plusieurs de ces entités, nous cherchons à identifier les entités contenues dans le document en utilisant la base de données. Ce travail est motivé par une application industrielle qui vise l'automatisation du traitement des images de documents administratifs arrivant en flux continu. Nous avons abordé ce problème comme un problème de rapprochement entre le contenu du document et celui de la base de données. Les difficultés de cette tâche sont dues à la variabilité de la représentation d'attributs d'entités dans la base et le document et à la présence d'attributs similaires dans des entités différentes. À cela s'ajoutent les redondances d'enregistrements et les erreurs de saisie dans la base de données et l'altération de la structure et du contenu du document, causée par l'OCR. Devant ces problèmes, nous avons opté pour une démarche en deux étapes : la résolution d'entités et la reconnaissance d'entités. La première étape consiste à coupler les enregistrements se référant à une même entité et à les synthétiser dans un modèle entité. Pour ce faire, nous avons proposé une approche supervisée basée sur la combinaison de plusieurs mesures de similarité entre attributs. Ces mesures permettent de tolérer quelques erreurs sur les caractères et de tenir compte des permutations entre termes. La deuxième étape vise à rapprocher les entités mentionnées dans un document avec le modèle entité obtenu. Nous avons procédé par deux manières différentes, l'une utilise le rapprochement par le contenu et l'autre intègre le rapprochement par la structure. Pour le rapprochement par le contenu, nous avons proposé deux méthodes : M-EROCS et ERBL. M-EROCS, une amélioration/adaptation d'une méthode de l'état de l'art, consiste à faire correspondre les blocs de l'OCR avec le modèle entité en se basant sur un score qui tolère les erreurs d'OCR et les variabilités d'attributs. ERBL consiste à étiqueter le document par les attributs d'entités et à regrouper ces labels en entités. Pour le rapprochement par les structures, il s'agit d'exploiter les relations structurelles entre les labels d'une entité pour corriger les erreurs d'étiquetage. La méthode proposée, nommée G-ELSE, consiste à utiliser le rapprochement inexact de graphes attribués modélisant des structures locales, avec un modèle structurel appris pour cet objectif. Cette thèse étant effectuée en collaboration avec la société ITESOFT-Yooz, nous avons expérimenté toutes les étapes proposées sur deux corpus administratifs et un troisième corpus extrait du Web
This thesis focuses on entity recognition in documents recognized by OCR, driven by a database. An entity is a homogeneous group of attributes such as an enterprise in a business form described by the name, the address, the contact numbers, etc. or meta-data of a scientific paper representing the title, the authors and their affiliation, etc. Given a database which describes entities by its records and a document which contains one or more entities from this database, we are looking to identify entities in the document using the database. This work is motivated by an industrial application which aims to automate the image document processing, arriving in a continuous stream. We addressed this problem as a matching issue between the document and the database contents. The difficulties of this task are due to the variability of the entity attributes representation in the database and in the document and to the presence of similar attributes in different entities. Added to this are the record redundancy and typing errors in the database, and the alteration of the structure and the content of the document, caused by OCR. To deal with these problems, we opted for a two-step approach: entity resolution and entity recognition. The first step is to link the records referring to the same entity and to synthesize them in an entity model. For this purpose, we proposed a supervised approach based on a combination of several similarity measures between attributes. These measures tolerate character mistakes and take into account the word permutation. The second step aims to match the entities mentioned in documents with the resulting entity model. We proceeded by two different ways, one uses the content matching and the other integrates the structure matching. For the content matching, we proposed two methods: M-EROCS and ERBL. M-EROCS, an improvement / adaptation of a state of the art method, is to match OCR blocks with the entity model based on a score that tolerates the OCR errors and the attribute variability. ERBL is to label the document with the entity attributes and to group these labels into entities. The structure matching is to exploit the structural relationships between the entity labels to correct the mislabeling. The proposed method, called G-ELSE, is based on local structure graph matching with a structural model which is learned for this purpose. This thesis being carried out in collaboration with the ITESOFT-Yooz society, we have experimented all the proposed steps on two administrative corpuses and a third one extracted from the web

APA, Harvard, Vancouver, ISO, and other styles

34

Mougel, Pierre-Nicolas. "Finding homogeneous collections of dense subgraphs using constraint-based data mining approaches." Thesis, Lyon, INSA, 2012. http://www.theses.fr/2012ISAL0073.

Full text

Abstract:

Ce travail de thèse concerne la fouille de données sur des graphes attribués. Il s'agit de graphes dans lesquels des propriétés, encodées sous forme d'attributs, sont associées à chaque sommet. Notre objectif est la découverte, dans ce type de données, de sous-graphes organisés en plusieurs groupes de sommets fortement connectés et homogènes au regard des attributs. Plus précisément, nous définissons l'extraction sous contraintes d'ensembles de sous-graphes densément connectés et tels que les sommets partagent suffisamment d'attributs. Pour cela nous proposons deux familles de motifs originales ainsi que les algorithmes justes et complets permettant leur extraction efficace sous contraintes. La première famille, nommée Ensembles Maximaux de Cliques Homogènes, correspond à des motifs satisfaisant des contraintes concernant le nombre de sous-graphes denses, la taille de ces sous-graphes et le nombre d'attributs partagés. La seconde famille, nommée Collections Homogènes de k-cliques Percolées emploie quant à elle une notion de densité plus relaxée permettant d'adapter la méthode aux données avec des valeurs manquantes. Ces deux méthodes sont appliquées à l'analyse de deux types de réseaux, les réseaux de coopérations entre chercheurs et les réseaux d'interactions de protéines. Les motifs obtenus mettent en évidence des structures utiles dans un processus de prise de décision. Ainsi, dans un réseau de coopérations entre chercheurs, l'analyse de ces structures peut aider à la mise en place de collaborations scientifiques entre des groupes travaillant sur un même domaine. Dans le contexte d'un graphe de protéines, les structures exhibées permettent d'étudier les relations entre des modules de protéines intervenant dans des situations biologiques similaires. L'étude des performances en fonction de différentes caractéristiques de graphes attribués réels et synthétiques montre que les approches proposées sont utilisables sur de grands jeux de données
The work presented in this thesis deals with data mining approaches for the analysis of attributed graphs. An attributed graph is a graph where properties, encoded by means of attributes, are associated to each vertex. In such data, our objective is the discovery of subgraphs formed by several dense groups of vertices that are homogeneous with respect to the attributes. More precisely, we define the constraint-based extraction of collections of subgraphs densely connected and such that the vertices share enough attributes. To this aim, we propose two new classes of patterns along with sound and complete algorithms to compute them efficiently using constraint-based approaches. The first family of patterns, named Maximal Homogeneous Clique Set (MHCS), contains patterns satisfying constraints on the number of dense subgraphs, on the size of these subgraphs, and on the number of shared attributes. The second class of patterns, named Collection of Homogeneous k-clique Percolated components (CoHoP), is based on a relaxed notion of density in order to handle missing values. Both approaches are used for the analysis of scientific collaboration networks and protein-protein interaction networks. The extracted patterns exhibit structures useful in a decision support process. Indeed, in a scientific collaboration network, the analysis of such structures might give hints to propose new collaborations between researchers working on the same subjects. In a protein-protein interaction network, the analysis of the extracted patterns can be used to study the relationships between modules of proteins involved in similar biological situations. The analysis of the performances, on real and synthetic data, with respect to different attributed graph characteristics, shows that the proposed approaches scale well for large datasets

APA, Harvard, Vancouver, ISO, and other styles

35

Taraviras, Stavros. "Évaluation de la diversité moléculaire des bases de données de molécules à intérêt pharmaceutique, en utilisant la théorie des graphes chimiques." Nice, 2000. http://www.theses.fr/2000NICE5472.

Full text

Abstract:

La compétition entre les grands groupes pharmaceutiques dans la recherche de nouvelles substances actives a favorisé le développement de nouvelles techniques de synthèses (chimie combinatoire et synthèse parallèle) et de méthodes de tests rapides des molécules (High-throughput screening ou HTS). Contrairement aux méthodes classiques, ces techniques ont pour caractéristique commune d'opérer sur de très grands nombres de molécules. Malgré leur puissance, il est vite apparu nécessaire de sélectionner des sous-ensembles représentatifs de l'énorme éventail de molécules potentiellement actives. Cette exigence est à la base du concept de diversité moléculaire. Les structures chimiques sont usuellement caractérisées par des descripteurs moléculaires qui appartiennent à plusieurs classes distinctes. Les descripteurs topologiques, qui sont au nombre de plusieurs centaines, apparaissent bien adaptés pour aborder ce problème. Le but de ce travail est de proposer des méthodes pour choisir des ensembles optimaux de descripteurs, afin de bien échantillonner la diversité de l'espace chimique.

APA, Harvard, Vancouver, ISO, and other styles

36

Dkhil, Abdellatif. "Identification systématique de structures visuelles de flux physique de production." Strasbourg, 2011. http://www.theses.fr/2011STRA6012.

Full text

Abstract:

Ce travail de recherche est motivé par le contexte concurrentiel des entreprises industrielles. Il porte sur la conception des systèmes physiques de production. Plus précisément, le cadre d’étude est centré la phase de conception préliminaire. Cette phase est particulièrement sensible et elle représente des enjeux majeurs. Lors de cette phase, différents points de vue peuvent être considérés pour générer des agencements conceptuels. Ce travail se focalise sur l’étude d’un point de vue unique ; celui du flux statique de produit entre les postes de charges. La génération des agencements conceptuels selon le point de vue flux de produits s’effectue par l’application d’une méthode appelée méthode usuelle d’élaboration des agencements conceptuels. Cette méthode est proposée dans la littérature scientifique. Elle se présente comme une chaîne de traitements des données générés par trois activités principales. La première activité consiste à extraire les données de flux à partir des gammes de production. Lors de la deuxième activité, des propriétés d’analyse sont utilisées pour analyse les données de flux. Les résultats de l’analyse unique ou combinée sont appelées structures visuelles. La troisième activité permet la transformation des structures visuelles en dessins de graphe de flux. Une étude bibliographique aboutit à 44 propriétés d’analyse induisant 1. 75 1013 structures visuelles possibles et donc au même nombre de dessins de graphes de flux. Devant ce constat, une problématique scientifique de réduction du modèle sur la base des connaissances expertes est définie. Dans ce travail, la réduction du modèle est présentée comme un processus de restriction basée sur des règles métiers et vérifiés avec des données industrielles. Au travers de ce processus de réduction, trois contributions sont proposées. La première consiste et à identifier un référentiel des propriétés d’analyse. Ces propriétés sont jugées les plus utiles et les plus pertinentes en conception préliminaire du système physique de production. La seconde correspond à l’identification d’un référentiel des structures visuelles. En fin la troisième contribution est une méthode d’identification automatique des structures visuelles particulière. Pour évaluer l’apport de ces trois contributions, une étude de cas industriel est proposée
This research is motivated by the competitive environment of manufacturing companies. It mainly concerns the design of physical production systems. Specifically, the framework study is performed during the preliminary design phase. This phase is particularly sensitive and plays a major role, where different point of views can be considered to realize the conceptual design. Only one view point concerning the static production flow is considered in this work. To generate a conceptual design depending on this point of view, a usual method of conceptual design elaboration is used. This method is introduced in many literatures. It looks like a string of data processing generated by three main activities. The first activity allows the extraction of data flow from product routing data. During the second activity, properties of analysis are used to analyze the data flow. The single or combined analysis results are called visual structures. The third activity allows the drawings of production flow graph using visual structures. After a literature review, 44 properties analysis are obtained. From these properties of analysis we can deduce 1. 75 1013 possible visual structures and the same number of production flow graphs. Recognizing this, a scientific problem of model reduction based on expert knowledge is defined. Here, the model reduction is a restriction process based on expert rules and validated with industrial data. Through this restriction process, three contributions are proposed. The first concerns the identification of referential properties of analysis which are considered the most useful and relevant in preliminary design phase. The second allows the identification of referential visual structures. The third contribution is a method to automatically identify the particular visual structures. In order to evaluate these contributions, an industrial case study is proposed

APA, Harvard, Vancouver, ISO, and other styles

37

Rahman, Md Rashedur. "Knowledge Base Population based on Entity Graph Analysis." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS092/document.

Full text

Abstract:

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'art
Knowledge 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

APA, Harvard, Vancouver, ISO, and other styles

38

Ayed, Rihab. "Recherche d’information agrégative dans des bases de graphes distribuées." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1305.

Full text

Abstract:

Le sujet de cette thèse s’inscrit dans le cadre général de la Recherche d’Information et la gestion des données massives et distribuées. Notre problématique concerne l’évaluation et l’optimisation de requêtes agrégatives (Aggregated Search). La Recherche d’Information Agrégative est un nouveau paradigme permettant l’accès à l’information massivement distribuée. Elle a pour but de retourner à l’utilisateur d’un système de recherche d’information des objets résultats qui sont riches et porteurs de connaissances. Ces objets n’existent pas en tant que tels dans les sources. Ils sont construits par assemblage (ou configuration ou agrégation) de fragments issus de diffèrentes sources. Les sources peuvent être non spécifiées dans l’expression de la requête mais découvertes dynamiquement lors de la recherche. Nous nous intéressons particulièrement à l’exploitation des dépendances de données pour optimiser les accès aux sources distribuées. Dans ce cadre, nous proposons une approche pour l’un des sous processus de systèmes de RIA, principalement le processus d’indexation/organisation des documents. Nous considérons dans cette thèse, les systèmes de recherche d’information orientés graphes (graphes RDF). Utilisant les relations dans les graphes, notre travail s’inscrit dans le cadre de la recherche d’information agrégative relationnelle (Relational Aggregated Search) où les relations sont exploitées pour agréger des fragments d’information. Nous proposons d’optimiser l’accès aux sources d’information dans un système de recherche d’information agrégative. Ces sources contiennent des fragments d’information répondant partiellement à la requête. L’objectif est de minimiser le nombre de sources interrogées pour chaque fragment de la requête, ainsi que de maximiser les opérations d’agrégations de fragments dans une même source. Nous proposons d’effectuer cela en réorganisant la/les base(s) de graphes dans plusieurs clusters d’information dédiés aux requêtes agrégatives. Ces clusters sont obtenus à partir d’une approche de clustering sémantique ou structurel des prédicats des graphes RDF. Pour le clustering structurel, nous utilisons les algorithmes d’extraction de sous-graphes fréquents et dans ce cadre nous élaborons une étude comparative des performances de ces algorithmes. Pour le clustering sémantique, nous utilisons les métadonnées descriptives des prédicats dont nous appliquons des outils de similarité textuelle sémantique. Nous définissons une approche de décomposition de requêtes basée essentiellement sur le clustering choisi
In this research, we are interested in investigating issues related to query evaluation and optimization in the framework of aggregated search. Aggregated search is a new paradigm to access massively distributed information. It aims to produce answers to queries by combining fragments of information from different sources. The queries search for objects (documents) that do not exist as such in the targeted sources, but are built from fragments extracted from the different sources. The sources might not be specified in the query expression, they are dynamically discovered at runtime. In our work, we consider data dependencies to propose a framework for optimizing query evaluation over distributed graph-oriented data sources. For this purpose, we propose an approach for the document indexing/orgranizing process of aggregated search systems. We consider information retrieval systems that are graph oriented (RDF graphs). Using graph relationships, our work is within relational aggregated search where relationships are used to aggregate fragments of information. Our goal is to optimize the access to source of information in a aggregated search system. These sources contain fragments of information that are relevant partially for the query. We aim at minimizing the number of sources to ask, also at maximizing the aggregation operations within a same source. For this, we propose to reorganize the graph database(s) in partitions, dedicated to aggregated queries. We use a semantic or strucutral clustering of RDF predicates. For structural clustering, we propose to use frequent subgraph mining algorithms, we performed for this, a comparative study of their performances. For semantic clustering, we use the descriptive metadata of RDF predicates and apply semantic textual similarity methods to calculate their relatedness. Following the clustering, we define query decomposing rules based on the semantic/structural aspects of RDF predicates

APA, Harvard, Vancouver, ISO, and other styles

39

Jakawat, Wararat. "Graphs enriched by Cubes (GreC) : a new approach for OLAP on information networks." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSE2087/document.

Full text

Abstract:

L'analyse en ligne OLAP (Online Analytical Processing) est une des technologies les plus importantes dans les entrepôts de données, elle permet l'analyse multidimensionnelle de données. Cela correspond à un outil d'analyse puissant, tout en étant flexible en terme d'utilisation pour naviguer dans les données, plus ou moins en profondeur. OLAP a été le sujet de différentes améliorations et extensions, avec sans cesse de nouveaux problèmes en lien avec le domaine et les données, par exemple le multimedia, les données spatiales, les données séquentielles, etc. A l'origine, OLAP a été introduit pour analyser des données structurées que l'on peut qualifier de classiques. Cependant, l'émergence des réseaux d'information induit alors un nouveau domaine intéressant qu'il convient d'explorer. Extraire des connaissances à partir de larges réseaux constitue une tâche complexe et non évidente. Ainsi, l'analyse OLAP peut être une bonne alternative pour observer les données avec certains points de vue. Différents types de réseaux d'information peuvent aider les utilisateurs dans différentes activités, en fonction de différents domaines. Ici, nous focalisons notre attention sur les réseaux d'informations bibliographiques construits à partir des bases de données bibliographiques. Ces données permettent d'analyser non seulement la production scientifique, mais également les collaborations entre auteurs. Il existe différents travaux qui proposent d'avoir recours aux technologies OLAP pour les réseaux d'information, nommé ``graph OLAP". Beaucoup de techniques se basent sur ce qu'on peut appeler cube de graphes. Dans cette thèse, nous proposons une nouvelle approche de “graph OLAP” que nous appelons “Graphes enrichis par des Cubes” (GreC). Notre proposition consiste à enrichir les graphes avec des cubes plutôt que de construire des cubes de graphes. En effet, les noeuds et/ou les arêtes du réseau considéré sont décrits par des cubes de données. Cela permet des analyses intéressantes pour l'utilisateur qui peut naviguer au sein d'un graphe enrichi de cubes selon différents niveaux d'analyse, avec des opérateurs dédiés. En outre, notons quatre principaux aspects dans GreC. Premièrement, GreC considère la structure du réseau afin de permettre des opérations OLAP topologiques, et pas seulement des opérations OLAP classiques et informationnelles. Deuxièmement, GreC propose une vision globale du graphe avec des informations multidimensionnelles. Troisièmement, le problème de dimension à évolution lente est pris en charge dans le cadre de l'exploration du réseau. Quatrièmement, et dernièrement, GreC permet l'analyse de données avec une évolution du réseau parce que notre approche permet d'observer la dynamique à travers la dimension temporelle qui peut être présente dans les cubes pour la description des noeuds et/ou arêtes. Pour évaluer GreC, nous avons implémenté notre approche et mené une étude expérimentale sur des jeux de données réelles pour montrer l'intérêt de notre approche. L'approche GreC comprend différents algorithmes. Nous avons validé de manière expérimentale la pertinence de nos algorithmes et montrons leurs performances
Online Analytical Processing (OLAP) is one of the most important technologies in data warehouse systems, which enables multidimensional analysis of data. It represents a very powerful and flexible analysis tool to manage within the data deeply by operating computation. OLAP has been the subject of improvements and extensions across the board with every new problem concerning domain and data; for instance, multimedia, spatial data, sequence data and etc. Basically, OLAP was introduced to analyze classical structured data. However, information networks are yet another interesting domain. Extracting knowledge inside large networks is a complex task and too big to be comprehensive. Therefore, OLAP analysis could be a good idea to look at a more compressed view. Many kinds of information networks can help users with various activities according to different domains. In this scenario, we further consider bibliographic networks formed on the bibliographic databases. This data allows analyzing not only the productions but also the collaborations between authors. There are research works and proposals that try to use OLAP technologies for information networks and it is called Graph OLAP. Many Graph OLAP techniques are based on a cube of graphs.In this thesis, we propose a new approach for Graph OLAP that is graphs enriched by cubes (GreC). In a different and complementary way, our proposal consists in enriching graphs with cubes. Indeed, the nodes or/and edges of the considered network are described by a cube. It allows interesting analyzes for the user who can navigate within a graph enriched by cubes according to different granularity levels, with dedicated operators. In addition, there are four main aspects in GreC. First, GreC takes into account the structure of network in order to do topological OLAP operations and not only classical or informational OLAP operations. Second, GreC has a global view of a network considered with multidimensional information. Third, the slowly changing dimension problem is taken into account in order to explore a network. Lastly, GreC allows data analysis for the evolution of a network because our approach allows observing the evolution through the time dimensions in the cubes.To evaluate GreC, we implemented our approach and performed an experimental study on a real bibliographic dataset to show the interest of our proposal. GreC approach includes different algorithms. Therefore, we also validated the relevance and the performances of our algorithms experimentally

APA, Harvard, Vancouver, ISO, and other styles

40

Echbarthi, Ghizlane. "Big Graph Processing : Partitioning and Aggregated Querying." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSE1225/document.

Full text

Abstract:

Avec l'avènement du « big data », de nombreuses répercussions ont eu lieu dans tous les domaines de la technologie de l'information, préconisant des solutions innovantes remportant le meilleur compromis entre coûts et précision. En théorie des graphes, où les graphes constituent un support de modélisation puissant qui permet de formaliser des problèmes allant des plus simples aux plus complexes, la recherche pour des problèmes NP-complet ou NP-difficils se tourne plutôt vers des solutions approchées, mettant ainsi en avant les algorithmes d'approximations et les heuristiques alors que les solutions exactes deviennent extrêmement coûteuses et impossible d'utilisation.Nous abordons dans cette thèse deux problématiques principales: dans un premier temps, le problème du partitionnement des graphes est abordé d'une perspective « big data », où les graphes massifs sont partitionnés en streaming. Nous étudions et proposons plusieurs modèles de partitionnement en streaming et nous évaluons leurs performances autant sur le plan théorique qu'empirique. Dans un second temps, nous nous intéressons au requêtage des graphes distribués/partitionnés. Dans ce cadre, nous étudions la problématique de la « recherche agrégative dans les graphes » qui a pour but de répondre à des requêtes interrogeant plusieurs fragments de graphes et qui se charge de la reconstruction de la réponse finale tel que l'on obtient un « matching approché » avec la requête initiale
With the advent of the "big data", many repercussions have taken place in all fields of information technology, advocating innovative solutions with the best compromise between cost and accuracy. In graph theory, where graphs provide a powerful modeling support for formalizing problems ranging from the simplest to the most complex, the search for NP-complete or NP-difficult problems is rather directed towards approximate solutions, thus Forward approximation algorithms and heuristics while exact solutions become extremely expensive and impossible to use. In this thesis we discuss two main problems: first, the problem of partitioning graphs is approached from a perspective big data, where massive graphs are partitioned in streaming. We study and propose several models of streaming partitioning and we evaluate their performances both theoretically and empirically. In a second step, we are interested in querying distributed / partitioned graphs. In this context, we study the problem of aggregative search in graphs, which aims to answer queries that interrogate several fragments of graphs and which is responsible for reconstructing the final response such that a Matching approached with the initial query

APA, Harvard, Vancouver, ISO, and other styles

41

Kooli, Nihel. "Rapprochement de données pour la reconnaissance d'entités dans les documents océrisés." Electronic Thesis or Diss., Université de Lorraine, 2016. http://www.theses.fr/2016LORR0108.

Full text

Abstract:

Cette thèse traite de la reconnaissance d'entités dans les documents océrisés guidée par une base de données. Une entité peut être, par exemple, une entreprise décrite par son nom, son adresse, son numéro de téléphone, son numéro TVA, etc. ou des méta-données d'un article scientifique tels que son titre, ses auteurs et leurs affiliations, le nom de son journal, etc. Disposant d'un ensemble d'entités structurées sous forme d'enregistrements dans une base de données et d'un document contenant une ou plusieurs de ces entités, nous cherchons à identifier les entités contenues dans le document en utilisant la base de données. Ce travail est motivé par une application industrielle qui vise l'automatisation du traitement des images de documents administratifs arrivant en flux continu. Nous avons abordé ce problème comme un problème de rapprochement entre le contenu du document et celui de la base de données. Les difficultés de cette tâche sont dues à la variabilité de la représentation d'attributs d'entités dans la base et le document et à la présence d'attributs similaires dans des entités différentes. À cela s'ajoutent les redondances d'enregistrements et les erreurs de saisie dans la base de données et l'altération de la structure et du contenu du document, causée par l'OCR. Devant ces problèmes, nous avons opté pour une démarche en deux étapes : la résolution d'entités et la reconnaissance d'entités. La première étape consiste à coupler les enregistrements se référant à une même entité et à les synthétiser dans un modèle entité. Pour ce faire, nous avons proposé une approche supervisée basée sur la combinaison de plusieurs mesures de similarité entre attributs. Ces mesures permettent de tolérer quelques erreurs sur les caractères et de tenir compte des permutations entre termes. La deuxième étape vise à rapprocher les entités mentionnées dans un document avec le modèle entité obtenu. Nous avons procédé par deux manières différentes, l'une utilise le rapprochement par le contenu et l'autre intègre le rapprochement par la structure. Pour le rapprochement par le contenu, nous avons proposé deux méthodes : M-EROCS et ERBL. M-EROCS, une amélioration/adaptation d'une méthode de l'état de l'art, consiste à faire correspondre les blocs de l'OCR avec le modèle entité en se basant sur un score qui tolère les erreurs d'OCR et les variabilités d'attributs. ERBL consiste à étiqueter le document par les attributs d'entités et à regrouper ces labels en entités. Pour le rapprochement par les structures, il s'agit d'exploiter les relations structurelles entre les labels d'une entité pour corriger les erreurs d'étiquetage. La méthode proposée, nommée G-ELSE, consiste à utiliser le rapprochement inexact de graphes attribués modélisant des structures locales, avec un modèle structurel appris pour cet objectif. Cette thèse étant effectuée en collaboration avec la société ITESOFT-Yooz, nous avons expérimenté toutes les étapes proposées sur deux corpus administratifs et un troisième corpus extrait du Web
This thesis focuses on entity recognition in documents recognized by OCR, driven by a database. An entity is a homogeneous group of attributes such as an enterprise in a business form described by the name, the address, the contact numbers, etc. or meta-data of a scientific paper representing the title, the authors and their affiliation, etc. Given a database which describes entities by its records and a document which contains one or more entities from this database, we are looking to identify entities in the document using the database. This work is motivated by an industrial application which aims to automate the image document processing, arriving in a continuous stream. We addressed this problem as a matching issue between the document and the database contents. The difficulties of this task are due to the variability of the entity attributes representation in the database and in the document and to the presence of similar attributes in different entities. Added to this are the record redundancy and typing errors in the database, and the alteration of the structure and the content of the document, caused by OCR. To deal with these problems, we opted for a two-step approach: entity resolution and entity recognition. The first step is to link the records referring to the same entity and to synthesize them in an entity model. For this purpose, we proposed a supervised approach based on a combination of several similarity measures between attributes. These measures tolerate character mistakes and take into account the word permutation. The second step aims to match the entities mentioned in documents with the resulting entity model. We proceeded by two different ways, one uses the content matching and the other integrates the structure matching. For the content matching, we proposed two methods: M-EROCS and ERBL. M-EROCS, an improvement / adaptation of a state of the art method, is to match OCR blocks with the entity model based on a score that tolerates the OCR errors and the attribute variability. ERBL is to label the document with the entity attributes and to group these labels into entities. The structure matching is to exploit the structural relationships between the entity labels to correct the mislabeling. The proposed method, called G-ELSE, is based on local structure graph matching with a structural model which is learned for this purpose. This thesis being carried out in collaboration with the ITESOFT-Yooz society, we have experimented all the proposed steps on two administrative corpuses and a third one extracted from the web

APA, Harvard, Vancouver, ISO, and other styles

42

Galicia, Auyón Jorge Armando. "Revisiting Data Partitioning for Scalable RDF Graph Processing Combining Graph Exploration and Fragmentation for RDF Processing Query Optimization for Large Scale Clustered RDF Data RDFPart- Suite: Bridging Physical and Logical RDF Partitioning. Reverse Partitioning for SPARQL Queries: Principles and Performance Analysis. ShouldWe Be Afraid of Querying Billions of Triples in a Graph-Based Centralized System? EXGRAF: Exploration et Fragmentation de Graphes au Service du Traitement Scalable de Requˆetes RDF." Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2021. http://www.theses.fr/2021ESMA0001.

Full text

Abstract:

Le Resource Description Framework (RDF) et SPARQL sont des standards très populaires basés sur des graphes initialement conçus pour représenter et interroger des informations sur le Web. La flexibilité offerte par RDF a motivé son utilisation dans d'autres domaines. Aujourd'hui les jeux de données RDF sont d'excellentes sources d'information. Ils rassemblent des milliards de triplets dans des Knowledge Graphs qui doivent être stockés et exploités efficacement. La première génération de systèmes RDF a été construite sur des bases de données relationnelles traditionnelles. Malheureusement, les performances de ces systèmes se dégradent rapidement car le modèle relationnel ne convient pas au traitement des données RDF intrinsèquement représentées sous forme de graphe. Les systèmes RDF natifs et distribués cherchent à surmonter cette limitation. Les premiers utilisent principalement l’indexation comme stratégie d'optimisation pour accélérer les requêtes. Les deuxièmes recourent au partitionnement des données. Dans le modèle relationnel, la représentation logique de la base de données est cruciale pour concevoir le partitionnement. La couche logique définissant le schéma explicite de la base de données offre un certain confort aux concepteurs. Cette couche leur permet de choisir manuellement ou automatiquement, via des assistants automatiques, les tables et les attributs à partitionner. Aussi, elle préserve les concepts fondamentaux sur le partitionnement qui restent constants quel que soit le système de gestion de base de données. Ce schéma de conception n'est plus valide pour les bases de données RDF car le modèle RDF n'applique pas explicitement un schéma aux données. Ainsi, la couche logique est inexistante et le partitionnement des données dépend fortement des implémentations physiques des triplets sur le disque. Cette situation contribue à avoir des logiques de partitionnement différentes selon le système cible, ce qui est assez différent du point de vue du modèle relationnel. Dans cette thèse, nous promouvons l'idée d'effectuer le partitionnement de données au niveau logique dans les bases de données RDF. Ainsi, nous traitons d'abord le graphe de données RDF pour prendre en charge le partitionnement basé sur des entités logiques. Puis, nous proposons un framework pour effectuer les méthodes de partitionnement. Ce framework s'accompagne de procédures d'allocation et de distribution des données. Notre framework a été incorporé dans un système de traitement des données RDF centralisé (RDF_QDAG) et un système distribué (gStoreD). Nous avons mené plusieurs expériences qui ont confirmé la faisabilité de l'intégration de notre framework aux systèmes existants en améliorant leurs performances pour certaines requêtes. Enfin, nous concevons un ensemble d'outils de gestion du partitionnement de données RDF dont un langage de définition de données (DDL) et un assistant automatique de partitionnement
The Resource Description Framework (RDF) and SPARQL are very popular graph-based standards initially designed to represent and query information on the Web. The flexibility offered by RDF motivated its use in other domains and today RDF datasets are great information sources. They gather billions of triples in Knowledge Graphs that must be stored and efficiently exploited. The first generation of RDF systems was built on top of traditional relational databases. Unfortunately, the performance in these systems degrades rapidly as the relational model is not suitable for handling RDF data inherently represented as a graph. Native and distributed RDF systems seek to overcome this limitation. The former mainly use indexing as an optimization strategy to speed up queries. Distributed and parallel RDF systems resorts to data partitioning. The logical representation of the database is crucial to design data partitions in the relational model. The logical layer defining the explicit schema of the database provides a degree of comfort to database designers. It lets them choose manually or automatically (through advisors) the tables and attributes to be partitioned. Besides, it allows the partitioning core concepts to remain constant regardless of the database management system. This design scheme is no longer valid for RDF databases. Essentially, because the RDF model does not explicitly enforce a schema since RDF data is mostly implicitly structured. Thus, the logical layer is inexistent and data partitioning depends strongly on the physical implementations of the triples on disk. This situation contributes to have different partitioning logics depending on the target system, which is quite different from the relational model’s perspective. In this thesis, we promote the novel idea of performing data partitioning at the logical level in RDF databases. Thereby, we first process the RDF data graph to support logical entity-based partitioning. After this preparation, we present a partitioning framework built upon these logical structures. This framework is accompanied by data fragmentation, allocation, and distribution procedures. This framework was incorporated to a centralized (RDF_QDAG) and a distributed (gStoreD) triple store. We conducted several experiments that confirmed the feasibility of integrating our framework to existent systems improving their performances for certain queries. Finally, we design a set of RDF data partitioning management tools including a data definition language (DDL) and an automatic partitioning wizard

APA, Harvard, Vancouver, ISO, and other styles

43

Simonne, Lucas. "Mining differential causal rules in knowledge graphs." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG008.

Full text

Abstract:

La fouille de règles d'association au sein de graphes de connaissances est un domaine de recherche important.En effet, ce type de règle permet de représenter des connaissances, et leur application permet de compléter un graphe en ajoutant des données manquantes ou de supprimer des données erronées.Cependant, ces règles ne permettent pas d'exprimer des relations causales, dont la sémantique diffère d'une simple association ou corrélation. Dans un système, un lien de causalité entre une variable A et une variable B est une relation orientée de A vers B et indique qu'un changement dans A cause un changement dans B, les autres variables du système conservant les mêmes valeurs.Plusieurs cadres d'étude existent pour déterminer des relations causales, dont le modèle d'étude des résultats potentiels, qui consiste à apparier des instances similaires ayant des valeurs différentes sur une variable nommée traitement pour étudier l'effet de ce traitement sur une autre variable nommée résultat.Nous proposons dans cette thèse plusieurs approches permettant de définir des règles représentant l'effet causal d'un traitement sur un résultat.Cet effet peut être local, i.e., valide pour un sous-ensemble d'instances d'un graphe de connaissances défini par un motif de graphe, ou bien moyen, i.e., valide en moyenne pour l'ensemble d'instances de la classe considérée. La découverte de ces règles se base sur le cadre d'étude des résultats potentiels en appariant des instances similaires, en comparant leurs descriptions RDF au sein du graphe ou bien leurs représentations vectorielles apprises à travers des modèles de plongements de graphes
The mining of association rules within knowledge graphs is an important area of research.Indeed, this type of rule makes it possible to represent knowledge, and their application makes it possible to complete a knowledge graph by adding missing triples or to remove erroneous triples.However, these rules express associations and do not allow the expression of causal relations, whose semantics differ from an association or a correlation.In a system, a causal link between variable A and variable B is a relationship oriented from A to B. It indicates that a change in A causes a change in B, with the other variables in the system maintaining the same values.Several frameworks exist for determining causal relationships, including the potential outcome framework, which involves matching similar instances with different values on a variable named treatment to study the effect of that treatment on another variable named the outcome.In this thesis, we propose several approaches to define rules representing a causal effect of a treatment on an outcome.This effect can be local, i.e., valid for a subset of instances of a knowledge graph defined by a graph pattern, or average, i.e., valid on average for the whole set of graph instances.The discovery of these rules is based on the framework of studying potential outcomes by matching similar instances and comparing their RDF descriptions or their learned vectorial representations through graph embedding models

APA, Harvard, Vancouver, ISO, and other styles

44

François, Hélène. "Synthèse de la parole par concaténation d'unités acoustiques : construction et exploitation d'une base de parole continue." Rennes 1, 2002. http://www.theses.fr/2002REN10127.

Full text

Abstract:

Ces travaux s'inscrivent dans le cadre de la synthèse de la parole par concaténation d'unités acoustiques de taille variable multi-représentées. Pour remédier à l'hétérogénéité de la qualité et de l'intelligibilité des voix synthétiques, nous utilisons une base de parole continue riche au niveau linguistique, ici un jeu de phrases naturelles. Sa construction est vue comme un problème NP-complet de recouvrement minimal d'ensemble. Les méthodes gloutonne, cracheuse et d'échange par paire condensent ainsi des corpus de 100000 à 5000 phrases. Ensuite nous cherchons dans un corpus spécifique l'ensemble des séquences d'unités acoustiques permettant la synthèse de 10 phrases tests. Pour chaque séquence trouvée ses unités sont concaténées, puis sa qualité est évaluée de façon objective en mesurant sa distance acoustique à une référence naturelle. Cela permet de spécifier et de caractériser des bases "génératives", de développer et d'évaluer de nouvelles méthodes de sélection d'unités.

APA, Harvard, Vancouver, ISO, and other styles

45

Alchicha, Élie. "Confidentialité Différentielle et Blowfish appliquées sur des bases de données graphiques, transactionnelles et images." Thesis, Pau, 2021. http://www.theses.fr/2021PAUU3067.

Full text

Abstract:

Les données numériques jouent un rôle crucial dans notre vie quotidienne en communiquant, en enregistrant des informations, en exprimant nos pensées et nos opinions et en capturant nos moments précieux sous forme d'images et de vidéos numériques. Les données numériques présentent d'énormes avantages dans tous les aspects de la vie moderne, mais constituent également une menace pour notre vie privée. Dans cette thèse, nous considérons trois types de données numériques en ligne générées par les utilisateurs des médias sociaux et les clients du commerce électronique : les graphiques, les transactions et les images. Les graphiques sont des enregistrements des interactions entre les utilisateurs qui aident les entreprises à comprendre qui sont les utilisateurs influents dans leur environnement. Les photos postées sur les réseaux sociaux sont une source importante de données qui nécessitent des efforts d'extraction. Les ensembles de données transactionnelles représentent les opérations qui ont eu lieu sur les services de commerce électronique.Nous nous appuyons sur une technique de préservation de la vie privée appelée Differential Privacy (DP) et sa généralisation Blowfish Privacy (BP) pour proposer plusieurs solutions permettant aux propriétaires de données de bénéficier de leurs ensembles de données sans risque de violation de la vie privée pouvant entraîner des problèmes juridiques. Ces techniques sont basées sur l'idée de récupérer l'existence ou la non-existence de tout élément dans l'ensemble de données (tuple, ligne, bord, nœud, image, vecteur, ...) en ajoutant respectivement un petit bruit sur la sortie pour fournir un bon équilibre entre intimité et utilité.Dans le premier cas d'utilisation, nous nous concentrons sur les graphes en proposant trois mécanismes différents pour protéger les données personnelles des utilisateurs avant d'analyser les jeux de données. Pour le premier mécanisme, nous présentons un scénario pour protéger les connexions entre les utilisateurs avec une nouvelle approche où les utilisateurs ont des privilèges différents : les utilisateurs VIP ont besoin d'un niveau de confidentialité plus élevé que les utilisateurs standard. Le scénario du deuxième mécanisme est centré sur la protection d'un groupe de personnes (sous-graphes) au lieu de nœuds ou d'arêtes dans un type de graphes plus avancé appelé graphes dynamiques où les nœuds et les arêtes peuvent changer à chaque intervalle de temps. Dans le troisième scénario, nous continuons à nous concentrer sur les graphiques dynamiques, mais cette fois, les adversaires sont plus agressifs que les deux derniers scénarios car ils plantent de faux comptes dans les graphiques dynamiques pour se connecter à des utilisateurs honnêtes et essayer de révéler leurs nœuds représentatifs dans le graphique.Dans le deuxième cas d'utilisation, nous contribuons dans le domaine des données transactionnelles en présentant un mécanisme existant appelé Safe Grouping. Il repose sur le regroupement des tuples de manière à masquer les corrélations entre eux que l'adversaire pourrait utiliser pour violer la vie privée des utilisateurs. D'un autre côté, ces corrélations sont importantes pour les propriétaires de données dans l'analyse des données pour comprendre qui pourrait être intéressé par des produits, biens ou services similaires. Pour cette raison, nous proposons un nouveau mécanisme qui expose ces corrélations dans de tels ensembles de données, et nous prouvons que le niveau de confidentialité est similaire au niveau fourni par Safe Grouping.Le troisième cas d'usage concerne les images postées par les utilisateurs sur les réseaux sociaux. Nous proposons un mécanisme de préservation de la confidentialité qui permet aux propriétaires des données de classer les éléments des photos sans révéler d'informations sensibles. Nous présentons un scénario d'extraction des sentiments sur les visages en interdisant aux adversaires de reconnaître l'identité des personnes
Digital data is playing crucial role in our daily life in communicating, saving information, expressing our thoughts and opinions and capturing our precious moments as digital pictures and videos. Digital data has enormous benefits in all the aspects of modern life but forms also a threat to our privacy. In this thesis, we consider three types of online digital data generated by users of social media and e-commerce customers: graphs, transactional, and images. The graphs are records of the interactions between users that help the companies understand who are the influential users in their surroundings. The photos posted on social networks are an important source of data that need efforts to extract. The transactional datasets represent the operations that occurred on e-commerce services.We rely on a privacy-preserving technique called Differential Privacy (DP) and its generalization Blowfish Privacy (BP) to propose several solutions for the data owners to benefit from their datasets without the risk of privacy breach that could lead to legal issues. These techniques are based on the idea of recovering the existence or non-existence of any element in the dataset (tuple, row, edge, node, image, vector, ...) by adding respectively small noise on the output to provide a good balance between privacy and utility.In the first use case, we focus on the graphs by proposing three different mechanisms to protect the users' personal data before analyzing the datasets. For the first mechanism, we present a scenario to protect the connections between users (the edges in the graph) with a new approach where the users have different privileges: the VIP users need a higher level of privacy than standard users. The scenario for the second mechanism is centered on protecting a group of people (subgraphs) instead of nodes or edges in a more advanced type of graphs called dynamic graphs where the nodes and the edges might change in each time interval. In the third scenario, we keep focusing on dynamic graphs, but this time the adversaries are more aggressive than the past two scenarios as they are planting fake accounts in the dynamic graphs to connect to honest users and try to reveal their representative nodes in the graph. In the second use case, we contribute in the domain of transactional data by presenting an existed mechanism called Safe Grouping. It relies on grouping the tuples in such a way that hides the correlations between them that the adversary could use to breach the privacy of the users. On the other side, these correlations are important for the data owners in analyzing the data to understand who might be interested in similar products, goods or services. For this reason, we propose a new mechanism that exposes these correlations in such datasets, and we prove that the level of privacy is similar to the level provided by Safe Grouping.The third use-case concerns the images posted by users on social networks. We propose a privacy-preserving mechanism that allows the data owners to classify the elements in the photos without revealing sensitive information. We present a scenario of extracting the sentiments on the faces with forbidding the adversaries from recognizing the identity of the persons. For each use-case, we present the results of the experiments that prove that our algorithms can provide a good balance between privacy and utility and that they outperform existing solutions at least in one of these two concepts

APA, Harvard, Vancouver, ISO, and other styles

46

Alborzi, Seyed Ziaeddin. "Automatic Discovery of Hidden Associations Using Vector Similarity : Application to Biological Annotation Prediction." Electronic Thesis or Diss., Université de Lorraine, 2018. http://www.theses.fr/2018LORR0035.

Full text

Abstract:

Cette thèse présente: 1) le développement d'une nouvelle approche pour trouver des associations directes entre des paires d'éléments liés indirectement à travers diverses caractéristiques communes, 2) l'utilisation de cette approche pour associer directement des fonctions biologiques aux domaines protéiques (ECDomainMiner et GODomainMiner) et pour découvrir des interactions domaine-domaine, et enfin 3) l'extension de cette approche pour annoter de manière complète à partir des domaines les structures et les séquences des protéines. Au total, 20 728 et 20 318 associations EC-Pfam et GO-Pfam non redondantes ont été découvertes, avec des F-mesures de plus de 0,95 par rapport à un ensemble de référence Gold Standard extrait d'une source d'associations connues (InterPro). Par rapport à environ 1500 associations déterminées manuellement dans InterPro, ECDomainMiner et GODomainMiner produisent une augmentation de 13 fois le nombre d'associations EC-Pfam et GO-Pfam disponibles. Ces associations domaine-fonction sont ensuite utilisées pour annoter des milliers de structures de protéines et des millions de séquences de protéines pour lesquelles leur composition de domaine est connue mais qui manquent actuellement d'annotations fonctionnelles. En utilisant des associations de domaines ayant acquis des annotations fonctionnelles inférées, et en tenant compte des informations de taxonomie, des milliers de règles d'annotation ont été générées automatiquement. Ensuite, ces règles ont été utilisées pour annoter des séquences de protéines dans la base de données TrEMBL
This thesis presents: 1) the development of a novel approach to find direct associations between pairs of elements linked indirectly through various common features, 2) the use of this approach to directly associate biological functions to protein domains (ECDomainMiner and GODomainMiner), and to discover domain-domain interactions, and finally 3) the extension of this approach to comprehensively annotate protein structures and sequences. ECDomainMiner and GODomainMiner are two applications to discover new associations between EC Numbers and GO terms to protein domains, respectively. They find a total of 20,728 and 20,318 non-redundant EC-Pfam and GO-Pfam associations, respectively, with F-measures of more than 0.95 with respect to a “Gold Standard” test set extracted from InterPro. Compared to around 1500 manually curated associations in InterPro, ECDomainMiner and GODomainMiner infer a 13-fold increase in the number of available EC-Pfam and GO-Pfam associations. These function-domain associations are then used to annotate thousands of protein structures and millions of protein sequences for which their domain composition is known but that currently lack experimental functional annotations. Using inferred function-domain associations and considering taxonomy information, thousands of annotation rules have automatically been generated. Then, these rules have been utilized to annotate millions of protein sequences in the TrEMBL database

APA, Harvard, Vancouver, ISO, and other styles

47

Ounis, Iadh. "Un modèle d'indexation relationnel pour les graphes conceptuels fondé sur une interprétation logique." Phd thesis, Université Joseph Fourier (Grenoble), 1998. http://tel.archives-ouvertes.fr/tel-00004902.

Full text

Abstract:

L'idée d'établir des relations entre des objets et de les représenter dans la base de connaissances d'un système informatique est le propre de toute approche en Intelligence Artificielle. Cependant, la plupart des formalismes de représentation de connaissances n'exploitent pas toute la richesse de la sémantique de ces relations, ni le comportement qui leur est associé. En recherche d'informations, les traitements de ces relations ne sont guère mieux élaborés et l'impact de leur prise en compte lors de la phase de correspondance n'a jamais été établi, même s'il reste vrai que de nombreuses approches tiennent compte de leur présence dans le document et tentent ainsi de les représenter lors du processus d'indexation. Pourtant la recherche de documents structurés ou complexes exige plus que jamais, outre un langage d'indexation robuste et expressif, la prise en charge de la sémantique des relations ainsi que leurs propriétés. À travers une étude des nouvelles exigences auxquelles la recherche d'informations d'aujourd'hui doit répondre, nous proposons un modèle d'indexation relationnel pour les documents. L'approche consiste à considérer qu'un terme d'indexation est fondé sur des concepts complexes où les connecteurs sémantiques sont vus comme des opérateurs, ou des relations permettant de construire des expressions nouvelles représentant des concepts nouveaux ou des situations nouvelles. Le modèle proposé ne se contente pas de représenter les relations, mais permet aussi d'offrir un cadre général précisant les principes généraux de manipulation de ces relations et la prise en compte de leurs propriétés dans un processus de recherche fondé sur une approche logique. Le modèle proposé comporte deux composantes: le langage de représentation des informations, permettant une approche d'indexation relationnelle, et les règles de dérivation qui, reprenant ce langage, permettent de diriger le processus de correspondance. Nous utilisons la théorie des situations comme langage de représentation et un système de dérivation de pertinence, reposant sur une axiomatisation de la notion de correspondance entre les documents et la requête pour la prise en compte des relations. Une caractéristique intéressante de ce modèle est qu'il conduit à étendre certains formalismes de représentation de connaissances par des notions utiles en recherche d'informations. Les limitations de la famille des logiques terminologiques, utilisée par ailleurs comme base formelle de l'approche d'indexation relationnelle proposée, peuvent ainsi être surmontées. Cependant, la complexité des traitements associés à cette famille de logiques empêche de les utiliser comme un modèle opérationnel. Nous proposons alors le formalisme des graphes conceptuels comme un bon compromis entre la complexité des démonstrateurs de théorèmes et la simplicité des approches algébriques. Ce formalisme est alors vu, à travers une interprétation logique adéquate, comme une implantation d'une logique terminologique étendue et du modèle d'indexation. Notre approche a été implantée sur une plate-forme de gestion de graphes conceptuels, réalisée sur le système de gestion de base de données à objets O2. Le prototype RELIEF résultant de notre expérimentation a été testé sur une collection d'images et a démontré l'applicabilité et le bien-fondé de notre approche.

APA, Harvard, Vancouver, ISO, and other styles

48

Ahmadi, Naser. "A framework for the continuous curation of a knowledge base system." Electronic Thesis or Diss., Sorbonne université, 2021. http://www.theses.fr/2021SORUS320.

Full text

Abstract:

Les graphes de connaissances centrés sur les entités sont de plus en plus populaires pour recueillir des informations sur les entités. Les schémas des KG sont complexes, avec de nombreux types et prédicats différents pour définir les entités et leurs relations. Ces KG contiennent des connaissances spécifiques à un domaine, mais pour tirer le maximum de ces données, il faut comprendre la structure et les schémas du KG. Leurs données comprennent des entités et leurs types sémantiques pour un domaine spécifique. En outre, les propriétés des entités et les relations entre les entités sont stockées. En raison de l'émergence de nouveaux faits et entités et de l'existence de déclarations invalides, la création et la maintenance des KG est un processus sans fin. Dans cette thèse, nous présentons d'abord une approche destinée à créer un KG dans le domaine de l'audit en faisant correspondre des documents de différents niveaux. Nous introduisons ensuite des méthodes pour la curation continue des KGs. Nous présentons un algorithme pour la fouille des règles conditionnelles et l'appliquons sur de grands KGs. Ensuite, nous décrivons RuleHub, un corpus extensible de règles pour les KGs publiques qui fournit des fonctionnalités pour l'archivage et la récupération des règles. Nous proposons également des méthodes pour l'exploitation des règles logiques dans deux applications différentes: l'apprentissage de règles souples à des modèles de langage pré-entraînés (RuleBert) et la vérification explicable des faits (ExpClaim)
Entity-centric knowledge graphs (KGs) are becoming increasingly popular for gathering information about entities. The schemas of KGs are semantically rich, with many different types and predicates to define the entities and their relationships. These KGs contain knowledge that requires understanding of the KG’s structure and patterns to be exploited. Their rich data structure can express entities with semantic types and relationships, oftentimes domain-specific, that must be made explicit and understood to get the most out of the data. Although different applications can benefit from such rich structure, this comes at a price. A significant challenge with KGs is the quality of their data. Without high-quality data, the applications cannot use the KG. However, as a result of the automatic creation and update of KGs, there are a lot of noisy and inconsistent data in them and, because of the large number of triples in a KG, manual validation is impossible. In this thesis, we present different tools that can be utilized in the process of continuous creation and curation of KGs. We first present an approach designed to create a KG in the accounting field by matching entities. We then introduce methods for the continuous curation of KGs. We present an algorithm for conditional rule mining and apply it on large graphs. Next, we describe RuleHub, an extensible corpus of rules for public KGs which provides functionalities for the archival and the retrieval of rules. We also report methods for using logical rules in two different applications: teaching soft rules to pre-trained language models (RuleBert) and explainable fact checking (ExpClaim)

APA, Harvard, Vancouver, ISO, and other styles

49

Hoonakker, Frank. "Graphes condensés de réactions, applications à la recherche par similarité, la classification et la modélisation." Université Louis Pasteur (Strasbourg) (1971-2008), 2008. https://publication-theses.unistra.fr/restreint/theses_doctorat/2008/HOONAKKER_Frank_2008.pdf.

Full text

Abstract:

Ce travail est consacré au développement de nouvelles méthodes de fouille de données dans le domaine des réactions en utilisant le concept de Graphe Condensé de Réaction (CGR). Le CGR est un graphe en 2D qui condense l’information contenue dans les réactifs et les produits d’une réaction. Grâce à la présence des liaisons conventionnelles (simples, doubles, etc. ) et dynamiques (coupure d’une liaison simple, transformation d’une double en simple etc. ), le CGR permet de condenser une réaction (incluant plusieurs molécules) en une pseudo-molécule. Ainsi, le CGR permettra d’appliquer des approches de chemoinformatique déjà développées pour les molécules. Trois applications possibles des CGRs ont été exploréees : – la classification non supervisée des réactions basées sur des algorithmes de clustering, – la recherche de réactions par similarité, – la modélisation structure-réactivité (QSRR, Quantitative Structure Reactivity Relationships). Ces méthodes, testées sur quatre bases de données contenant entre 1 000 et 200 000 réactions, ont démontré l’efficacité de l’approche et des logiciels développés. Un système d’optimisation de conditions réactionnelles a ainsi été implémenté et un brevet a été déposé aux États-Unis
This work is devoted to the developpement of new methods of mining of chemical reactions based on the Condensed Graph of Reaction (CGR) approach. A CGR integrates an information about all reactants and products of a given chemical reaction into one 2D molecular graph. Due to the application of both conventional (simple, double, etc. ) and dynamical (single to double, broken single, etc. ) bond types, a CGR ”condenses” a reaction (involving many molecules) into one pseudo-molecule. This formally allows one to apply to CGRs the chemoinformatics approaches earlier developed for individual compounds. Three possible applications of CGRs were considered: – unsupervised classification of reactions based on clustering algorithms; – reactions similarity search, and – Quantitative Structure Reactivity Relationships (QSRR). Model calculations performed on four databases containing from 1 000 to 200 000 reactions demonstrated high efficiency of the developed approaches and software tools. An system for optimizing reactions condition has been designed, and patented in the USA

APA, Harvard, Vancouver, ISO, and other styles

50

Slama, Olfa. "Flexible querying of RDF databases : a contribution based on fuzzy logic." Thesis, Rennes 1, 2017. http://www.theses.fr/2017REN1S089/document.

Full text

Abstract:

Cette thèse porte sur la définition d'une approche flexible pour interroger des graphes RDF à la fois classiques et flous. Cette approche, basée sur la théorie des ensembles flous, permet d'étendre SPARQL qui est le langage de requête standardisé W3C pour RDF, de manière à pouvoir exprimer i) des préférences utilisateur floues sur les données (par exemple, l'année de publication d'un album est récente) et sur la structure du graphe (par exemple, le chemin entre deux amis doit être court) et ii) des préférences utilisateur plus complexes, prenant la forme de propositions quantifiées floues (par exemple, la plupart des albums qui sont recommandés par un artiste, sont très bien notés et ont été créés par un jeune ami de cet artiste). Nous avons effectué des expérimentations afin d'étudier les performances de cette approche. L'objectif principal de ces expérimentations était de montrer que le coût supplémentaire dû à l'introduction du flou reste limité/acceptable. Nous avons également étudié, dans un cadre plus général, celui de bases de données graphe, la question de l'intégration du même type de propositions quantifiées floues dans une extension floue de Cypher qui est un langage déclaratif pour l'interrogation des bases de données graphe classiques. Les résultats expérimentaux obtenus montrent que le coût supplémentaire induit par la présence de conditions quantifiées floues dans les requêtes reste également très limité dans ce cas
This thesis concerns the definition of a flexible approach for querying both crisp and fuzzy RDF graphs. This approach, based on the theory of fuzzy sets, makes it possible to extend SPARQL which is the W3C-standardised query language for RDF, so as to be able to express i) fuzzy user preferences on data (e.g., the release year of an album is recent) and on the structure of the data graph (e.g., the path between two friends is required to be short) and ii) more complex user preferences, namely, fuzzy quantified statements (e.g., most of the albums that are recommended by an artist, are highly rated and have been created by a young friend of this artist). We performed some experiments in order to study the performances of this approach. The main objective of these experiments was to show that the extra cost due to the introduction of fuzziness remains limited/acceptable. We also investigated, in a more general framework, namely graph databases, the issue of integrating the same type of fuzzy quantified statements in a fuzzy extension of Cypher which is a declarative language for querying (crisp) graph databases. Some experimental results are reported and show that the extra cost induced by the fuzzy quantified nature of the queries also remains very limited

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Base de données graphes'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles