Search

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.; 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.; 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.

Mining object movement patterns to understand the behavior of moving objects has many high impact applications. However even if existing pattern models are meaningful, there are still challenging issues such as: 1) there are many kinds of patterns and algorithms without an efficient management scheme, 2) lacking of relevant approaches in dealing with time gaps, 3) they usually focus on an unchanged group of objects and thus do not capture the behavior of the whole object class, 4) Naturally, there are huge amount of very redun- dant movement patterns extracted while only a few of them are meaningful. However, few researchers address this issue. 5) Despite the growing demands for diverse applications, there have been few scalable tools for mining massive and sophisticated moving object data.In my thesis, I will mainly focus on addressing these issues. We propose the three step framework: 1) the first step aims to present and framework to mine and manage different existing movement patterns in an efficient way, 2) in the second step, we propose novel movement pattern concepts to access the relevance of movement patterns by dealing with time gaps. We also further present the gradual trajectory pattern notion to analysis the behavior of moving objects in a graduality point of view. 3) In the last step, we propose an novel MDL principal-based approach, named SmartCompo to extract representative movement patterns from moving object data. 4) Our three step framework is illustrated in a demonstration system, named Multi_Move, which is designed to extract and manage dif- ferent kinds of spatio-temporal patterns concurrently. A user-friendly interface is provided to facilitate interactive exploration of mining results.As an extra work, I further present the concept of multi-relational gradual pattern which generalizes the gradual pattern notion in single relation data to multi-relation database.; La fouille de motifs d'objets en mouvement pour mieux appréhender le comportement des objets a de très nombreuses applications. Cependant, même si les modèles de motifs existants sont très pertinents, il existe de nombreuses challenges: 1) il existe de très nombreux types de motifs qu'il est difficile d'appréhender, 2) il n'existe pas d'approches qui considèrent véritablement les différences entre estampilles temporelles, 3) elles se focalisent sur un seul type de motifs et ne sont donc pas capable de faire émerger d'autres motifs qui pourraient être intéressant, 4) elles engendrent une grande quantité de motifs et seulement quelques uns d'entre eux sont utiles, 5) généralement elles ne sont pas capables de prendre en compte des données fortement très volumineuses et évolutives.Dans cette thèse, je fais différentes propositions pour répondre à ces challenges. Nous proposons une approche en trois étapes : 1) la première étape propose une approche unifiée pour extraire l'ensemble des trajectoires de la literature, 2) nous proposons ensuite une nouvelle approche originale pour gérer les évolutions au cours du temps des trajectoires et proposons la notion de trajectoires graduelles pour analyser le comportement des objets de manière graduelle, 3) dans la dernière étape nous proposons une approche, appelée SmartCombo, inspirée de MDL, pour extraire l'ensemble des trajectoires représentatives (top-k) à partir de données spatio-temporelles. Nous montrons également le système développé, Multi-Move, qui via une interface graphique permet d'extraire et de visualiser l'ensemble des trajectoires. En complément nous présentons également des recherches que nous avons menées pour généraliser les motifs graduels en prenant en compte des bases de données multi-relationnelles.