Les masses de données scientifiques générées par les moyens d'observation modernes, dont l’observation spatiale, soulèvent des problèmes de performances récurrents, et ce malgré les avancées des systèmes distribués de gestion de données. Ceci est souvent lié à la complexité des systèmes et des paramètres qui impactent les performances et la difficulté d’adapter les méthodes d’accès au flot de données et de traitement.Cette thèse propose de nouvelles techniques d'optimisations logiques et physiques pour optimiser les plans d'exécution des requêtes astronomiques en utilisant des règles d'optimisation. Ces méthodes sont intégrées dans ASTROIDE, un système distribué pour le traitement de données astronomiques à grande échelle.ASTROIDE allie la scalabilité et l’efficacité en combinant les avantages du traitement distribué en utilisant Spark avec la pertinence d’un optimiseur de requêtes astronomiques.Il permet l'accès aux données à l'aide du langage de requêtes ADQL, couramment utilisé.Il implémente des algorithmes de requêtes astronomiques (cone search, kNN search, cross-match, et kNN join) en exploitant l'organisation physique des données proposée.En effet, ASTROIDE propose une méthode de partitionnement des données permettant un traitement efficace de ces requêtes grâce à l'équilibrage de la répartition des données et à l'élimination des partitions non pertinentes. Ce partitionnement utilise une technique d’indexation adaptée aux données astronomiques, afin de réduire le temps de traitement des requêtes. / The big scientific data generated by modern observation telescopes, raises recurring problems of performances, in spite of the advances in distributed data management systems. The main reasons are the complexity of the systems and the difficulty to adapt the access methods to the data. This thesis proposes new physical and logical optimizations to optimize execution plans of astronomical queries using transformation rules. These methods are integrated in ASTROIDE, a distributed system for large-scale astronomical data processing.ASTROIDE achieves scalability and efficiency by combining the benefits of distributed processing using Spark with the relevance of an astronomical query optimizer.It supports the data access using the query language ADQL that is commonly used.It implements astronomical query algorithms (cone search, kNN search, cross-match, and kNN join) tailored to the proposed physical data organization.Indeed, ASTROIDE offers a data partitioning technique that allows efficient processing of these queries by ensuring load balancing and eliminating irrelevant partitions. This partitioning uses an indexing technique adapted to astronomical data, in order to reduce query processing time.

