La recherche de points communs entre des descriptions de données ou de connaissances est un problème de raisonnement fondamental en Machine Learning, qui a été formalisé par G. Plotkin dans les années 70s sous la forme du calcul du plus petit généralisant de ces descriptions. L'identification des plus petits généralisants a un large panel d'applications qui vont de l'optimisation de requêtes (e.g., pour matérialiser les points communs entre des requêtes lors de la sélection de vues ou pour factoriser leur exécution dans un contexte d'accès concurrentiel), à la recommandation dans le contexte des réseaux sociaux (e.g. pour créer de liens entre des utilisateurs basées sur leurs points communs selon leur profil ou leurs recherches). Dans cette thèse nous avons revisité la notion du plus petit généralisant dans le contexte de Resource Description Framework (RDF) et le fragment conjonctif de son langage de requêtes associé SPARQL, alias Basic Graph Pattern (BGP) queries. Contrairement à l'état de l'art, nous ne considérons aucune restriction, ni structurelle ni sémantique, sur les graphes et les requêtes. Nos contributions incluent la définition et le calcul des plus petits généralisants dans ces deux formalismes ce qui revient à trouver le plus grand ensemble de points communs entre des bases de données incomplètes et des requêtes conjonctives en présence de contraintes déductives. Nous proposons également une évaluation expérimentale de nos contributions. / Finding commonalities between descriptions of data or knowledge is a fundamental task in Machine Learning. The formal notion characterizing precisely such commonalities is known as least general generalization of descriptions and was introduced by G. Plotkin in the early 70's, in First Order Logic. Identifying least general generalizations has a large scope of database applications ranging from query optimization (e.g., to share commonalities between queries in view selection or multi-query optimization), to recommendation in social networks (e.g., to establish connections between users based on their commonalities between proles or searches), through exploration (e.g., to classify/categorize datasets and to identify common social graph patterns between organizations (e.g., criminal ones)). In this thesis we revisit the notion of least general generalizations in the entire Resource Description Framework (RDF) and popular conjunctive fragment of SPARQL, a.k.a. Basic Graph Pattern (BGP) queries. By contrast to the literature, we do not restrict the structure nor semantics of RDF graphs and BGPQs. Our contributions include the denition and the computation of least general generalizations in these two settings, which amounts to nding the largest set of commonalities between incomplete databases and conjunctive queries, under deductive constraints. We also provide an experimental assessment of our technical contributions.

Ces deux dernières décennies les systèmes P2P de partage de fichiers sont devenus très populaires grâce aux accès à des ressources diverses, distribuées sur Internet. Parallèlement à l'évolution de cette catégorie de systèmes, les dispositifs mobiles (téléphones cellulaires, PDA et autres appareils portatifs) ont eu un grand succès sur le marché. Équipés d'une technologie de communication sans fil (Bluetooth, et Wifi), ils peuvent communiquer sans nécessiter une infrastructure particulière en utilisant un réseau mobile adhoc (Mobile Adhoc NETwork -MANET). De la même manière, les systèmes P2P peuvent être aussi déployés sur ce type de réseau et deviennent des systèmes P2P mobiles (Mobile 2P systems). Dans le cadre de cette thèse, nous nous intéressons essentiellement à la recherche d'information dans les systèmes P2P et plus précisément au problème de routage de requêtes. La première partie de la thèse, s'est focalisée sur le routage de requêtes dans les systèmes P2P sur Internet. Nous avons proposé (i) un modèle de routage sémantique basé sur l'historique des requêtes. Ce modèle est ensuite instancié pour définir une nouvelle méthode de routage par apprentissage. Pour pallier le problème de démarrage à froid, (ii) nous avons proposé une méthode prédictive de l'intention de l'utilisateur qui construit une base de connaissances à priori pour chaque pair. Enfin, (iii) nous avons proposé une méthode de routage hybride pour traiter le problème d'échec de sélection. Cette méthode est basée sur l'historique des requêtes et le regroupement de pairs dans des groupes sémantiques. La deuxième partie de la thèse, s'est focalisée sur le routage de requêtes dans les systèmes P2P mobiles. L'apparition des MANETs, a soulevé de nouveaux challenges de routage. Ces réseaux souffrent de plusieurs contraintes liées aux supports de transmission ou bien aux dispositifs mobiles. Dans ce cadre, nous avons proposé une méthode de routage pour les systèmes P2P non structurés mobiles basée sur le contexte de l'utilisateur. D'un point de vue technique, toutes ces propositions ont été développées, validées et évaluées grâce aux simulateurs PeerSim et NS2 / Peer-to-peer systems have emerged as platforms for users to search and share information over the Internet. In fact, thanks to these systems, user can share various resources, send queries to search and locate resources shared by other users. Nowadays, mobile and wireless technology has achieved great progress. These devices are also equipped with low radio range technology, like Bluetooth and Wi-Fi, etc. By means of the low radio range technology, they can communicate with each other without using communication infrastructure (e.g. Internet network) and form a mobile ad hoc network (MANET). Hence, P2P file sharing systems can be also deployed over MANET. A challenging problem in unstructured P2P systems is query routing. Researches' efficiency and effectiveness can be improved by making smart decisions for query routing. Our contributions, in this thesis, focus on two complementary axes. Firstly, our research work focalized on P2P systems over Internet. We introduced a novel semantic model for query routing based on past queries, thereafter we instantiated this model to define our specific routing method. In addition, we addressed two difficult challenging problems: (i) the bootstraping (ii) the unsuccessful relevant peers search. Secondly, we are focalized on P2P systems over MANET. Due the nature of MANET, mobile P2P systems suffer from several constraints of wireless medium and energy-limited. Indeed, query routing methods proposed for P2P system over Internet cannot be applied. In this context, we proposed a context-aware integrated routing method for P2P file sharing systems over MANET. The different contributions are developed, validated and evaluated with the network simulators PeerSim and NS2