Le développement récent des offres commerciales autour du cloud computing a fortement influé sur la recherche et le développement des plateformes de distribution numérique. Les fournisseurs du cloud offrent une infrastructure de distribution extensible qui peut être utilisée pour le stockage et le traitement des données.En parallèle avec le développement des plates-formes de cloud computing, les modèles de programmation qui parallélisent de manière transparente l'exécution des tâches gourmandes en données sur des machines standards ont suscité un intérêt considérable, à commencer par le modèle MapReduce très connu aujourd'hui puis par d'autres frameworks plus récents et complets. Puisque ces modèles sont de plus en plus utilisés pour exprimer les tâches de traitement de données analytiques, la nécessité se fait ressentir dans l'utilisation des langages de haut niveau qui facilitent la charge de l'écriture des requêtes complexes pour ces systèmes.Cette thèse porte sur des modèles et techniques d'optimisation pour le traitement efficace de grandes masses de données du Web sur des infrastructures à grande échelle. Plus particulièrement, nous étudions la performance et le coût d'exploitation des services de cloud computing pour construire des entrepôts de données Web ainsi que la parallélisation et l'optimisation des langages de requêtes conçus sur mesure selon les données déclaratives du Web.Tout d'abord, nous présentons AMADA, une architecture d'entreposage de données Web à grande échelle dans les plateformes commerciales de cloud computing. AMADA opère comme logiciel en tant que service, permettant aux utilisateurs de télécharger, stocker et interroger de grands volumes de données Web. Sachant que les utilisateurs du cloud prennent en charge les coûts monétaires directement liés à leur consommation de ressources, notre objectif n'est pas seulement la minimisation du temps d'exécution des requêtes, mais aussi la minimisation des coûts financiers associés aux traitements de données. Plus précisément, nous étudions l'applicabilité de plusieurs stratégies d'indexation de contenus et nous montrons qu'elles permettent non seulement de réduire le temps d'exécution des requêtes mais aussi, et surtout, de diminuer les coûts monétaires liés à l'exploitation de l'entrepôt basé sur le cloud.Ensuite, nous étudions la parallélisation efficace de l'exécution de requêtes complexes sur des documents XML mis en œuvre au sein de notre système PAXQuery. Nous fournissons de nouveaux algorithmes montrant comment traduire ces requêtes dans des plans exprimés par le modèle de programmation PACT (PArallelization ConTracts). Ces plans sont ensuite optimisés et exécutés en parallèle par le système Stratosphere. Nous démontrons l'efficacité et l'extensibilité de notre approche à travers des expérimentations sur des centaines de Go de données XML.Enfin, nous présentons une nouvelle approche pour l'identification et la réutilisation des sous-expressions communes qui surviennent dans les scripts Pig Latin. Notre algorithme, nommé PigReuse, agit sur les représentations algébriques des scripts Pig Latin, identifie les possibilités de fusion des sous-expressions, sélectionne les meilleurs à exécuter en fonction du coût et fusionne d'autres expressions équivalentes pour partager leurs résultats. Nous apportons plusieurs extensions à l'algorithme afin d’améliorer sa performance. Nos résultats expérimentaux démontrent l'efficacité et la rapidité de nos algorithmes basés sur la réutilisation et des stratégies d'optimisation. / The recent development of commercial cloud computing environments has strongly impacted research and development in distributed software platforms. Cloud providers offer a distributed, shared-nothing infrastructure, that may be used for data storage and processing.In parallel with the development of cloud platforms, programming models that seamlessly parallelize the execution of data-intensive tasks over large clusters of commodity machines have received significant attention, starting with the MapReduce model very well known by now, and continuing through other novel and more expressive frameworks. As these models are increasingly used to express analytical-style data processing tasks, the need for higher-level languages that ease the burden of writing complex queries for these systems arises.This thesis investigates the efficient management of Web data on large-scale infrastructures. In particular, we study the performance and cost of exploiting cloud services to build Web data warehouses, and the parallelization and optimization of query languages that are tailored towards querying Web data declaratively.First, we present AMADA, an architecture for warehousing large-scale Web data in commercial cloud platforms. AMADA operates in a Software as a Service (SaaS) approach, allowing users to upload, store, and query large volumes of Web data. Since cloud users support monetary costs directly connected to their consumption of resources, our focus is not only on query performance from an execution time perspective, but also on the monetary costs associated to this processing. In particular, we study the applicability of several content indexing strategies, and show that they lead not only to reducing query evaluation time, but also, importantly, to reducing the monetary costs associated with the exploitation of the cloud-based warehouse.Second, we consider the efficient parallelization of the execution of complex queries over XML documents, implemented within our system PAXQuery. We provide novel algorithms showing how to translate such queries into plans expressed in the PArallelization ConTracts (PACT) programming model. These plans are then optimized and executed in parallel by the Stratosphere system. We demonstrate the efficiency and scalability of our approach through experiments on hundreds of GB of XML data.Finally, we present a novel approach for identifying and reusing common subexpressions occurring in Pig Latin scripts. In particular, we lay the foundation of our reuse-based algorithms by formalizing the semantics of the Pig Latin query language with extended nested relational algebra for bags. Our algorithm, named PigReuse, operates on the algebraic representations of Pig Latin scripts, identifies subexpression merging opportunities, selects the best ones to execute based on a cost function, and merges other equivalent expressions to share its result. We bring several extensions to the algorithm to improve its performance. Our experiment results demonstrate the efficiency and effectiveness of our reuse-based algorithms and optimization strategies.

La Cour Européenne des droits de l’homme, depuis les années 1990, connait une extension de ses compétences ratione personae et ratione loci sans précèdent. Faire face à ce phénomène exceptionnel requiert des instruments nouveaux. L’objet de cette étude réside dans l’examen des techniques adaptées par la Cour afin de maintenir le niveau de protection des droits de l’homme garantis par la Convention. Par ailleurs les organes et les Etats membres du Conseil de l’Europe participèrent grandement à l’effort de conservation du niveau d’excellence de protection des droits de l’homme en Europe. Ce sont ces aspects précis qui sont passés en revue et apprécié sous l’angle de leurs apports et parfois, inconvénients. Sujet d’étude apporté dans un espace-temps précis, il demanderait dans un avenir d’être complété et apprécié sous cet angle. / The European Court of Human Rights, since the 1990s, recognizes an unprecedented extension of its competence ratione personae and ratione loci. In order to face this exceptional phenomenon new instruments are required. The purpose of this study is the examination of new techniques adapted by the Court to maintain the level of protection of human rights guaranteed by the Convention. Other organs and Member States of the Council of Europe participated actively to the efforts in order to conserve the excellent level for the protection of human rights in Europe. These are specific areas having been reviewed and valued in terms of their contribution and sometimes their disadvantages. Prepared in a particular space-time, this study would ask in the future to be completed and assessed from this angle.

La popularité croissante des applications Internet très gourmandes en bande passante (P2P, streaming,...) nous pousse à considérer le problème suivant :Comment construire des systèmes de communications collectives efficaces sur une plateforme à grande échelle ? Le développement de schéma de communications collectives dans le cadre d'un réseau distribué à grande échelle est une tâche difficile, qui a été largement étudiée et dont de multiples solutions ont été proposées. Toutefois, une nouvelle approche globale et systématique est nécessaire, une approche qui combine des modèles de réseaux et la conception algorithmique.Dans ce mémoire nous proposons l'utilisation de modèles capables de capturer le comportement d'un réseau réel et suffisamment simples pour que leurs propriétés mathématiques puissentêtre étudiées et pour qu'il soit possible de créer des algorithmesoptimaux. Premièrement, nous considérons le problème d'évaluation de la bande passante disponible pour une connexion point-à-point donnée. Nousétudions la façon d'obtenir des jeux de données de bande passante, utilisant plateforme PlanetLab. Nous présentons aussi nos propres jeux de données, jeux obtenus avec bedibe, un logiciel que nous avons développé. Ces données sont nécessaires pour évaluer les performances des différents algorithmesde réseau. Bien qu'on trouve de nombreux jeux de données de latence,les jeux de données de bande passante sont très rares. Nous présentons ensuite un modèle, appelé LastMile, qui estime la bande passante. En profitant des jeux de données décrits précédemment, nous montrons que cet algorithme est capable de prédire la bande passante entre deux noeuds donnés avec une précision comparable au meilleur algorithme connu de prédiction (DMF). De plus le modèle LastMile s'étend naturellement aux prédictions dans le scénario de congestion (plusieurs connexions partageant un même lien). Nous sommes effectivement en mesure de démontrer, à l'aide des ensembles de données PlanetLab, que la prédiction LastMile est préférable dans des tels scénarios.Dans le troisième chapitre, nous proposons des nouveaux algorithmes pour résoudre le problème de diffusion. Nous supposons que le réseau est modélisé par le modèle LastMile. Nous montrons que, sous cette hypothèse, nous sommes en mesure de fournir des algorithmes avec des ratios d'approximation élevés. De plus nous étendons le modèle LastMile, de manière à y intégrer des artéfacts de connectivité, dans notre cas ce sont des firewalls qui empêchent certains nœuds de communiquer directement entre eux. Dans ce dernier cas, nous sommes également en mesure de fournir des algorithmes d'approximation avec des garanties de performances prouvables. Les chapitres 1 à 3 forment les trois étapes accomplies de notre programme qui visent trois buts. Premièrement, développer à partir dezéro un modèle de réseau de communication. Deuxièmement, prouver expérimentalement sa performance. Troisièmement, montrer qu'il peut être utilisé pour développer des algorithmes qui résolvent les problèmes de communications collectives. Dans le 4e chapitre, nous montrons comment on peut concevoir dessystèmes de communication efficaces, selon différents modèles decoûts, en utilisant des techniques combinatoires,tout en utilisant des hypothèses simplificatrices sur la structure duréseau et les requêtes. Ce travail est complémentaire au chapitre précédent puisque auparavant, nous avons adopté l'hypothèse que les connectionsétaient autonomes (i.e. nous n'avons aucun contrôle sur le routage des connexions simples). Dans le chapitre 4, nous montrons comment résoudre le problème du routage économe en énergie, étant donnée une topologie fixée. / The increasing popularity of Internet bandwidth-intensive applications prompts us to consider followingproblem: How to compute efficient collective communication schemes on large-scale platform?The issue of designing a collective communication in the context of a large scale distributed networkis a difficult and a multi-level problem. A lot of solutions have been extensively studied andproposed. But a new, comprehensive and systematic approach is required, that combines networkmodels and algorithmic design of solutions.In this work we advocate the use of models that are able to capture real-life network behavior,but also are simple enough that a mathematical analysis of their properties and the design of optimalalgorithms is achievable.First, we consider the problem of the measuring available bandwidth for a given point-topointconnection. We discuss how to obtain reliable datasets of bandwidth measurements usingPlanetLab platform, and we provide our own datasets together with the distributed software usedto obtain it. While those datasets are not a part of our model per se, they are necessary whenevaluating the performance of various network algorithms. Such datasets are common for latencyrelatedproblems, but very rare when dealing with bandwidth-related ones.Then, we advocate for a model that tries to accurately capture the capabilities of a network,named LastMile model. This model assumes that essentially the congestion happens at the edgesconnecting machines to the wide Internet. It has a natural consequence in a bandwidth predictionalgorithm based on this model. Using datasets described earlier, we prove that this algorithm is ableto predict with an accuracy comparable to best known network prediction algorithm (DistributedMatrix Factorization) available bandwidth between two given nodes. While we were unable toimprove upon DMF algorithm in the field of point-to-point prediction, we show that our algorithmhas a clear advantage coming from its simplicity, i.e. it naturally extends to the network predictionsunder congestion scenario (multiple connections sharing a bandwidth over a single link). We areactually able to show, using PlanetLab datasets, that LastMile prediction is better in such scenarios.In the third chapter, we propose new algorithms for solving the large scale broadcast problem.We assume that the network is modeled by the LastMile model. We show that under thisassumption, we are able to provide algorithms with provable, strong approximation ratios. Takingadvantage of the simplicity and elasticity of the model, we can even extend it, so that it captures theidea of connectivity artifacts, in our case firewalls preventing some nodes to communicate directlybetween each other. In the extended case we are also able to provide approximation algorithmswith provable performance.The chapters 1 to 3 form three successful steps of our program to develop from scratch amathematical network communication model, prove it experimentally, and show that it can beapplied to develop algorithms solving hard problems related to design of communication schemesin networks.In the chapter 4 we show how under different network cost models, using some simplifyingassumptions on the structure of network and queries, one can design very efficient communicationschemes using simple combinatorial techniques. This work is complementary to the previous chapter in the sense that previously when designing communication schemes, we assumed atomicityof connections, i.e. that we have no control over routing of simple connections. In chapter 4 weshow how to solve the problem of an efficient routing of network request, given that we know thetopology of the network. It shows the importance of instantiating the parameters and the structureof the network in the context of designing efficient communication schemes.