La recherche d'information (RI) est un domaine de recherche qui est de plus en plus visible, surtout avec la profusion de données (textes, images, vidéos, etc) sur Internet.<br />Nous nous intéressons dans cette thèse à la RI à partir de documents textuels non structurés.<br />Trois éléments sont essentiels dans un processus de RI : un besoin d'information (généralement exprimé sous la forme d'une requête), un système de recherche d'information (SRI), et une collection de documents. Ainsi, la requête est soumise au SRI qui<br />recherche dans la collection les documents les plus pertinents pour la requête. La variabilité relative à l'expression de la requête, la relation entre la requête et les documents, ainsi que celle liée aux caractéristiques des SRI utilisés conduisent à des variabilités dans les réponses obtenues (Buckley et al., 2004). Ainsi, le système A peut être très<br />performant pour une requête donnée et être très médiocre pour une autre requête, alors que le système B conduira à des résultats inversés.<br />Notre thèse se situe dans ce contexte. Notre objectif est de proposer des méthodes de recherche pouvant s'intégrer dans un modèle de recherche capable de s'adapter à différents contextes. Nous considérons par exemple que les caractéristiques linguistiques (CL) des requêtes, les performances locales des systèmes ainsi que leurs caractéristiques<br />sont des éléments définissant différents contextes. Nous proposons plusieurs processus afin d'atteindre cet objectif. D'une part, nous utilisons un profil linguistique des requêtes (Mothe et Tanguy, 2005) qui nous permet d'établir une classification des requêtes à base de leurs CL. Nous utilisons à cet effet des techniques statistiques d'analyse de données telles que la classification ascendante hiérarchique (CAH) et les k-means. Les requêtes ne sont plus alors considérées de manière isolée, mais sont vues comme des groupes possédant des CL similaires. L'hypothèse sous-jacente que nous faisons est qu'il existe des contextes dans lesquels certains SRI sont plus adaptés que d'autres. Nous étudions alors les performances des systèmes sur les classes de requêtes obtenues (contextes). Nous proposons quatre méthodes de fusion afin de combiner les résultats obtenus pour une requête donnée, par différents SRI. Une série d'expérimentations valide nos propositions. <br />L'ensemble de ces travaux s'appuie sur l'évaluation au travers des campagnes d'évaluation de TREC.

Les systèmes de médiation sont aujourd'hui largement développés et connus. Cependant, leur mise en œuvre pose un certain nombre de problèmes, en particulier la définition de requêtes de médiation en présence d'un grand nombre de sources de données, et d'un volume important de méta-données les décrivant. Ce problème est d'autant plus complexe que les sources sont hétérogènes.<br />Face a cette problématique, nous proposons dans cette thèse pour le contexte relationnel, une approche de génération automatique de requêtes de médiation. A partir de la description d'un ensemble de sources de données distribuées et hétérogènes et de méta-données, notre algorithme produit un ensemble de requêtes de médiation possibles. Nous avons développé un outil qui permet de générer automatiquement des requêtes de médiation dans un environnement hétérogène. Notre objectif principal étant de fournir à l'utilisateur un outil adapté aux petits et grands systèmes, nous avons réalisé une série de tests d'évaluation des performances pour mesurer son passage à l'échelle. Ces tests montrent la faisabilité de notre approche.

.

Un SGBD temporel doit offrir les fonctionnalités permettant aux applications de dater les informations et de gérer l'histoire de leur évolution. Cette thèse présente le modèle d'historiques TEMPOS et le prototype qui a été réalisé au dessus du SGBD O2. TEMPOS s'appuie sur un modèle du temps, qui permet de manipuler des valeurs temporelles, simples et complexes, exprimées dans différentes unités. Le jeu d'unité est extensible, et les opérations définies sont indépendantes des unités. La multiplicité des formes externes des valeurs temporelles est également prise en compte. Le modèle d'historiques proposé dans TEMPOS intègre les fonctionnalités essentielles attendues pour gérer la dimension historique des informations d'une base de données. La définition de différents types d'historiques (discret, en escalier, interpolé) permet de donner la signification des valeurs saisies et d'interpoler les autres valeurs. Ainsi, en TEMPOS, un historique est vu comme une chronique (séquence de valeurs datées), un domaine temporel d'observation, et une fonction d'interpolation. Le modèle permet diverses structurations des historiques basées sur le regroupement d'instants. Les opérations d'interrogation des historiques sont issues de l'extension temporelle des opérateurs de l'algèbre relationnelle et également d'une adaptation d'opérateurs sur les séquences, qui permettent en particulier de raisonner sur la succession dans le temps. Les opérations classiques de mise à jour sont étendues pour prendre en compte la dimension temporelle. Toutes les opérations sur les historiques sont définies de manière à être indépendantes de la représentation et de l'unité d'observation temporelle des historiques. Le prototype comprend une hiérarchie de classes implantant les types et les opérations proposés dans TEMPOS, et un préprocesseur TempOQL permettant de manipuler des valeurs temporelles dans des requêtes OQL.

Le développement de l'internet a conduit à une grande augmentation de l'information disponible pour les utilisateurs. Ces utilisateurs veulent exprimer leur besoins de manière simple, par l'intermédiaire des requêtes, et ils veulent que ces requêtes soient évaluées sans se soucier où les données sont placées ou comment les requêtes sont évaluées. Le travail qui est présenté dans cette thèse contribue à l'objectif de la gestion du contenu du Web de manière déclarative et efficace et il est composé de deux parties. Dans le premier partie, nous présentons OptimAX, un optimiseur pour la langage Active XML qui est capable de reécrire un document Active XML donné dans un autre document équivalent dont l'évaluation sera plus efficace. OptimAX contribue à résoudre le problème d'optimisation des requêtes distribuées dans le cadre d'Active XML et nous présentons deux études de cas. Dans le deuxième partie, nous proposons une solution au problème de l'optimisation d'un point de vue différent. Nous optimisons des requêtes en utilisant un ensemble des requêtes pré-calculées (vues matérialisées). Nous avons développé une plateforme pair-à-pair, qui s'appelle ViP2P (views in peer-to-peer) qui permet aux utilisateurs de publier des documents XML et de spécifier des vues sur ces documents en utilisant une langage de motifs d'arbres. Quand un utilisateur pose une requête, le système essaiera de trouver des vues qui peuvent être combinées pour construire une réécriture équivalente à la requête. Nous avons fait des expérimentations en utilisant des ordinateurs des différents laboratoires en France et nous avons montré que notre plateforme passe à l'échelle jusqu'à plusieurs GB de données.

Avec le nombre croissant d'utilisateurs novices des applications informatiques, le besoin d'une aide efficace est devenu critique. Afin de répondre à ce besoins, nous suggérons d'utiliser un Agent Conversationnel Assistant (ACA), c'est-à-dire une interface permettant l'utilisation de la langue naturelle (en effet celle-ci est utilisée spontanément dès qu'un problème surgit) ainsi qu'une présence rassurante pour les utilisateurs.Une étude préliminaire détaille la constitution (en combinant la collecte et l'utilisation de thesaurus) d'un corpus de requêtes dont nous justifions le besoin. Ce corpus de 11626 requêtes est comparé avec d'autres corpus existants et nous montrons qu'il couvre le domaine étudié d'aide et que de plus, il contient des requêtes portant d'une part sur le contrôle de l'application et d'autre part des phrases de 'clavardage'. Ce corpus fournit une base saine pour la conception d'un analyseur syntactico-sémantique de requêtes en langage naturel, utilisant un jeu de classes (keys) sémantiques, un jeu de règles d'analyse et un jeu de règles de transformation. En entrée, les requêtes sont exprimées dans un langage formel (DAFT) pour lequel nous proposons une syntaxe et une sémantique. L'analyseur est alors évalué en comparant une annotation manuelle avec les requêtes produites automatiquement et nous étudions l'usage de techniques d'apprentissage supervisé afin d'identifier les classes d'activités conversationnelles. La méthodologie employée est validée via l'intégration d'un ACA dans une application Web existante , dédiée au prototypage collectif de la musique sur Internet. Enfin, nous décrivons l'architecture requise pour implémenter un agent rationnel qui a pour rôle de définir les réactions aux requêtes formelles des usagers, exprimées en DAFT ainsi que le modèle de l'application assistée, mettant ainsi en lumière le besoin d'un modèle cognitif.

The so-called Web 2.0 revolution has fundamentally changed the way people interact with the Internet. The Web has turned from a read-only infrastructure to a collaborative platform. By expressing their preferences and sharing private information, the users benefit from a personalized Web experience. Yet, these systems raise several problems in terms of \emph{privacy} and \emph{scalability}. The social platforms use the user information for commercial needs and expose the privacy and preferences of the users. Furthermore, centralized personalized systems require costly data-centers. As a consequence, existing centralized social platforms do not exploit the full extent of the personalization possibilities. In this thesis, we consider the design of social networks and social information services in the context of \emph{peer-to-peer} (P2P) networks. P2P networks are decentralized architecture, thus the users participates to the service and control their own data. This greatly improves the privacy of the users and the scalability of the system. Nevertheless, building social systems in a distributed context also comes with many challenges. The information is distributed among the users and the system has be able to efficiently locate relevant data. The contributions of this thesis are as follow. We define the \emph{cold start link prediction} problem, which consists in predicting the edges of a social network solely from the social information of the users. We propose a method based on a \emph{probabilistic graph} to solve this problem. We evaluate it on a dataset from Flickr, using the group membership as social information. Our results show that the social information indeed enables a prediction of the social network. Thus, the centralization of the information threatens the privacy of the users, hence the need for decentralized systems. We propose \textsc{SoCS}, a \emph{decentralized} algorithm for \emph{link prediction}. Recommending neighbors is a central functionality in social networks, and it is therefore crucial to propose a decentralized approach as a first step towards P2P social networks. \textsc{SoCS} relies on gossip protocols to perform a force-based embedding of the social networks. The social coordinates are then used to predict links among vertices. We show that \textsc{SoCS} is adapted to decentralized systems at it is churn resilient and has a low bandwidth consumption. We propose \textsc{GMIN}, a \emph{decentralized} platform for \emph{personalized services} based on social information. \textsc{GMIN} provides each user with neighbors that share her interests. The clustering algorithm we propose takes care to encompass all the different interests of the user, and not only the main ones. We then propose a personalized \emph{query expansion} algorithm (\textsc{GQE}) that leverages the \textsc{GMIN} neighbors. For each query, the system computes a tag centrality based on the relations between tags as seen by the user and her neighbors.