Le langage XML est devenu un standard de représentation et d'échange de données à travers le web. Le but de la réplication de données au sein de différents sites est de minimiser le temps d'accès à ces données partagées. Cependant, différents problèmes sont liés à la sécurisation de ces données. Le but de cette thèse est de proposer des modèles de contrôles d'accès XML qui prennent en compte les droits de lecture et de mise-à-jour et qui permettent de surmonter les limites des modèles qui existent. Nous considérons les langages XPath et XQuery Update Facility pour la formalisation des requêtes d'accès et des requêtes de mise-à-jour respectivement. Nous donnons des descriptions formelles de nos modèles de contrôles d'accès et nous présentons des algorithmes efficaces pour le renforcement des politiques de sécurité spécifiées à la base de ces modèles. L'autre partie de cette thèse est consacrée à l'étude pratique de nos propositions. Nous présentons notre système appelé SVMAX qui met en oeuvre nos solutions, et nous conduisons une étude expérimentale basée sur une DTD réelle pour montrer son efficacité. Plusieurs systèmes de bases de données natives (systèmes de BDNs) ont été proposés récemment qui permettent une manipulation efficace des données XML en utilisant la plupart des standards du W3C. Nous montrons que notre système SVMAX peut être intégré facilement et efficacement au sein d'un large ensemble de systèmes de BDNs. A nos connaissances, SVMAX est le premier système qui permet la sécurisation des données XML conformes à des DTDs arbitraires (récursives ou non) et ceci en moyennant un fragment significatif de XPath et une classe riche d'opérations de mise-à-jour XML / XML has become a standard for representation and exchange of data across the web. Replication of data within different sites is used to increase the availability of data by minimizing the access's time to the shared data. However, the safety of the shared data remains an important issue. The aim of the thesis is to propose some models of XML access control that take into account both read and update rights and that overcome limitations of existing models. We consider the XPath language and the XQuery Update Facility to formalize respectively user access queries and user update operations. We give formal descriptions of our read and update access control models and we present efficient algorithms to enforce policies that can be specified using these models. Detailed proofs are given that show the correctness of our proposals. The last part of this thesis studies the practicality of our proposals. Firstly, we present our system, called SVMAX, that implements our solutions and we conduct an extensive experimental study, based on real-life DTD, to show that it scales well. Many native XML databases systems (NXD systems) have been proposed recently that are aware of the XML data structure and provide efficient manipulation of XML data by the use of most of W3C standards. Finally, we show that our system can be integrated easily and efficiently within a large set of NXD systems, namely BaseX, Sedna and eXist-db. To the best of our knowledge, SVMAX is the first system for securing XML data in the presence of arbitrary DTDs (recursive or not), a significant fragment of XPath and a rich class of XML update operations

Les systèmes d'information mobiles et ambiants liés à la localisation et à la navigation évoluent progressivement vers des environnements à petite échelle. La nouvelle frontière scientifique et technologique concerne les applications qui assistent les utilisateurs dans leurs déplacements et activités au sein d’espaces bâtis dits «indoor» (e.g., aéroports, musées, bâtiments). La recherche présentée par cette thèse développe une représentation de données spatiales d'un environnement «indoor» qui tient compte des dimensions contextuelles centrées sur l'utilisateur et aborde les enjeux de gestion de données mobiles. Un modèle de données «indoor» hiérarchique et sensible au contexte est proposé. Ce modèle intègre différentes dimensions du contexte en plus de la localisation des entités concernées, telles que le temps et les profils des utilisateurs. Ce modèle est basé sur une structure arborescente dans laquelle l'information spatiale est représentée à différents niveaux d'abstraction. Cette conception hiérarchique favorise un traitement adaptatif et efficace des Requêtes Dépendantes de la Localisation (RDL) qui sont considérées comme des éléments clés pour le développement des différentes catégories de services de géolocalisation sensibles au contexte. Un langage de requêtes continues est développé et illustré par des exemples de requêtes RDL. Ce langage exploite le concept des granules spatiales, et permet de représenter les requêtes continues et dépendantes de la localisation en prenant compte des préférences de l'utilisateur au moment de l'exécution.Cette approche de modélisation est complétée par le développement d'une architecture générique pour le traitement continu des requêtes RDL et par la conception et la mise en oeuvre de plusieurs algorithmes qui permettent un traitement efficace des requêtes dépendantes de la localisation sur des objets mobiles en «indoor». Plusieurs algorithmes de traitement continu des requêtes de recherche de chemin hiérarchique et des requêtes de zone appliquées à des objets statiques et/ou en mouvement sont présentés. Ces algorithmes utilisent une approche hiérarchique et incrémentale afin d'exécuter efficacement les requêtes RDL continues. Un prototype encapsulant le modèle de données hiérarchique, les opérateurs et les contraintes introduits dans le langage de requête ainsi que les différents algorithmes et méthodes pour la manipulation de requêtes RDL a été développé comme une extension du SGBD Open Source PostgreSQL. Une étude expérimentale des solutions développées a été menée pour étudier la performance et le passage à l'échelle à l'égard des propriétés intrinsèques des solutions proposées. / The range of applications in ambient information systems progressively evolves from large to small scale environments. This is particularly the case for applications that assist humans in navigation-related activities in indoor spaces (e.g., airports, museums, office buildings). The research presented by this Ph.D. dissertation develops a data and knowledge representation of an indoor environment that takes into account user-centred contextual dimensions and mobile data management issues. We introduce a hierarchical, context-dependent, and feature-based indoor spatial data model. This model takes into account additional contextual dimensions such as time, user profiles, and real-time events. The model is based on a tree structure in which location information is represented at different levels of abstraction. The hierarchical design favours performance and scalability of location-dependent query processing. A query grammar is developed and implemented on top of that model. This query language supports continuous location-dependent queries and takes into account user preferences at execution time. The concept of location granules is introduced at the query execution and presentation levels.This modelling approach is complemented by the development of a generic architecture for continuous query processing. Several algorithms for location dependent query processing over indoor moving objects have been designed and implemented. These algorithms include path searches and range queries applied to both static and moving objects. They are based on an incremental approach in order to execute continuous location-dependent queries.The operators and constraints introduced in the query language and the algorithms for location-dependent query processing have been implemented as a database extension of the open source DBMS PostgreSQL, and where the hierarchical network-based indoor data model has been developed at the logical level. Several experiments have been conducted to evaluate the scalability and performance of the whole framework.