XML est un langage générique de description de données destiné à l'origine au stockage, au traitement et à l'échange d'informations sur Internet ; il s'agit aujourd'hui d'un format standard pour les communautés bases de données, documents ou technologies Web, qui est utilisé dans de nombreuses applications. Le format des données traitées par celles-ci est généralement spécifié par un schéma XML. Il s'agit d'une méta-description permettant de contraindre la structure et le type des données des documents XML qui le respectent.<br/><br/> Interroger les documents afin d'en extraire des informations est une tâche essentielle en informatique. Les requêtes de sélection de nœuds sont ainsi à la base de la transformation de documents XML. Cependant, la plupart des outils existants pour définir des requêtes sur les documents XML présupposent des connaissances techniques de la part de l'utilisateur. L'induction de requêtes supervisée est au contraire un moyen d'élaborer des tâches d'extraction d'information sans prérequis. Dans un tel système, une interface graphique permet à l'utilisateur d'annoter des documents qui servent d'exemples. Un algorithme d'apprentissage est alors utilisé pour inférer la requête.<br/><br/> Dans cette thèse, nous proposons d'utiliser les connaissances fournies par le schéma XML dans les algorithmes d'induction de requêtes basés sur une technique d'inférence grammaticale. En tant que langages réguliers d'arbres, les schémas peuvent être facilement représentés par des automates d'arbres. Leur utilisation dans des algorithmes d'inférence d'automates apparaît donc particulièrement appropriée. Nous en avons distingué deux.<br/><br/> 1. La première idée est de contraindre la requête inférée à être consistante avec le schéma. Pour cela, nous avons mis au point un test d'inclusion efficace dans les automates d'arbres factorisés déterministes, un modèle d'automates permettant de représenter les DTD de façon compacte que nous avons introduit.<br/><br/> 2. La seconde idée est que les informations contenues dans le schéma peuvent être précieuses pour élaguer les arbres correspondants à des documents annotés. L'élagage est nécessaire lorsque les documents traités sont gros et/ou annotés partiellement. En contrepartie, il n'est plus possible d'inférer toutes les requêtes régulières. Nous donnons une caractérisation de la classe de requêtes apprenables à partir d'un ensemble d'arbres annotés élagués, à savoir les requêtes stables.<br/><br/> Nous avons implémenté et testé nos algorithmes d'induction de requêtes guidée par schéma. Le système développé permet de simuler le comportement d'un utilisateur lors de la définition d'une nouvelle requête. Les résultats de nos expériences soutiennent la pertinence de notre approche. Ils montrent en effet que l'usage du schéma permet d'améliorer l'apprentissage.