Cette thèse part du constat qu’il y a une infobésité croissante sur le Web. Les deux types d’outils principaux, à savoir le système de recherche et celui de recommandation, qui sont conçus pour nous aider à explorer les données du Web, connaissent plusieurs problématiques dans : (1) l’assistance de la manifestation des besoins d’informations explicites, (2) la sélection des documents pertinents, et (3) la mise en valeur des documents sélectionnés. Nous proposons des approches mobilisant les technologies du Web sémantique afin de pallier à ces problématiques et d’améliorer l’accès aux informations pertinentes. Nous avons notamment proposé : (1) une approche sémantique d’auto-complétion qui aide les utilisateurs à formuler des requêtes de recherche plus longues et plus riches, (2) des approches de recommandation utilisant des liens hiérarchiques et transversaux des graphes de connaissances pour améliorer la pertinence, (3) un framework d’affinité sémantique pour intégrer des données sémantiques et sociales pour parvenir à des recommandations qualitativement équilibrées en termes de pertinence, diversité et nouveauté, (4) des approches sémantiques visant à améliorer la pertinence, l’intelligibilité et la convivialité des explications des recommandations, (5) deux approches de profilage sémantique utilisateur à partir des images, et (6) une approche de sélection des meilleures images pour accompagner les documents recommandés dans les bannières de recommandation. Nous avons implémenté et appliqué nos approches dans le domaine du e-tourisme. Elles ont été dûment évaluées quantitativement avec des jeux de données vérité terrain et qualitativement à travers des études utilisateurs. / This thesis starts with the observation that there is an increasing infobesity on the Web. The two main types of tools, namely the search engine and the recommender system, which are designed to help us explore the Web data, have several problems: (1) in helping users express their explicit information needs, (2) in selecting relevant documents, and (3) in valuing the selected documents. We propose several approaches using Semantic Web technologies to remedy these problems and to improve the access to relevant information. We propose particularly: (1) a semantic auto-completion approach which helps users formulate longer and richer search queries, (2) several recommendation approaches using the hierarchical and transversal links in knowledge graphs to improve the relevance of the recommendations, (3) a semantic affinity framework to integrate semantic and social data to yield qualitatively balanced recommendations in terms of relevance, diversity and novelty, (4) several recommendation explanation approaches aiming at improving the relevance, the intelligibility and the user-friendliness, (5) two image user profiling approaches and (6) an approach which selects the best images to accompany the recommended documents in recommendation banners. We implemented and applied our approaches in the e-tourism domain. They have been properly evaluated quantitatively with ground-truth datasets and qualitatively through user studies.

Résumé en français non fourni par l'auteur. / There is a paradigm shift in the nature and processing means of today’s data: data are used to being mostly static and stored in large databases to be queried. Today, with the advent of new applications and means of collecting data, most applications on the Web and in enterprises produce data in a continuous manner under the form of streams. Thus, the users of these applications expect to process a large volume of data with fresh low latency results. This has resulted in the introduction of Data Stream Processing Systems (DSMSs) and a Complex Event Processing (CEP) paradigm – both with distinctive aims: DSMSs are mostly employed to process traditional query operators (mostly stateless), while CEP systems focus on temporal pattern matching (stateful operators) to detect changes in the data that can be thought of as events. In the past decade or so, a number of scalable and performance intensive DSMSs and CEP systems have been proposed. Most of them, however, are based on the relational data models – which begs the question for the support of heterogeneous data sources, i.e., variety of the data. Work in RDF stream processing (RSP) systems partly addresses the challenge of variety by promoting the RDF data model. Nonetheless, challenges like volume and velocity are overlooked by existing approaches. These challenges require customised optimisations which consider RDF as a first class citizen and scale the processof continuous graph pattern matching. To gain insights into these problems, this thesis focuses on developing scalable RDF graph stream processing, and semantically-enabled CEP systems (i.e., Semantic Complex Event Processing, SCEP). In addition to our optimised algorithmic and data structure methodologies, we also contribute to the design of a new query language for SCEP. Our contributions in these two fields are as follows: • RDF Graph Stream Processing. We first propose an RDF graph stream model, where each data item/event within streams is comprised of an RDF graph (a set of RDF triples). Second, we implement customised indexing techniques and data structures to continuously process RDF graph streams in an incremental manner. • Semantic Complex Event Processing. We extend the idea of RDF graph stream processing to enable SCEP over such RDF graph streams, i.e., temporalpattern matching. Our first contribution in this context is to provide a new querylanguage that encompasses the RDF graph stream model and employs a set of expressive temporal operators such as sequencing, kleene-+, negation, optional,conjunction, disjunction and event selection strategies. Based on this, we implement a scalable system that employs a non-deterministic finite automata model to evaluate these operators in an optimised manner. We leverage techniques from diverse fields, such as relational query optimisations, incremental query processing, sensor and social networks in order to solve real-world problems. We have applied our proposed techniques to a wide range of real-world and synthetic datasets to extract the knowledge from RDF structured data in motion. Our experimental evaluations confirm our theoretical insights, and demonstrate the viability of our proposed methods

Contrairement aux données traditionnelles, les données semi-structurées<br />sont irrégulières : des données peuvent manquer, des concepts<br />similaires peuvent être représentés par différents types de données,<br />et les structures même peuvent être mal connues. Cette absence <br />de schéma prédéfini, permettant de tenir compte de toutes les données<br />du monde extérieur, présente l'inconvénient de complexifier les<br />algorithmes d'intégration des données de différentes sources.<br /><br />Nous proposons une architecture de médiation basée entièrement sur XML.<br />L'objectif de cette architecture de médiation est de fédérer des sources de<br />données distribuées de différents types.<br />Elle s'appuie sur le langage XQuery, un langage fonctionnel<br />conçu pour formuler des requêtes sur des documents XML. Le médiateur analyse<br />les requêtes exprimées en XQuery et répartit l'exécution de la requête<br />sur les différentes sources avant de recomposer les résultats.<br /><br />L'évaluation des requêtes doit se faire en exploitant au maximum les<br />spécificités des données et permettre une optimisation efficace.<br />Nous décrivons l'algèbre XAlgebre à base d'opérateurs conçus<br />pour XML. Cette algèbre a pour but de construire des plans d'exécution pour<br />l'évaluation de requêtes XQuery et traiter des tuples d'arbres XML.<br /><br />Ces plans d'exécution doivent pouvoir être modélisés par un modèle<br />de coût et celui de coût minimum sera sélectionné pour l'exécution. <br />Dans cette thèse, nous définissons un modèle de coût pour les données<br />semi-structurées adapté à notre algèbre.<br /><br />Les sources de données (SGBD, serveurs Web, moteur de recherche)<br />peuvent être très hétérogènes, elles peuvent avoir des<br />capacités de traitement de données très différentes, mais aussi avoir<br />des modèles de coût plus ou moins définis. <br />Pour intégrer ces différentes informations dans<br />l'architecture de médiation, nous devons déterminer comment communiquer<br />ces informations entre le médiateur et les sources, et comment les intégrer.<br />Pour cela, nous utilisons des langages basés sur XML comme XML-Schema et MathML<br />pour exporter les informations de métadonnées, de formules de coûts<br />et de capacité de sources.<br />Ces informations exportées sont communiquées par l'intermédiaire d'une interface<br />applicative nommée XML/DBC.<br /><br />Enfin, des optimisations diverses spécifiques à l'architecture de médiation<br />doivent être considérées. Nous introduisons pour cela un cache sémantique<br />basé sur un prototype de SGBD stockant efficacement des données XML<br />en natif.

Dans cette thèse, nous abordons le problème de la construction de réponses à des requêtes formelles modélisant les questions qu'un utilisateur humain peut poser concernant le fonctionnement d'un composant actif. Nous présentons d'abord un langage de programmation qui permet d'accéder en cours d'exécution à la description des actions du composant. Nous proposons ensuite un modèle de requêtes qui permet de représenter une large classe de question sur le fonctionnement et de prendre en compte des notions de bon sens issues de l'interaction en langage naturel. Nous proposons des algorithmes de construction de réponses pour ces requêtes formelles de bon sens. Nous étudions aussi le traitement des requêtes portant sur l'exécution passée du composant. Nous proposons une approche dynamique fondée sur l'extraction de comportement à partir des flux d'interaction. Enfin, nous montrons que notre travail peut être utilisé dans le web sémantique pour définir des pages dynamiques capables d'interagir avec les utilisateurs ordinaires, puis nous présentons l'implémentation de notre modèle dans le cadre du projet InterViews.