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

Le thème de recherche de cette thèse concerne la conception et l’implantation d’un système de gestion de bases de données distribuées et scalables (ang. Scalable Distributed Database System, SD-DBS) que nous avons appelé SD-SQL Server. SD-SQL Server implémente une nouvelle architecture de SGBD relationnel. Une base de SD-SQL Server, dite base scalable, grandit par la partition dynamique, scalable et distribuée de ses tables, dites scalables aussi. La partition et son évolution sont invisibles de l’usager/application. A l’heure actuelle, SD-SQL Server est le seul SGBD à offrir cette possibilité à notre connaissance. Les autres SGBDs connus, n’offrent au mieux que le partitionnement statique, nécessitant des réorganisations périodiques globales. Leur maniement est en général complexe et peu apprecié des usagers. Nos tables scalables sont organisées en segments d’une structure de données distribuée et scalable (SDDS). Chaque segment est placé sur un nœud lié de SQL Server. A l’heure actuelle, SQL Server supporte 250 nœuds liés, permettant à une table scalable de croître autant. L'expansion dynamique résulte des éclatements de segments débordant leur capacité de stockage. Chaque éclatement est déclenché par une insertion, à l’origine du débordement. Tout éclatement crée un ou plusieurs nouveaux segments. Les segments sont cachés des usagers/applications derrière les vues supportant les mises à jour, dites images. Les images sont des vues partitionnées et distribuées de SQL Server dynamiquement ajustées. Les usagers/applications de tables scalables n’interfacent que les images ou les vues des images
Our thesis elaborates on the design of a scalable distributed database system (SD-DBS). A novel feature of an SD-DBS is the concept of a scalable distributed relational table, a scalable table in short. Such a table accommodates dynamic splits of its segments at SD-DBS storage nodes. A split occurs when an insert makes a segment to overflow, like in, e. G. , B-tree file. Current DBMSs provide the static partitioning only, requiring a cumbersome global reorganization from time to time. The transparency of the distribution of a scalable table is in this light an important step beyond the current technology. Our thesis explores the design issues of an SD-DBS, by constructing a prototype termed SD-SQL Server. As its name indicates, it uses the services of SQL-Server. SD-SQL Server repartitions a table when an insert overflows existing segments. With the comfort of a single node SQL Server user, the SD-SQL Server user has larger tables or a faster response time through the dynamic parallelism. We present the architecture of our system, its implementation and the performance analysis

Dans la région Méditerranéenne les crues « éclair » représentent un risque des plus destructeurs ayant coûté la vie à de nombreuses personnes et entraînant des dommages matériels importants ces dernières années (Nîmes en 1988, Vaison-la-Romaine en 1992, Aude en 1999, Gard en 2002). Le groupe HydroEco de l'IMFT (Institut de Mécanique des Fluides de Toulouse) a développé le code MARINE (Modélisation de l'Anticipation du Ruissellement et des Inondations pour des évéNements Extrêmes) qui est un modèle hydrologique distribué à base physique pour la prévision de ce type de crues. Une méthode d'assimilation variationnelle de données, la méthode de l'état adjoint, est implémentée dans le modèle MARINE. Cette méthode considère les paramètres d'entrée comme des variables de contrôle du modèle et les optimise en minimisant les écarts entre les observations et les simulations par l'intermédiaire d'une fonction coût. Le bassin d'étude est le bassin versant du Gardon d'Anduze sur lequel nous disposons d'une base de données d'évènements extrêmes. Une analyse de sensibilité préliminaire permet d'identifier les paramètres les plus sensibles du modèle afin de réduire l'équifinalité. Une première application de la méthode de l'état adjoint est alors utilisée pour la calibration du modèle. Elle permet de tester la validité des hypothèses physiques en évaluant les performances du modèle puis de suggérer des pistes d'amélioration. Un jeu de paramètres consistant, cohérent avec les résultats de simulations utilisant une méthode de Monte Carlo, est alors identifié. Les hydrogrammes de crues obtenus sont compris dans une plage d'incertitude réduite. La seconde application de cette méthode s'intéresse à la prévision des crues par l'emploi de deux stratégies différentes. La première consiste à utiliser les informations à l'exutoire pendant la phase de montée de crue pour prédire ce pic de crue. La seconde consiste à utiliser les observations d'une station intermédiaire à l'amont du bassin pour prédire le débit à l'exutoire. Ces deux stratégies permettent une anticipation du pic de crue de quelques heures, résultat essentiel d'un point de vue opérationnel.

Le thème de recherche de cette thèse concerne la conception et la mise au point d'une structure de données distribuée et scalable (SDDS) à haute disponibilité : LH*RS. Cette structure permet de mémoriser un grand fichier de données. Les données du fichier LH*RS sont réparties par le hachage linéaire distribué sur les nœuds de stockage connectés par un réseau. LH*RS tolère l'indisponibilité de k  1 nœuds de stockage de données. La tolérance résulte de l'ajout de données de parité, encodées selon un nouveau code que cette Thèse contribue à proposer, de type Reed Solomon (RS). Nos résultats contribuent à la conception du code proposé à travers l'étude théorique et expérimentale de diverses techniques de codage/ décodage candidates pour LH*RS. L'étude expérimentale concernait tout particulièrement la conception et l'implantation d'un gestionnaire prototype pour cette SDDS. Nous avons montré l'efficacité de notre gestionnaire au niveau de temps des opérations de recherche et de mise à jour de données, ainsi que l'efficacité de la récupération de données mémorisées sur un ou plusieurs nœuds de stockage devenus indisponibles.

La problématique du transport de la donnée médicale, de surcroît nominative, comporte de nombreuses contraintes, qu'elles soient d'ordre technique, légale ou encore relationnelle. Les nouvelles technologies, issues particulièrement des grilles informatiques, permettent d'offrir une nouvelle approche au partage de l'information. En effet, le développement des intergiciels de grilles, notamment ceux issus du projet européen EGEE, ont permis d'ouvrir de nouvelles perspectives pour l'accès distribué aux données. Les principales contraintes d'un système de partage de données médicales, outre les besoins en termes de sécurité, proviennent de la façon de recueillir et d'accéder à l'information. En effet, la collecte, le déplacement, la concentration et la gestion de la donnée, se fait habituellement sur le modèle client-serveur traditionnel et se heurte à de nombreuses problématiques de propriété, de contrôle, de mise à jour, de disponibilité ou encore de dimensionnement des systèmes. La méthodologie proposée dans cette thèse utilise une autre philosophie dans la façon d'accéder à l'information. En utilisant toute la couche de contrôle d'accès et de sécurité des grilles informatiques, couplée aux méthodes d'authentification robuste des utilisateurs, un accès décentralisé aux données médicales est proposé. Ainsi, le principal avantage est de permettre aux fournisseurs de données de garder le contrôle sur leurs informations et ainsi de s'affranchir de la gestion des données médicales, le système étant capable d'aller directement chercher la donnée à la source. L'utilisation de cette approche n'est cependant pas complètement transparente et tous les mécanismes d'identification des patients et de rapprochement d'identités (data linkage) doivent être complètement repensés et réécris afin d'être compatibles avec un système distribué de gestion de bases de données. Le projet RSCA (Réseau Sentinelle Cancer Auvergne - www.e-sentinelle.org) constitue le cadre d'application de ce travail. Il a pour objectif de mutualiser les sources de données auvergnates sur le dépistage organisé des cancers du sein et du côlon. Les objectifs sont multiples : permettre, tout en respectant les lois en vigueur, d'échanger des données cancer entre acteurs médicaux et, dans un second temps, offrir un support à l'analyse statistique et épidémiologique.

Le Web des données offre un environnement de partage et de diffusion des données, selon un cadre particulier qui permet une exploitation des données tant par l’humain que par la machine. Pour cela, le framework RDF propose de formater les données en phrases élémentaires de la forme (sujet, relation, objet) , appelées triplets. Les bases du Web des données, dites bases RDF, sont des ensembles de triplets. Dans une base RDF, l’ontologie – données structurelles – organise la description des données factuelles. Le nombre et la taille des bases du Web des données n’a pas cessé de croître depuis sa création en 2001. Cette croissance s’est même accélérée depuis l’apparition du mouvement du Linked Data en 2008 qui encourage le partage et l’interconnexion de bases publiquement accessibles sur Internet. Ces bases couvrent des domaines variés tels que les données encyclopédiques (e.g. Wikipédia), gouvernementales ou bibliographiques. L’utilisation et la mise à jour des données dans ces bases sont faits par des communautés d’utilisateurs liés par un domaine d’intérêt commun. Cette exploitation communautaire se fait avec le soutien d’outils insuffisamment matures pour diagnostiquer le contenu d’une base ou pour interroger ensemble les bases du Web des données. Notre thèse propose trois méthodes pour encadrer le développement, tant factuel qu’ontologique, et pour améliorer l’interrogation des bases du Web des données. Nous proposons d’abord une méthode pour évaluer la qualité des modifications des données factuelles lors d’une mise à jour par un contributeur. Nous proposons ensuite une méthode pour faciliter l’examen de la base par la mise en évidence de groupes de données factuelles en conflit avec l’ontologie. L’expert qui guide l’évolution de cette base peut ainsi modifier l’ontologie ou les données. Nous proposons enfin une méthode d’interrogation dans un environnement distribué qui interroge uniquement les bases susceptibles de fournir une réponse
The web of data is a mean to share and broadcast data user-readable data as well as machine-readable data. This is possible thanks to rdf which propose the formatting of data into short sentences (subject, relation, object) called triples. Bases from the web of data, called rdf bases, are sets of triples. In a rdf base, the ontology – structural data – organize the description of factual data. Since the web of datacreation in 2001, the number and sizes of rdf bases have been constantly rising. This increase has accelerated since the apparition of linked data, which promote the sharing and interlinking of publicly available bases by user communities. The exploitation – interrogation and edition – by theses communities is made without adequateSolution to evaluate the quality of new data, check the current state of the bases or query together a set of bases. This thesis proposes three methods to help the expansion at factual and ontological level and the querying of bases from the web ofData. We propose a method designed to help an expert to check factual data in conflict with the ontology. Finally we propose a method for distributed querying limiting the sending of queries to bases that may contain answers

La problématique du transport de la donnée médicale, de surcroît nominative, comporte de nombreuses contraintes, qu'elles soient d'ordre technique, légale ou encore relationnelle. Les nouvelles technologies, issues particulièrement des grilles informatiques, permettent d'offrir une nouvelle approche au partage de l'information. En effet, le développement des intergiciels de grilles, notamment ceux issus du projet européen EGEE, ont permis d'ouvrir de nouvelles perspectives pour l'accès distribué aux données. Les principales contraintes d'un système de partage de données médicales, outre les besoins en termes de sécurité, proviennent de la façon de recueillir et d'accéder à l'information. En effet, la collecte, le déplacement, la concentration et la gestion de la donnée, se fait habituellement sur le modèle client-serveur traditionnel et se heurte à de nombreuses problématiques de propriété, de contrôle, de mise à jour, de disponibilité ou encore de dimensionnement des systèmes. La méthodologie proposée dans cette thèse utilise une autre philosophie dans la façon d'accéder à l'information. En utilisant toute la couche de contrôle d'accès et de sécurité des grilles informatiques, couplée aux méthodes d'authentification robuste des utilisateurs, un accès décentralisé aux données médicales est proposé. Ainsi, le principal avantage est de permettre aux fournisseurs de données de garder le contrôle sur leurs informations et ainsi de s'affranchir de la gestion des données médicales, le système étant capable d'aller directement chercher la donnée à la source.L'utilisation de cette approche n'est cependant pas complètement transparente et tous les mécanismes d'identification des patients et de rapprochement d'identités (data linkage) doivent être complètement repensés et réécris afin d'être compatibles avec un système distribué de gestion de bases de données. Le projet RSCA (Réseau Sentinelle Cancer Auvergne - www.e-sentinelle.org) constitue le cadre d'application de ce travail. Il a pour objectif de mutualiser les sources de données auvergnates sur le dépistage organisé des cancers du sein et du côlon. Les objectifs sont multiples : permettre, tout en respectant les lois en vigueur, d'échanger des données cancer entre acteurs médicaux et, dans un second temps, offrir un support à l'analyse statistique et épidémiologique.

Notre but est de permettre à un utilisateur du Web d'organiser la gestion de ses données distribuées en place, c'est à dire sans l'obliger à centraliser ses données chez un unique hôte. Par conséquent, notre système diffère de Facebook et des autres systèmes centralisés, et propose une alternative permettant aux utilisateurs de lancer leurs propres pairs sur leurs machines gérant localement leurs données personnelles et collaborant éventuellement avec des services Web externes. Dans ma thèse, je présente Webdamlog, un langage dérivé de datalog pour la gestion de données et de connaissances distribuées. Le langage étend datalog de plusieurs manières, principalement avec une nouvelle propriété la délégation, autorisant les pairs à échanger non seulement des faits (les données) mais aussi des règles (la connaissance). J'ai ensuite mené une étude utilisateur pour démontrer l'utilisation du langage. Enfin je décris le moteur d'évaluation de Webdamlog qui étend un moteur d'évaluation de datalog distribué nommé Bud, en ajoutant le support de la délégation et d'autres innovations telles que la possibilité d'avoir des variables pour les noms de pairs et des relations. J'aborde de nouvelles techniques d'optimisation, notamment basées sur la provenance des faits et des règles. Je présente des expérimentations qui démontrent que le coût du support des nouvelles propriétés de Webdamlog reste raisonnable même pour de gros volumes de données. Finalement, je présente l'implémentation d'un pair Webdamlog qui fournit l'environnement pour le moteur. En particulier, certains adaptateurs permettant aux pairs Webdamlog d'échanger des données avec d'autres pairs sur Internet. Pour illustrer l'utilisation de ces pairs, j'ai implémenté une application de partage de photos dans un réseau social en Webdamlog.

L'objet de cette these est l'implantation d'un langage de programmation parallele de haut niveau sur des machines physiques paralleles a memoire partagee ou distribuee. Le langage support de l'etude, lcs, combine les aspects haut niveau du langage fonctionnel standard ml et le modele des processus communicants ccs. L'implantation repose sur une machine virtuelle parallele, composee d'un nombre limite de machines virtuelles sequentielles elementaires partageant l'ensemble des objets construits dans un tas. Les principales contributions sont: (1) la gestion du tas partage, qui fait appel a un ramasse miettes s'executant en parallele sur les machines elementaires, incrementalement avec le calcul sur chacune d'elles. Un mecanisme original de credit de tracage, et des algorithmes distribues d'allocation permettent une cooperation totale entre les machines. Sur des machines cibles a memoire distribuee, le tas est construit par la technique de memoire virtuelle partagee distribuee, integree efficacement avec le ramasse miettes grace a l'utilisation dans les deux cas des protections d'acces aux pages memoire. (2) la gestion de l'ensemble des processus, pour laquelle un algorithme de repartition de charge, base sur l'emploi de bornes dynamiques, a ete concu. Ses proprietes sont demontrees, et les resultats confirmes par simulation. L'implementation effectuee a permis d'apprecier les qualites du ramasse miettes paralleles developpe

Nous vivons dans un monde de big data, où les données sont générées en grand volume, grande vitesse et grande variété. Le big data apportent des valeurs et des avantages énormes, de sorte que l’analyse des données est devenue un facteur essentiel de succès commercial dans tous les secteurs. Cependant, si les données ne sont pas analysées assez rapidement, les bénéfices de big data seront limités ou même perdus. Malgré l’existence de nombreux systèmes modernes d’analyse de données à grande échelle, la préparation des données est le processus le plus long de l’analyse des données, n’a pas encore reçu suffisamment d’attention. Dans cette thèse, nous étudions le problème de la façon d’accélérer la préparation des données pour le big data d’analyse. En particulier, nous nous concentrons sur deux grandes étapes de préparation des données, le chargement des données et le nettoyage des données. Comme première contribution de cette thèse, nous concevons DiNoDB, un système SQL-on-Hadoop qui réalise l’exécution de requêtes à vitesse interactive sans nécessiter de chargement de données. Les applications modernes impliquent de lourds travaux de traitement par lots sur un grand volume de données et nécessitent en même temps des analyses interactives ad hoc efficaces sur les données temporaires générées dans les travaux de traitement par lots. Les solutions existantes ignorent largement la synergie entre ces deux aspects, nécessitant de charger l’ensemble des données temporaires pour obtenir des requêtes interactives. En revanche, DiNoDB évite la phase coûteuse de chargement et de transformation des données. L’innovation importante de DiNoDB est d’intégrer à la phase de traitement par lots la création de métadonnées que DiNoDB exploite pour accélérer les requêtes interactives. La deuxième contribution est un système de flux distribué de nettoyage de données, appelé Bleach. Les approches de nettoyage de données évolutives existantes s’appuient sur le traitement par lots pour améliorer la qualité des données, qui demandent beaucoup de temps. Nous ciblons le nettoyage des données de flux dans lequel les données sont nettoyées progressivement en temps réel. Bleach est le premier système de nettoyage qualitatif de données de flux, qui réalise à la fois la détection des violations en temps réel et la réparation des données sur un flux de données sale. Il s’appuie sur des structures de données efficaces, compactes et distribuées pour maintenir l’état nécessaire pour nettoyer les données et prend également en charge la dynamique des règles. Nous démontrons que les deux systèmes résultants, DiNoDB et Bleach, ont tous deux une excellente performance par rapport aux approches les plus avancées dans nos évaluations expérimentales, et peuvent aider les chercheurs à réduire considérablement leur temps consacré à la préparation des données
We are living in a big data world, where data is being generated in high volume, high velocity and high variety. Big data brings enormous values and benefits, so that data analytics has become a critically important driver of business success across all sectors. However, if the data is not analyzed fast enough, the benefits of big data will be limited or even lost. Despite the existence of many modern large-scale data analysis systems, data preparation which is the most time-consuming process in data analytics has not received sufficient attention yet. In this thesis, we study the problem of how to accelerate data preparation for big data analytics. In particular, we focus on two major data preparation steps, data loading and data cleaning. As the first contribution of this thesis, we design DiNoDB, a SQL-on-Hadoop system which achieves interactive-speed query execution without requiring data loading. Modern applications involve heavy batch processing jobs over large volume of data and at the same time require efficient ad-hoc interactive analytics on temporary data generated in batch processing jobs. Existing solutions largely ignore the synergy between these two aspects, requiring to load the entire temporary dataset to achieve interactive queries. In contrast, DiNoDB avoids the expensive data loading and transformation phase. The key innovation of DiNoDB is to piggyback on the batch processing phase the creation of metadata, that DiNoDB exploits to expedite the interactive queries. The second contribution is a distributed stream data cleaning system, called Bleach. Existing scalable data cleaning approaches rely on batch processing to improve data quality, which are very time-consuming in nature. We target at stream data cleaning in which data is cleaned incrementally in real-time. Bleach is the first qualitative stream data cleaning system, which achieves both real-time violation detection and data repair on a dirty data stream. It relies on efficient, compact and distributed data structures to maintain the necessary state to clean data, and also supports rule dynamics. We demonstrate that the two resulting systems, DiNoDB and Bleach, both of which achieve excellent performance compared to state-of-the-art approaches in our experimental evaluations, and can help data scientists significantly reduce their time spent on data preparation

Les utilisateurs des bases de données doivent faire face au problème de surcharge d'information lors de l'interrogation de leurs données, qui se traduit par un nombre de réponses trop élevé à des requêtes exploratoires. Pour remédier à ce problème, nous proposons un algorithme efficace et rapide, ap- pelé ESRA (Explore-Select-Rearrange Algorithm), qui utilise les résumés SAINTETIQ pré-calculés sur l'ensemble des données pour regrouper les réponses à une requête utilisateur en un ensemble de classes (ou résumés) organisées hiérarchiquement. Chaque classe décrit un sous-ensemble de résul- tats dont les propriétés sont voisines. L'utilisateur pourra ainsi explorer la hiérarchie pour localiser les données qui l'intéressent et en écarter les autres. Les résultats expérimentaux montrent que l'al- gorithme ESRA est efficace et fournit des classes bien formées (i.e., leur nombre reste faible et elles sont bien séparées). Cependant, le modèle SAINTETIQ, utilisé par l'algorithme ESRA, exige que les données soient disponibles sur le serveur des résumés. Cette hypothèse rend inapplicable l'algo- rithme ESRA dans des environnements distribués où il est souvent impossible ou peu souhaitable de rassembler toutes les données sur un même site. Pour remédier à ce problème, nous proposons une collection d'algorithmes qui combinent deux résumés générés localement et de manière autonome sur deux sites distincts pour en produire un seul résumant l'ensemble des données distribuées, sans accéder aux données d'origine. Les résultats expérimentaux montrent que ces algorithmes sont aussi performants que l'approche centralisée (i.e., SAINTETIQ appliqué aux données après regroupement sur un même site) et produisent des hiérarchies très semblables en structure et en qualité à celles produites par l'approche centralisée.

Les architectures distribuées des systèmes embarqués sont souvent décrites sous la forme de composants concurrents communiquant entre eux. De tels systèmes sont à la fois orientés flot de données pour leur description, et dirigés par le temps pour leur exécution. Cette thèse s'inscrit dans cette problématique et se concentre sur le contrôle de la compatibilité temporelle d'un ensemble de données interdépendantes utilisées par les composants du système. L'architecture d'un système modélisé par composants forme un graphe où plusieurs chemins peuvent relier deux composants, avec des caractéristiques temporelles hétérogènes, ce qui induit des temps de parcours disparates. Il est alors important que ces flots d'information soient assemblés de façon cohérente sur le composant destinataire, c'est-à-dire de telle manière que le composant utilise en entrée des données dépendant (directement ou indirectement) du même pas d'exécution du composant à l'origine de ces flots multiples. Dans un premier temps, ce principe d'association cohérente de données est identifié et formalisé. Une méthodologie est proposée afin de détecter, dans un graphe de composants, les configurations pouvant poser des problèmes d'association de données Dans un deuxième temps, différentes approches sont détaillées afin de gérer l'association cohérente des données dans des systèmes périodiques sans supposer de propriétés strictes sur l'ordonnancement des composants. Dans les systèmes où les composants partagent la même période et où les communications intra-périodiques sont interdites, l'association des données est gérée par un mécanisme de files permettant de rééquilibrer les temps de parcours des données sur les différents chemins. Dans le cas où les composants sont de périodes diverses, un mécanisme d'estampillage des données est utilisé afin de mémoriser les dépendances entre données. Associé à l'utilisation de files, cet estampillage permet aux composants de sélectionner, à chacune de leurs phases d'activation, des ensembles de données cohérents choisis parmi les données à leur disposition. La notion d'association cohérente est ensuite relâchée, permettant une utilisation de données approximativement cohérentes. Des files filtrantes, n'enregistrant qu'une donnée sur un certain nombre de données reçues, permettent de réduire la taille des files nécessaires. Par ailleurs, du fait de la liberté du modèle d'exécution choisi, il existe des situations où il est impossible de garantir la vivacité de l'association cohérente des données. D'autre part, une architecture particulière peut générer des contraintes de cohérence conflictuelles et aboutir à une impossibilité de gestion de la cohérence. Pour terminer, les résultats de ces travaux sont appliqués sur le logiciel applicatif d'un satellite d'observation terrestre détectant des points chauds.

Ma thèse porte sur la compilation des langages de requêtes orientés web des données. Plus particulièrement, ma thèse s'intéresse à l'analyse, l'optimisation et l'évaluation distribuée d'un tel langage : SPARQL. Ma contribution principale est l'élaboration d'une méthode nouvelle particulièrement intéressante pour des requêtes contenant de la récursion ou dans le cadre d'une évaluation distribuée. Cette nouvelle méthode s'appuie sur un nouvel outil que nous introduisons : la μ-algèbre. C'est une variation de l'algèbre relationnelle équipée d'un opérateur de point fixe. Nous présentons sa syntaxe et sémantique ainsi qu'une traduction vers la μ-algèbre depuis SPARQL avec Property Paths (une fonctionnalité introduite dans le dernier standard SPARQL qui autorise une forme de récursion).Nous présentons ensuite un système de types et nous montrons comment les termes de la μ-algèbre peuvent être réécrits en d'autres termes (de sémantique équivalente) en utilisant soit des règles de réécriture provenant de l'algèbre relationnelle soit des règles nouvelles, spécifiques à la μ-algèbre. Nous démontrons la correction des nouvelles règles qui sont introduites pour réécrire les points fixes : elles permettent de pousser les filtres, les jointures ou les projections à l'intérieur des points fixes (dépendant des certaines conditions sur le terme).Nous présentons ensuite comment ces termes peuvent être évalués, d'abord de manière générale, puis en considérant le cas particulier d'une évaluation sur une plateforme distribuée. Nous présentons aussi un modèle de coût pour l'évaluation des termes. À l'aide du modèle de coût et de l'évaluateur, plusieurs termes qui sont équivalents d'un point de vue sémantiques peuvent maintenant être vus comme différentes manières d'évaluer les termes avec différents coûts estimés. Nous montrons alors que les termes qui sont considérés grâce aux nouvelles règles de réécritures que nous avons introduites, permettent une exécution plus efficace que ce qui était possible dans les autres approches existantes. Nous confirmons ce résultat théorique par une expérimentation comparant plusieurs exécuteurs sur des requêtes SPARQL contenant de la récursion.Nous avons investigué comment utiliser une plateforme de calcul distribuée (Apache Spark) pour produire un évaluateur efficace de requêtes SPARQL. Cet évaluateur s'appuie sur un fragment de la μ-algèbre, limité aux opérateurs qui ont une traduction en code Spark efficace. Le résultat de ces investigations à résultat en l'implémentation de SPARQLGX, un évaluateur SPARQL distribué en pointe par rapport à l'état de l'art.Pour finir, ma dernière contribution concerne l'estimation de la cardinalité des solutions à un terme de la μ-algèbre. Ces estimateurs sont particulièrement utiles pour l'optimisation. En effet, les modèles de coût reposent généralement sur de telles estimations pour choisir quel sera le terme le plus efficace parmi plusieurs termes équivalents. Pour cette estimation nous nous intéressons tout particulièrement au fragment conjonctif de la μ-algèbre (ce qui correspond au fragment bien connu Basic Graph Pattern de SPARQL). Notre nouvelle estimation de cardinalité s'appuie sur des statistiques sur les données et a été implémenté dans SPARQLGX. Nos expériences montrent que cette méthode permet de grandement accélérer l'évaluation de SPARQL sur SPARQLGX
The topic of my PhD is the compilation of web data query languages. More particularly, the analysisand the distributed evaluation of a such language: SPARQL. My main contributions concern theevaluation of web data queries especially for recursive queries or for distributed settings.In this thesis, I introduce μ-algebra: it is a kind of relational algebra equipped with a fixpointoperator. I present its syntax, semantics, and a translation from SPARQL with Property Paths (anew feature of SPARQL allowing some form of recursion) to this μ-algebra.I then present a type system and show how μ-algebra terms can be rewritten to terms withequivalent semantics using either classical rewrite rules of the relational world or new rules that arespecific to this μ-algebra. We demonstrate the correctness of these new rules that are introduced tohandle the rewriting of fixpoints: they allow to push filters, joins and projections inside fixpointsor to combine several fixpoints (when some condition holds).I demonstrate how these terms could be evaluated both from a general perspective and in thespecific case of a distributed evaluation. I devise a cost model for μ-algebra terms inspired by thisevaluation. With this cost model and this evaluator, several terms that are semantically equivalentcan be seen as various Query Execution Plans (QEP) for a given query. I show that the μ-algebraand its rewrite rules allow the reach of QEP that are more efficient than all QEP considered in otherexisting approaches and confirm this by an experimental comparison of several query evaluators onSPARQL queries with recursion.I investigate the use of an efficient distributed framework (Spark) to build a fast SPARQL dis-tributed query evaluator. It is based on a fragment of μ-algebra, limited to operators that havea translation into fast Spark code. The result of this has been used to implement SPARQLGX, astate of the art distributed SPARQL query evaluator.Finally, my last contribution concerns the estimation of the cardinality of solutions to a μ-algebraterm. Such estimators are key in the optimization. Indeed, most cost models for QEP rely on suchestimators and are therefore necessary to determine the most efficient QEP. I specifically considerthe conjunctive query fragment of μ-algebra (which corresponds to the well-known Basic GraphPattern fragment of SPARQL). I propose a new cardinality estimation based on statistics about thedata and implemented the method into SPARQLGX. Experiments show that this method improvesthe performance of SPARQLGX

Le travail présenté propose une solution au traitement de l'information complexe et distribuée dans le contexte d'applications médicales. La solution repose à la fois sur un modèle de données qui facilite la représentation des données temporelles ou répétitives et des relations entre les données (le modèle LIED, langage interactif pour l'exploitation des données) et sur une architecture de communication (le HUB, HELIOS Unification Bus). Apres une rapide introduction sur le contexte médical d'expérimentation et sur une brève présentation du modèle, on y aborde en détails les aspects de modélisation. On y fait référence aux travaux de normalisation ou de recherche du domaine médical (travaux du CEN TC 251 ou de l'ODMG, projets HELIOS, GEHR, GALEN, …). On y décrit ensuite le modèle choisi pour la représentation des concepts médicaux et des items ainsi que la façon dont ces items sont agrégés pour former le modèle d'information. Les aspects temporels sont aussi abordés, à la fois d'un point de vue bibliographique portant sur les bases de données temporelles et d'un point de vue de la solution proposée dans le modèle LIED. L'auteur s'intéresse ensuite aux aspects de distribution et aux solutions en terme de logiciels pour assurer l'intégration des systèmes hétérogènes distribués. Les différentes solutions, connues sous le nom générique de middleware, sont présentées. Une proposition de classification des middlewares est aussi faite, ainsi qu'une présentation des tendances en matière d'évolution de ces logiciels. L'auteur s'intéresse ensuite à la solution middleware qu'il a mise en œuvre dans le cadre du projet HELIOS, le HUB, et à la façon dont LIED a bénéficié des apports du HUB. Les aspects d'interface homme-machine sont ensuite étudiés, avant d'aborder les résultats de l'implémentation et de la mise en production dans les différents services de l'hôpital Broussais. Le travail se termine sur une étude critique de positionnement par rapport aux « SGBD Orienté Objet » ainsi que sur les perspectives qu'il offre dans le cadre des projets de recherche européens Synapses et SynEx, références en terme de plateformes d'intégration du domaine médical. Ce travail résume l'investissement personnel de l'auteur depuis de nombreuses années (entre 12 et 15) ainsi que l'état de l'art du génie logiciel, dans le contexte des réalisations d'informatique médicale.

Le principal défi du contrôle et de la gestion des réseaux électriques intelligents (Smartgrids) est la quantité de données à traiter. Les techniques classiques centralisées, même si elles offrent l’avantage de facilité de gestion par leur vision globale du réseau, ne supportent pas en pratique la croissance continue des volumes de données (bande passante limitée, goulot d’étranglement, quantité de calculs à assurer, etc.). Le passage à un contrôle et une gestion décentralisée (répartie), où le système est composé d’une multitude d’unités de calcul coopérantes, offre de très bonnes perspectives (robustesse, calcul au plus près des producteurs et consommateurs de données, exploitation de toutes les ressources disponibles), mais reste difficile à mettre en place. En effet, la programmation d’algorithmes distribués nécessite de prendre en compte les échanges de données et la synchronisation des unités participantes, cette complexité augmentant avec le nombre d’unités. Dans cette thèse, nous proposons une approche innovante de programmation de haut niveau d’abstraction masquant ces difficultés.Tout d’abord, nous proposons d’abstraire l’ensemble des unités de calcul du Smartgrid (compteur intelligent, capteurs, concentrateurs de données, etc.) sous forme d’une base de données distribuées. Chaque unité de calcul hébergeant une base de données locale et seules les données nécessaires à la poursuite du calcul sont échangées avec d’autres unités, ce qui diminue l’utilisation de la bande passante disponible. L’utilisation d’un langage de manipulation de données déclaratif simplifiera la programmation des applications de contrôle et de gestion. Nous proposons également SmartLog, un langage à base de règles (basé sur le langage Datalog et ses dérivés) dédié à ces applications. Il facilite la programmation distribuée des applications Smartgrid en réagissant immédiatement à tout changement dans les données.Même avec un langage tel que SmartLog, il est nécessaire de prendre en compte les échanges de données et la synchronisation des participants. C’est pourquoi nous proposons ensuite une approche simplifiant la programmation distribuée. Cette approche, nommée CPDE pour Centralized Programmation and Distributed Execution, consiste en deux étapes : (i) programmer l’application centralisée en SmartLog, car cela est plus facile, et (ii) traduire le programme centralisé en programme distribué en se basant sur la localisation réelle des données. Pour ce faire, nous proposons un algorithme de distribution semi-automatique des règles SmartLog.Afin de démontrer l’intérêt de CPDE, nous avons mené une expérimentation exhaustive en utilisant des applications et des algorithmes réellement utilisés dans les Smartgrids, telles que le contrôle secondaire dans les micro-réseaux isolés ou la régulation de tension équitable. L’expérimentation a été réalisée sur une plate-forme de simulation de réseau électrique temps réel, avec une machine de simulation OPAL-RT, et des un réseau Raspberry-Pi représentant les unités de calcul (leurs performances sont tout à fait comparables aux équipements réels). Cette expérimentation a permis de valider les comportements et les performances des programmes distribués conçus avec CPDE comparativement à leurs versions centralisées en SmartLog et à leurs versions de référence implantés en Java. Nous avons également étudié l’impact de différents paramètres, tels que le nombre d’unités de calcul ou les différentes alternatives de répartition des données
The main challenge of smart grids control and management is the amount of data to be processed. Traditional, centralized techniques, even if they offer the advantage of the ease of management by their global grid vision, do not support in practice the continuous growth of data volumes (limited bandwidth, bottleneck, amount of calculations, etc.). The transition to decentralized(distributed)control and management, where the system is made up of a multitude of co-operating computing units, offers very good prospects (robustness, calculation close to the producers and consumers of data, exploitation of data in all available resources), but remains challenging to implement. In fact, the programming of distributed algorithms requires taking into account the data exchanges and the synchronization of the participating units; this complexity increases with the number of units. In this thesis, we propose an innovative approach of programming of a high level of abstraction masking these difficulties.First, we propose to abstract all Smartgrid computing units (smart meters, sensors, data concentrators, etc.) as a distributed database. Each computing unit hosts a local database and only the data needed to continue the calculation are exchanged with other units, which decreases the use of the available bandwidth. The use of a declarative data handling language will simplify the programming of control and management applications. Besides, we also propose SmartLog, a rule-based language (based on the Datalog language and its derivatives dedicated to these applications. It facilitates distributed programming of Smartgrid applications by immediately responding to any changes in the data.Even with a language such as SmartLog, it is necessary to take into account the data exchange and the synchronization of the participants. This is why we then propose an approach that simplifies distributed programming. This approach, named CPDE for Centralized Programming and Distributed Execution, consists of two steps: (i) programming the centralized application in SmartLog, as this is easier, and (ii) translating the centralized program into a distributed program based on the actual location of the data. To do this, we propose a semi-automatic Smartlog rule distribution algorithm.In order to demonstrate the interest of CPDE, we conducted a comprehensive experiment using applications and algorithms actually used in Smartgrids, such as secondary control in isolated micro-grids or fair voltage regulation. The experiment was carried out on a real-time electrical network simulation platform, with an OPAL-RT simulation machine, and a Raspberry-Pi network representing the computing units (their performances are quite comparable to the real equipment). This experiment allowed validating the behaviours and the performances of the distributed programs conceived with CPDE, and comparing to their centralized versions in SmartLog and their reference versions implanted in Java. The impact of different parameters, such as the number of calculation units or different data distribution alternatives, is studied as well

De nos jours, l'information géographique constitue une ressource incontournable dans un contexte de prise de décision et les données numériques spatiales sont de plus en plus fréquemment exploitées comme support et aide à la décision par de nombreuses organisations.
L'institution militaire utilise elle aussi les données spatiales comme soutien et aide à la décision. A chaque étape d'une mission, des informations géographiques de tous types sont employées (données numériques, cartes papiers, photographies aériennes...) pour aider les unités dans leurs choix stratégiques. Par ailleurs, l'utilisation de réseaux de communication favorise le partage et l'échange des données spatiales entre producteurs et utilisateurs situés à des endroits différents. L'information n'est pas centralisée, les données sont répliquées sur chaque site et les utilisateurs peuvent ponctuellement être déconnectés du réseau, par exemple lorsqu'une unité mobile va faire des mesures sur le terrain.
La problématique principale concerne donc la gestion dans un contexte militaire, d'une application collaborative permettant la mise à jour asynchrone et symétrique de données géographiques répliquées selon un protocole à cohérence faible optimiste. Cela nécessite de définir un modèle de cohérence approprié au contexte militaire, un mécanisme de détection des mises à jour conflictuelles lié au type de données manipulées et des procédures de réconciliation des écritures divergentes adaptées aux besoins des unités participant à la mission.
L'analyse des travaux montre que plusieurs protocoles ont été définis dans les communautés systèmes (Cederqvist :2001 ; Kermarrec :2001) et bases de données (Oracle :2003 ; Seshadri :2000) pour gérer la réplication des données. Cependant, les solutions apportées sont souvent fonctions du besoin spécifique de l'application et ne sont donc pas réutilisables dans un contexte différent, ou supposent l'existence d'un serveur de référence centralisant les données. Les mécanismes employés en information géographique pour gérer les données et les mises à jour ne sont pas non plus appropriés à notre étude car ils supposent que les données soient verrouillées aux autres utilisateurs jusqu'à ce que les mises à jour aient été intégrée (approche check in-check out (ESRI :2004), ou utilisent un serveur centralisé contenant les données de référence (versionnement : Cellary :1990).
Notre objectif est donc de proposer des solutions permettant l'intégration cohérente et autant que possible automatique, des mises à jour de données spatiales dans un environnement de réplication optimiste, multimaître et asynchrone.
Nous proposons une stratégie globale d'intégration des mises à jour spatiales basée sur une vérification de la cohérence couplé à des sessions de mises à jour. L'originalité de cette stratégie réside dans le fait qu'elle s'appuie sur des métadonnées pour fournir des solutions de réconciliation adaptées au contexte particulier d'une mission militaire.
La contribution de cette thèse est double. Premièrement, elle s'inscrit dans le domaine de la gestion de la mise à jour des données spatiales, domaine toujours très actif du fait de la complexité et de l'hétérogénéité des données (Nous limitons néanmoins notre étude aux données géographiques vectorielles) et de la relative «jeunesse » des travaux sur le sujet. Deuxièmement, elle s'inscrit dans le domaine de la gestion de la cohérence des données répliquées selon un protocole optimiste, en spécifiant en particulier, de nouveaux algorithmes pour la détection et la réconciliation de données conflictuelles, dans le domaine applicatif de l'information géographique.

Dans les SGBD actifs la notion de réaction automatique à des événements est offerte au travers de règles actives de la forme Événement-Condition-Action. Ces règles sont gérées par des mécanismes spécifiques, dits actifs, intégrés dans les SGBD. Nous nous intéressons à l'introduction de ces mécanismes dans les fédérations de données. Les fédérations sont caractérisées par la distribution et l'autonomie de leurs composants et les mécanismes actifs doivent donc s'adapter à de telles caractéristiques. Notre approche propose de mettre en œuvre ces mécanismes sous forme d'un service de règles et un service d'événements qui coopèrent. Dans cette thèse nous nous intéressons plus précisément à la définition et à la structuration d'un service de règles. Nous proposons un service adaptable nommé ADRUS (pour ADaptable RUle Service) qui permet la construction et le contrôle de gestionnaires de règles spécialisés selon les besoins des applications de la fédération bases de données. Les modèles implantés par ces gestionnaires sont spécifiés à partir des trois métamodèles offerts par le service : le métamodèle de définition et de manipulation de règles, le métamodèle d'exécution de règles et le métamodèle de coopération entre gestionnaires. Notre travail se concentre sur la définition de la structure et des caractéristiques des métamodèles. Nous modélisons la coopération entre gestionnaires de règles, d'événements et de transactions car celle-ci est fondamentale pour l'exécution des règles dans une fédération. Nous présentons une expérience d'utilisation de notre service dans le cadre de la mise en œuvre de systèmes ODAS. Ces systèmes sont basés sur des services d'événements et de règles ouverts et répartis (Open and Distributed Active Services) utilisés au niveau d'une fédération de bases de données dans le contexte d'une application de type commerce électronique

La sélection de sources de données est un des processus des plus critiques pour les systèmes de médiation dans des contextes grande échelle. C'est le cas notamment des grandes organisations virtuelles où le grand nombre de sources de données, la distribution, l'hétérogénéité, la fragmentation et la duplication des données rendent difficile l'identification des sources pertinentes à l'évaluation d'une requête. Cette thèse aborde cette problématique et propose OptiSource, une stratégie de sélection de sources de données créée pour des tels contextes. OptiSource est particulièrement performante dans des configurations où un grand nombre de sources sont susceptibles de contribuer à une requête selon leur niveau intentionnel (schéma), mais seulement un petit nombre d'entre elles peuvent effectivement le faire au niveau extensionnel (le contenu). OptiSource propose un processus itératif basé sur la sélection des sources de données dominantes pour chaque condition de la requête. Les sources dominantes sont désignées selon leur contribution attendue. Cette estimation utilise un modèle qui priorise les sources en fonction du rôle qu'elles peuvent jouer dans la requête, et optimise la répartition des sous-requêtes en utilisant un modèle d'optimisation combinatoire. OptiSource fait partie d'un système de médiation créé pour organisations virtuelles qui peut choisir dynamiquement la stratégie de sélection de sources la plus approprié au contexte. Notre domaine d'application privilégié a été le médical. Nous avons validé nos propositions sur divers types de contextes de grande taille.

Actuellement, dans les domaines du Big Data et de l’IoT, les recherches menées sont restées longtemps concentrées sur des problématiques en amont liées aux protocoles de communication pour la collecte des données, ou en aval pour l’exploitation des données collectés. Peu d’attention a été tourné vers des problématiques pourtant importantes qui se situent justement entre celles en amont et celles en aval telles que le déploiement, la mise en œuvre d’architectures logicielles modulables (au niveau Edge, Fog ou Cloud Computing), le contrôle fin du comportement des IoTs pour une meilleure utilisation du réseau et de l’énergie limitée des dispositifs. Dans le cadre de ce travail, la démarche prend en compte deux problématiques auxquelles nous devons faire face lors de l’implémentation d’une technologie Big Data / IoT. Premièrement, quelle architecture générique pourrions-nous adopter pour mettre en œuvre une plateforme reconfigurable selon les futures fonctionnalités visées pour un client donné ? En d’autres termes, comment mettre en œuvre une plateforme multi micro-services que l’on peut déverrouiller ou créer à la demande pour personnaliser une offre ? Deuxièmement, vers quelles méthodes de modélisation formelles s’orienter pour lever les obstacles rencontrés lors du déploiement de projets opérationnels liés aux IoTs et pour optimiser les performances, notamment énergétiques, étant donné que l’on peut les considérer comme des systèmes dynamiques à événements discrets ? Pour répondre à la première problématique, une plateforme logicielle modulable et configurable d’analyse de données Big Data a été développée constituée de fonctions nécessaires : (a) à l’acquisition des données IoT mais également d’informations provenant d’autres sources et protocoles, (b) au contrôle et traitement nécessaire à leur exploitation, et (c) au stockage des données massives. Un service Data Science, intégrant une approche IA, attaché à la plateforme nécessaire, (d) à l’extraction de connaissance et (e) à la prévision pour le diagnostic et l’aide à la décision a été développée. De plus, la plateforme se doit être modulable (i.e., possibilité d’ajouter ou de retirer des micro-services à la demande) et configurable (i.e., possibilité de personnaliser le paramétrage de la plateforme selon les besoins et les règles métier de chaque client). Pour répondre à la deuxième problématique, nous avons développé des approches algébriques basées sur l’algèbre Max Plus, pour répondre à des problèmes réels rencontrés dans des projets opérationnels liés aux objets connectés. Ceci a permis la mise en œuvre de solutions permettant en particulier de rendre plus efficients le déploiement et la gestion de l’énergie des IoTs. Ce travail a été effectué en s’appuyant sur une approche de modélisation analytique, pour l’établissement de critères de contrôle et d’évaluation des performances des solutions
Currently, in the fields of Big Data and IoT, the research carried out has for a long time remained focused on upstream issues related to communication protocols for data collection, or downstream issues related to the exploitation of collected data. Few attention has been paid to important issues that lie precisely between those upstream and those downstream problems, such as deployment, modular software architectures implementation (at Edge, Fog or Cloud Computing level), fine control of IoTs behaviors for a better use of the network bandwidth and the limited energy of devices. In the context of this work, the following questions that one has to deal with to implement Big Data / IoT technology solutions are considered. Firstly, what generic architecture could we adopt to implement a reconfigurable platform according to expected functionalities for a client? In other words, how can we implement a multi-micro-services platform that could be unlocked or created on demand to customize an offer? Secondly, which formal modelling method should be used to overcome encountered obstacles when deploying IoT operational projects to optimize performance, considering that an IoT based systems can be viewed as discrete-event dynamic systems? To address the first issue, a modular and configurable Big Data analysis platform has been developed with essential functions: (a) data acquisition from IoT devices but also information gathered from other sources and protocols, (b) control and processing components for their exploitation, and (c) massive data storage. A Data Science service has been developed, integrating AI approaches, (d) for knowledge discovery and (e) forecasting for diagnosis and decision support. In addition, the platform must be modular (i.e. the possibility of adding or removing micro-services on demand) and configurable (i.e. the possibility to customize the platform's parameters according to the needs and business rules of each user). To address the second issue, an approach based on Max Plus algebra is developed, to tackle real problems encountered in IoT operational projects. This has enabled the implementation of solutions that make the deployment and energy management of IoTs more efficient. This work has been carried out using an analytical modelling approach to establish criteria for monitoring and assessing the performance of the solutions

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations n-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques.

Dans ce travail, nous nous focalisons sur l’ajout de contraintes temporelles dans les Bases de Données de Capteurs Sans Fil (BDCSF). La cohérence temporelle d’une BDCSF doit être assurée en respectant les contraintes temporelles des transactions et la validité temporelle des données, pour que les données prélevées par les capteurs reflètent fidèlement l’état réel de l’environnement. Cependant, les retards de transmission et/ou de réception pendant la collecte des données peuvent conduire au non-respect de la validité temporelle des données. Une solution de type bases de données s'avère la plus adéquate. Il faudrait pour cela faire coïncider les aspects BD traditionnelles avec les capteurs et leur environnement. À cette fin, les capteurs déployés au sein d'un réseau sans fils sont considérés comme une table d'une base de données distribuée, à laquelle sont appliquées des transactions (interrogations, mises à jour, etc.). Les transactions sur une BD de capteurs nécessitent des modifications pour prendre en compte l'aspect continu des données et l'aspect temps réel. Les travaux réalisés dans cette thèse portent principalement sur trois contributions : (i) une étude comparative des propriétés temporelles entre une collecte périodique des données avec une base de données classique et une approche de traitement des requêtes avec une BDCSF, (ii) la proposition d’un modèle de traitement des requêtes temps réel, (iii) la mise en œuvre d’une BDCSF temps réel, basée sur les techniques décrites dans la deuxième contribution
In this thesis, we are interested in adding real-time constraints in the Wireless Sensor Networks Database (WSNDB). Temporal consistency in WSNDB must be ensured by respecting the transaction deadlines and data temporal validity, so that sensor data reflect the current state of the environment. However, delays of transmission and/or reception in a data collection process can lead to not respect the data temporal validity. A database solution is most appropriate, which should coincide with the traditional database aspects with sensors and their environment. For this purpose, the sensor in WSN is considered as a table in a distributed database, which applied transactions (queries, updates, etc.). Transactions in a WSNDB require modifications to take into account of the continuous datastream and real-time aspects. Our contribution in this thesis focus on three parts: (i) a comparative study of temporal properties between a periodic data collection based on a remote database and query processing approach with WSNDB, (ii) the proposition of a real-time query processing model, (iii) the implementation of a real time WSNDB, based on the techniques described in the second contribution

Our goal is to enable aWeb user to easily specify distributed data managementtasks in place, i.e. without centralizing the data to a single provider. Oursystem is therefore not a replacement for Facebook, or any centralized system,but an alternative that allows users to launch their own peers on their machinesprocessing their own local personal data, and possibly collaborating with Webservices.We introduce Webdamlog, a datalog-style language for managing distributeddata and knowledge. The language extends datalog in a numberof ways, notably with a novel feature, namely delegation, allowing peersto exchange not only facts but also rules. We present a user study thatdemonstrates the usability of the language. We describe a Webdamlog enginethat extends a distributed datalog engine, namely Bud, with the supportof delegation and of a number of other novelties of Webdamlog such as thepossibility to have variables denoting peers or relations. We mention noveloptimization techniques, notably one based on the provenance of facts andrules. We exhibit experiments that demonstrate that the rich features ofWebdamlog can be supported at reasonable cost and that the engine scales tolarge volumes of data. Finally, we discuss the implementation of a Webdamlogpeer system that provides an environment for the engine. In particular, a peersupports wrappers to exchange Webdamlog data with non-Webdamlog peers.We illustrate these peers by presenting a picture management applicationthat we used for demonstration purposes.

Les environnements virtuels distribués (EVDs) sont destinés à fournir à leurs utilisateurs une expérience immersive au sein d'un environnement virtuel partagé. Pour cette raison, les EVDs essaient d'apporter aux différents participants des vues cohérentes du monde partagé. Ceci nécessite un échange intense de messages en particulier pour les EVDs fortement peuplés. Cet important échange de messages consomme beaucoup de ressources de calcul et réseau, ce qui ralentit le système et limite l'interactivité. Ainsi, la cohérence, l'interactivité et le passage à l'échelle sont trois besoins primordiales pour les EVDs. Par contre, ces besoins sont contradictoires : le besoin de cohérence requiert un échange plus important de messages alors que ceux d'interactivité et de passage à l'échelle demandent de diminuer au minimum ces échanges. Pour gérer l'échange de messages d'une manière intelligente, les systèmes d'EVDs utilisent des méthodes de filtrage différentes. Parmi ces méthodes, les méthodes de gestion d'intérêt filtrent les messages en se basant sur les intérêts des utilisateurs dans le monde. Dans ce document, nous présentons notre méthode de gestion d'intérêt, la gestion d'effet. Cette méthode exprime les intérêts et les manifestations des participants dans les différents média à travers les zones de conscience et d'effet. Lorsque la zone de conscience d'un participant chevauche la zone d'effet d'un autre dans un média, le premier devient conscient du second dans ce média. De plus, pour un passage à l'échelle continu, la gestion d'effet a été développée au sein d'une architecture client/multi-serveurs qui gère les intérêts des participants à travers les serveurs. .
Distributed virtual environments (DVEs) are intended to provide an immersive experience to their users within a shared virtual environment. For this purpose, DVEs try to supply participants with coherent views of the shared world. This requires a heavy message exchange between participants especially with the increasing popularity of massively multiplayer DVEs. This heavy message exchange consumes a lot of processing power and bandwidth, slowing down the system and limiting interactivity. Indeed, coherence, interactivity and scalability are basic requirements of DVEs. However, these requirements are conflicting because coherence requires the more important exchange of messages that we can have while interactivity and scalability demand to decrease this exchange to minimum. For this reason, the management of message exchange is essential for distributed virtual environments. To manage message exchange in an intelligent way, DVE systems use various filtering techniques. Among them, interest management techniques filter messages according to users' interests in the world. In this document, we present our interest management technique, the effect management. This technique expresses the interests and manifestations of participants in various media through conscience and effect zones. When the conscience zone of a participant collides the effect zone of another participant in a given medium, the first one becomes conscious of the second. ). .

Les réseaux de capteurs sans fil (RCSFs) déterminent un axe de recherche en plein essor, puisqu’ils sont utilisés aujourd’hui dans de nombreuses applications qui diffèrent par leurs objectifs et leurs contraintes individuelles.Toutefois, le dénominateur commun de toutes les applications de réseaux de capteurs reste la vulnérabilité des nœuds capteurs en raison de leurs caractéristiques et aussi de la nature des données générées.En effet, les RCSFs génèrent une grande masse de données en continue à des vitesses élevées, hétérogènes et provenant d’emplacements répartis. Par ailleurs, la nécessité de traiter et d’extraire des connaissances à partir de ces grandes quantités de données nous ont motivé à explorer l’une des techniques conçues pour traiter efficacement ces ensembles de données et fournir leurs modèles de représentation. Cependant, parmi les techniques utilisées pour la gestion des données, nous pouvons utiliser les techniques de Data mining. Néanmoins, ces méthodes ne sont pas directement applicables aux RCSFs à cause des contraintes des noeuds capteurs. Il faut donc répondre à un double objectif : l’efficacité d’une solution tout en offrant une bonne adaptation des méthodes de Data mining classiques pour l’analyse de grosses masses de données des RCSFs en prenant en compte les contraintes des noeuds capteurs, et aussi l’extraction du maximum de connaissances afin de prendre des décisions meilleures. Les contributions de cette thèse portent principalement sur l’étude de plusieurs algorithmes distribués qui répondent à la nature des données et aux contraintes de ressources des noeuds capteurs en se basant sur les techniques de Data mining. Chaque noeud favorise un traitement local des techniques de Data mining et ensuite échange ses informations avec ses voisins, pour parvenir à un consensus sur un modèle global. Les différents résultats obtenus montrent que les approches proposées réduisent considérablement la consommation d’énergie et les coûts de consommation, ce qui étend la durée de vie du réseau.Les résultats obtenus indiquent aussi que les approches proposées sont extrêmement efficaces en termes de calcul du modèle, de latence, de réduction de la taille des données, d’adaptabilité et de détection des événements
Recently, Wireless Sensor Networks (WSNs) have emerged as one of the most exciting fields. However, the common challenge of all sensor network applications remains the vulnerability of sensor nodes due to their characteristics and also the nature of the data generated which are of large volume, heterogeneous, and distributed. On the other hand, the need to process and extract knowledge from these large quantities of data motivated us to explore Data mining techniques and develop new approaches to improve the detection accuracy, the quality of information, the reduction of data size, and the extraction of knowledge from WSN datasets to help decision making. However, the classical Data mining methods are not directly applicable to WSNs due to their constraints.It is therefore necessary to satisfy the following objectives: an efficient solution offering a good adaptation of Data mining methods to the analysis of huge and continuously arriving data from WSNs, by taking into account the constraints of the sensor nodes which allows to extract knowledge in order to make better decisions. The contributions of this thesis focus mainly on the study of several distributed algorithms which can deal with the nature of sensed data and the resource constraints of sensor nodes based on the Data mining algorithms by first using the local computation at each node and then exchange messages with its neighbors, in order to reach consensus on a global model. The different results obtained show that the proposed approaches reduce the energy consumption and the communication cost considerably which extends the network lifetime.The results also indicate that the proposed approaches are extremely efficient in terms of model computation, latency, reduction of data size, adaptability, and event detection

Le développement d'applications avec une architecture Pair-à-Pair (P2P) est devenu de plus en plus important en ingénierie du logiciel. Aujourd'hui, un grand nombre d'organisations de tailles et secteurs différents compte d'une manière croissante sur la collaboration entre multiples acteurs (individus, groupes, communautés, etc.) pour accomplir des tâches essentielles. Ces applications P2P ont généralement un comportement récursif que plusieurs approches de modélisation ne peuvent pas décrire et analyser (ex. les approches basées sur les automates à états finis). Un autre challenge qui concerne le développement d'applications P2P est le couplage fort entre la spécification d'une part, et les technologies et protocoles sous-jacents d'autre part. Cela force les développeurs à faire des efforts considérables pour trouver puis comprendre des informations sur les détails de ces couches basses du P2P. De plus, ce couplage fort oblige les applications à s'exécuter dans des environnements figés. Par conséquent, choisir par exemple un autre protocole pour répondre à un nouveau besoin à l'exécution devient une tache très difficile. Outre ces points, les applications P2P sont souvent spécifiées avec une faible capacité à déléguer des traitements entre les pairs, et se focalisent surtout sur le partage et le stockage de données. Ainsi, elles ne profitent pas pleinement de la puissance de calcul et de traitement offerte par le réseau P2P sous-jacent. Dans cette thèse, nous présentons une approche qui combine les principes du développement orienté composants et services avec des techniques issues des Grammaires Attribuées et d'analyses de flot de données (techniques utilisées surtout dans la construction de compilateurs) afin de faciliter la spécification, l'analyse et le déploiement d'applications dans des architectures P2P. Cette approche incorpore: i) Un langage formel nommé DDF (de l'anglais Data-Dependency Formalism) pour spécifier les applications et construire leurs graphes de dépendances de données. Un graphe de dépendances de données est nommé DDG (de l'anglais Data-Dependency Graph) et est défini pour être une représentation abstraite de l'application spécifiée. ii) Une méthode d'analyse qui utilise le graphe de dépendances de données pour inférer et calculer diverses propriétés, y compris certaines propriétés que les model-checkers ne peuvent pas calculer si le système présente un comportement récursif. iii) Un intergiciel nommé SON (de l'anglais Shared data Overlay Network) afin de développer et d'exécuter des applications dans une architecture P2P sans faire face à la complexité des couches sous-jacentes. Cela grâce essentiellement au couplage faible (par une approche orientée services) et à la fonctionnalité de génération de code automatique.

Dans le domaine du calcul réparti à grande échelle (aussi appelé metacomputing), la plupart des projets existants n'exploitent pas les programmes déjà écrits pour bâtir des applications distribuées. La majorité de ces projets proposent une nouvelle interface pour programmer des applications, alors que beaucoup de librairies de programmes existent pour effectuer des calculs performants. Nous introduisons un modèle de composants et une plate-forme d'exécution, ainsi qu'un environnement de développement, pour permettre l'utilisation et l'interconnexion de composants hétérogènes au sein d'un ensemble de serveurs logiciels dispersés géographiquement, et interconnectés par un réseau à grande échelle, de type Internet. La puissance et la localisation des machines utilisées n'est pas connu à l'avance, et nous avons donc développé la plate-forme logicielle dans l'optique de possibles changements d'échelle. En particulier, il n'y a pas de composante centralisée. Le principal aspect de cette thèse est le fait que ces composants peuvent être pris tels quels sans modifier leur comportement. Cela sous entend que le contenu de ces composants, qu'il s'agisse d'un programme exécutable ou d'un script interprétable, ne peut pas subir d'introspection spécifique. Le second aspect important concerne les transferts de données entre ces composants. Les flux de données d'un composant sont explicités par son fournisseur lors de son installation. Les transferts de données s'effectuent par la plate-forme, en interceptant l'écriture de données en sortie de composant pour l'envoyer en entrée du composant qui lui est lié. Du point de vue d'un composant, ses flux d'entrée/sortie,sont considérés comme locaux alors que ces données proviennent d'un mécanisme que nous nommons connecteur. Chacun de nos connecteurs gère une ressource de communication spécifique en entrée ou en sortie (fichier, flux standard, socket, méthode) pour effectuer les transferts de données de manière appropriée. Les app1ications formées avec ces composants génériques sont développées facilement grâce aux outils fournis avec la plate-forme, en particulier une console graphique servant d'environnement de développement. Ces applications sont déployées automatiquement sur les machines disponibles, en fonction des besoins en matériel et logiciel de chacun, et exécutées par la plate-forme. Une implantation de ces concepts a été réalisée et testée au travers d'un exemple de génération d'arbres de regroupement d'espèces en phylogénie. Cette petite application, décrite préalablement et dont les composants binaires sont accessibles sur l'Internet, a été assemblée, déployée et exécutée. Elle valide donc le modèle, dans le sens où il est possible d'exploiter des composants totalement hétérogènes pour une exécution distribuée. Il reste toutefois quelques perspectives de recherche sur ce sujet, telles que la montée en charge, l'adaptation de notre modèle aux modèles de composants fortement typés, ou encore le développement incrémentaI de la. Plate-forme.

Dans de nombreux domaines, les nouvelles technologies d'acquisition de l'information ou encore de mesure (e.g. serres de phénotypage robotisées) ont engendré une création phénoménale de données. Nous nous appuyons en particulier sur deux cas d'application réels: les observations de plantes en botanique et les données de phénotypage en biologie. Cependant, nos contributions peuvent être généralisées aux données du Web. Par ailleurs, s'ajoute à la quantité des données leur distribution. Chaque utilisateur stocke en effet ses données sur divers sites hétérogènes (e.g. ordinateurs personnels, serveurs, cloud), données qu'il souhaite partager. Que ce soit pour les observations de botanique ou pour les données de phénotypage en biologie, des solutions collaboratives, comprenant des outils de recherche et de recommandation distribués, bénéficieraient aux utilisateurs. L'objectif général de ce travail est donc de définir un ensemble de techniques permettant le partage et la découverte de données, via l'application d'approches de recherche et de recommandation, dans un environnement distribué (e.g. sites hétérogènes).Pour cela, la recherche et la recommandation permettent aux utilisateurs de se voir présenter des résultats, ou des recommandations, à la fois pertinents par rapport à une requête qu'ils auraient soumise et par rapport à leur profil. Les techniques de diversification permettent de présenter aux utilisateurs des résultats offrant une meilleure nouveauté tout en évitant de les lasser par des contenus redondants et répétitifs. Grâce à la diversité, une distance entre toutes les recommandations est en effet introduite afin que celles-ci soient les plus représentatives possibles de l'ensemble des résultats pertinents. Peu de travaux exploitent la diversité des profils des utilisateurs partageant les données. Dans ce travail de thèse, nous montrons notamment que dans certains scénarios, diversifier les profils des utilisateurs apporte une nette amélioration en ce qui concerne la qualité des résultats~: des sondages montrent que dans plus de 75% des cas, les utilisateurs préfèrent la diversité des profils à celle des contenus. Par ailleurs, afin d'aborder les problèmes de distribution des données sur des sites hétérogènes, deux approches sont possibles. La première, les réseaux P2P, consiste à établir des liens entre chaque pair (noeud du réseau): étant donné un pair p, ceux avec lesquels il a établi un lien représentent son voisinage. Celui-ci est utilisé lorsque p soumet une requête q, pour y répondre. Cependant, dans les solutions de l'état de l'art, la redondance des profils des pairs présents dans les différents voisinages limitent la capacité du système à retrouver des résultats pertinents sur le réseau, étant donné les requêtes soumises par les utilisateurs. Nous montrons, dans ce travail, qu'introduire de la diversité dans le calcul du voisinage, en augmentant la couverture, permet un net gain en termes de qualité. En effet, en tenant compte de la diversité, chaque pair du voisinage a une plus forte probabilité de retourner des résultats nouveaux à l'utilisateur courant: lorsqu'une requête est soumise par un pair, notre approche permet de retrouver jusqu'à trois fois plus de bons résultats sur le réseau. La seconde approche de la distribution est le multisite. Généralement, dans les solutions de l'état de l'art, les sites sont homogènes et représentés par de gros centres de données. Dans notre contexte, nous proposons une approche permettant la collaboration de sites hétérogènes, tels que de petits serveurs d'équipe, des ordinateurs personnels ou de gros sites dans le cloud. Un prototype est issu de cette contribution. Deux versions du prototype ont été réalisées afin de répondre aux deux cas d'application, en s'adaptant notamment aux types des données
In many fields, novel technologies employed in information acquisition and measurement (e.g. phenotyping automated greenhouses) are at the basis of a phenomenal creation of data. In particular, we focus on two real use cases: plants observations in botany and phenotyping data in biology. Our contributions can be, however, generalized to Web data. In addition to their huge volume, data are also distributed. Indeed, each user stores their data in many heterogeneous sites (e.g. personal computers, servers, cloud); yet he wants to be able to share them. In both use cases, collaborative solutions, including distributed search and recommendation techniques, could benefit to the user.Thus, the global objective of this work is to define a set of techniques enabling sharing and discovery of data in heterogeneous distributed environment, through the use of search and recommendation approaches.For this purpose, search and recommendation allow users to be presented sets of results, or recommendations, that are both relevant to the queries submitted by the users and with respect to their profiles. Diversification techniques allow users to receive results with better novelty while avoiding redundant and repetitive content. By introducing a distance between each result presented to the user, diversity enables to return a broader set of relevant items.However, few works exploit profile diversity, which takes into account the users that share each item. In this work, we show that in some scenarios, considering profile diversity enables a consequent increase in results quality: surveys show that in more than 75% of the cases, users would prefer profile diversity to content diversity.Additionally, in order to address the problems related to data distribution among heterogeneous sites, two approaches are possible. First, P2P networks aim at establishing links between peers (nodes of the network): creating in this way an overlay network, where peers directly connected to a given peer p are known as his neighbors. This overlay is used to process queries submitted by each peer. However, in state of the art solutions, the redundancy of the peers in the various neighborhoods limits the capacity of the system to retrieve relevant items on the network, given the queries submitted by the users. In this work, we show that introducing diversity in the computation of the neighborhood, by increasing the coverage, enables a huge gain in terms of quality. By taking into account diversity, each peer in a given neighborhood has indeed, a higher probability to return different results given a keywords query compared to the other peers in the neighborhood. Whenever a query is submitted by a peer, our approach can retrieve up to three times more relevant items than state of the art solutions.The second category of approaches is called multi-site. Generally, in state of the art multi-sites solutions, the sites are homogeneous and consist in big data centers. In our context, we propose an approach enabling sharing among heterogeneous sites, such as small research teams servers, personal computers or big sites in the cloud. A prototype regrouping all contributions have been developed, with two versions addressing each of the use cases considered in this thesis

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

Le pattern mining est un domaine du data mining dont le but est l'extraction de régularité dans les données. Ce document présente nos contributions au domaine selon 3 axes : 1. Le domaine du pattern mining est jeune et il y existe encore beaucoup de types de régularités qu'un analyste serait intéressé de découvrir mais qui ne sont pas encore gérées. Nous avons contribué à deux nouveaux types de patterns: les patterns graduels et les patterns périodiques avec "ruptures". Nous avons aussi proposé ParaMiner, un algorithme original pour le pattern mining générique, qui permet à des analystes de spécifier directement le type de patterns qui les intéressent. 2. Le pattern mining demande beaucoup de ressources de calcul. Pour réduire le temps de calcul, nous avons étudié comment exploiter le parallélisme des processeurs multicoeurs. Nos résultats montrent que des techniques classiques en pattern mining sont mal adaptées au parallélisme, et nous avons proposé des solutions. 3. Notre objectif à long terme est de rendre le pattern mining plus facile à utiliser par les analystes. Il y a beaucoup à faire dans ce but, actuellement les analystes doivent travailler sur de longues listes de millions de patterns. Nous présentons nos premiers résultats, dans le contexte de la fouille de traces d'exécution de processeurs.

Le diagnostic est aujourd'hui plus que jamais un thème de recherche pertinent. La sécurité est en effet au cSur des préoccupations de la société d'aujourd'hui. Les enjeux tant économiques, sociétaux qu'environnementaux en font un des axes majeurs d'innovation pour l'industrie actuelle. Aujourd'hui la conception et l'exploitation des systèmes doivent être abordées en intégrant une dimension sécurité dont le diagnostic fait partie intégrante. C'est dans cette problématique du diagnostic (incluant la détection et le pronostic) que s'inscrivent nos travaux. Deux thèmes de recherches sont explorés : - les modèles et les sources de connaissances pour le diagnostic. Ce thème de recherche couvre les aspects multi-modèles (modèle du procédé, modèle de surveillance, modèle de stratégie &) pour la surveillance, et met en avant la pertinence d'utiliser des sources d'informations variées (ordonnancement, AMDE, historiques &) pour mettre en place une fonction diagnostic. La génération d'un modèle de comportement à partir de données classifiées est également abordée dans ce thème. Une approche de surveillance reposant sur l'observation de la trajectoire d'un système dynamique au travers d'une séquence d'assignations de l'état courant à des classes est développée. - le diagnostic distribué. Les approches proposées ici se focalisent sur la distribution des fonctions et des modèles. Une approche de détection distribuée basée sur un modèle temporel (contraintes) du comportement est développée. Une extension vers le diagnostic embarqué dans le domaine automobile s'appuyant sur un modèle du comportement issu des données de conception est également présentée. Sur la base de ces travaux notre projet de recherche concerne d'une part l'utilisation des approches basées données pour structurer les connaissances et générer automatiquement des modèles exploitables par des méthodes de diagnostic basées modèles, d'autre part la problématique du diagnostic pour l'aide à la décision, notamme nt dans les systèmes où la dimension humaine doit être considérée

Cette thèse porte sur l'étude des techniques de fusion de données réparties et incertaines au sein d'un réseau de véhicules pour gérer la confiance dans les autres véhicules ou dans les données reçues. L'algorithme de fusion distribuée proposé est basé sur les fonctions de croyance et est appliqué par chaque nœud à la réception des messages. In se base sur la gestion d'une connaissance directe, locale à chaque nœud et d'une connaissance distribuée diffusée dans le réseau. Cette dernière résulte de la fusion des messages par un opérateur adapté prenant en compte les cycles éventuels et limitant l'effet de "data incest". Chaque nœud peut être autonome pour estimer la confiance mais la coopération entre les véhicules permet d'améliorer et de rendre plus robuste cette estimation. L'algorithme peut être adapté au cas d'étude en considérant un ou plusieurs éléments d'observation et en prenant en compte l'obsolescence des données. Lorsqu'il y a plusieurs éléments d'observation, se pose le problème de l'association de données nécessaire avant l'étape de combinaison. Un nouvel algorithme d'association a été formalisé dans le cadre des fonctions de croyance. Il a été démontré que ce problème est équivalent à un problème d'affectation linéaire, qui peut être résolu en temps polynomial. Cette solution est à la fois optimale et beaucoup plus efficace que d'autres approches développées dans ce formalisme. La gestion de la confiance dans les nœuds et dans les données échangées ont été illustrées par la mise en œuvre de deux applications : la détection de faux nœuds dans une attaque Sybil et la gestion de la confiance dans les cartes dynamiques pour la perception augmentée.

Notre utilisation quotidienne de l’Internet et des technologies connexes génère, de manière continue et à des vitesses rapides et variables, de grandes quantités de données hétérogènes issues des réseaux de capteurs, des logs de moteurs de recherches génériques ou spécialisés, des données de sites de contenu multimédia, des données de mesure de stations météorologiques, de la géolocalisation, des applications IoT (l’Internet des objets), etc. Traiter de telles données dans les bases de données conventionnelles (Systèmes de Gestion de Bases de Données Relationnelles) peut être très coûteux en ressources temporelles et mémoires. Pour répondre efficacement aux besoins et aider à la prise de décision, ces flots d’informations nécessitent des traitements en temps réel. Les Systèmes de Gestion de Flux de Données (SGFDs) posent et évaluent des requêtes sur les données récentes d’un flux dans des structures appelées fenêtre. Les données en entrée des SGFDs sont de différents formats bruts tels que CSV, XML, RSS, ou encore JSON. Ce verrou d’hétérogénéité émane de la nature des flux de données et doit être levé. Pour cela, plusieurs groupes de recherche ont bénéficié des avantages des technologies du web sémantique (RDF et SPARQL) en proposant des systèmes de traitement de flux de données RDF appelés RSPs. Cependant, la volumétrie des données, le débit d’entrée élevé, les requêtes concurrentes, le croisement des flux RDF à de larges volumes de données stockées et les calculs coûteux baissent considérablement les performances de ces systèmes. Il faut prévoir une nouvelle approche de réduction de la charge de traitement des flux de données RDF. Dans cette thèse, nous proposons plusieurs solutions pour réduire la charge de traitement de flux de données en mode centralisé. Une approche d’échantillonnage à la volée de flux de graphes RDF est proposée afin de réduire la charge de données et du traitement des flux tout en préservant les liens sémantiques. Cette approche est approfondie en adoptant une méthode de résumé orienté graphe pour extraire des graphes RDF les informations les plus pertinentes en utilisant des mesures de centralité issues de l’Analyse des Réseaux Sociaux. Nous adoptons également un format compressé des données RDF et proposons une approche d’interrogation de données RDF compressées sans phase de décompression. Pour assurer une gestion parallèle et distribuée des flux de données, le travail présenté propose deux solutions supplémentaires de réduction de la charge de traitement en mode distribué : un moteur de traitement parallèle et distribué de flux de graphes RDF et une approche de traitement optimisé des opérations de croisement entre données statiques et dynamiques sont présentés
Our daily use of the Internet and related technologies generates, at a rapid and variable speeds, large volumes of heterogeneous data issued from sensor networks, search engine logs, multimedia content sites, weather forecasting, geolocation, Internet of Things (IoT) applications, etc. Processing such data in conventional databases (Relational Database Management Systems) may be very expensive in terms of time and memory storage resources. To effectively respond to the needs of rapid decision-making, these streams require real-time processing. Data Stream Management Systems (SGFDs) evaluate queries on the recent data of a stream within structures called windows. The input data are different formats such as CSV, XML, RSS, or JSON. This heterogeneity lock comes from the nature of the data streams and must be resolved. For this, several research groups have benefited from the advantages of semantic web technologies (RDF and SPARQL) by proposing RDF data streams processing systems called RSPs. However, large volumes of RDF data, high input streams, concurrent queries, combination of RDF streams and large volumes of stored RDF data and expensive processing drastically reduce the performance of these systems. A new approach is required to considerably reduce the processing load of RDF data streams. In this thesis, we propose several complementary solutions to reduce the processing load in centralized environment. An on-the-fly RDF graphs streams sampling approach is proposed to reduce data and processing load while preserving semantic links. This approach is deepened by adopting a graph-oriented summary approach to extract the most relevant information from RDF graphs by using centrality measures issued from the Social Networks Analysis. We also adopt a compressed format of RDF data and propose an approach for querying compressed RDF data without decompression phase. To ensure parallel and distributed data streams management, the presented work also proposes two solutions for reducing the processing load in distributed environment. An engine and parallel processing approaches and distributed RDF graphs streams. Finally, an optimized processing approach for static and dynamic data combination operations is also integrated into a new distributed RDF graphs streams management system

L'adaptation dynamique permet de modifier une application en cours d'exécution en fonction des fluctuations de son environnement et des changements des exigences des utilisateurs. De nombreux travaux ont proposé des méthodes et mécanismes pour adapter une application centralisée. Mais, le cas des applications distribuées a été beaucoup moins abordé. En particulier, la distribution du système d'adaptation lui-même est très peu envisagée. Nous proposons dans cette thèse une approche visant à définir une architecture logicielle à base de composants pour permettre la gestion distribuée et coordonnée de l'adaptation dynamique d'applications. Nous définissons un modèle d'architecture logicielle de systèmes d'adaptation qui permet la variabilité des configurations du système et qui inclut des mécanismes spécialisables pour assurer la coordination. Le domaine d'application choisi pour illustrer notre approche d'adaptation est la gestion de données répliquées. Dans ce domaine, nous avons développé un prototype pour la construction de systèmes d'adaptation distribués d'une part, et de systèmes de réplication d'autre part. Le prototype, qui se base sur le modèle de composants Fractal, nous a permis de mener des expérimentations d'adaptation distribuée sur un système de réplication de données en milieu médical pour le suivi d'un patient à domicile.

Cette thèse est centrée sur la modélisation de l'exécution d'une application parallèle par un graphe de flot de données. Ce graphe, qui relie les tâches aux données partagées, est construit de manière dynamique. Cette construction, indépendante de l'ordonnancement des tâches effectué, permet de définir la sémantique des accès aux données et de controler la consommation mémoire de toute exécution. Nous étudions dans une première partie les algorithmes permettant la construction et la gestion d'un tel graphe de flot de données dans un environnement distribué. Un point crucial de ces algorithmes est la détection de terminaison des accès des tâches sur les données partagées. Nous proposons un algorithme réactif réalisant cette détection. L'implantation de cet algorithme est au centre de l'implantation distribuée de l'interface de programmation parallèle Athapascan-1. Cette interface permet la description du parallélisme d'une application par création de tâches asynchrones. La sémantique (de type lexicographique) de cette interface est également définie à partir du graphe de flot de données. Nous montrons dans une deuxième partie que la connaissance du flot de données d'une application permet de controler de manière théorique la durée et, surtout, la consommation mémoire de toute exécution. Ce controle est effectué à partir d'un ordonnancement séquentiel implicite des tâches. Nous proposons, implantons dans Athapascan-1 et évaluons deux algorithmes d'ordonnancement distribués permettant de limiter le volume de mémoire requis par toute exécution. Ces expérimentations permettent de valider les résultats théoriques obtenus.

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

Les communautés en ligne pair-a-pair (P2P), comme les communautés professionnelles (p. Ex. , médicales ou de recherche) deviennent de plus en plus populaires a cause de l’augmentation des besoins du partage de données. Alors que les environnements P2P offrent des caractéristiques intéressantes (p. Ex. , passage a l’échelle, disponibilité, dynamicité), leurs garanties en termes de protection des données sensibles sont limitées. Ils peuvent être considérés comme hostiles car les données publiées peuvent être consultées par tous les pairs (potentiellement malicieux) et utilisées pour tout (p. Ex. , pour le commerce illicite ou tout simplement pour des activités contre les préférences personnelles ou éthiques du propriétaire des données). Cette thèse propose un service qui permet le partage de données sensibles dans les systèmes P2P, tout en assurant leur confidentialité. La première contribution est l’analyse des techniques existant pour la confidentialité de données dans les architectures P2P. La deuxième contribution est un modèle de confidentialité, nomme PriMod, qui permet aux propriétaires de données de spécifier leurs préférences de confidentialité dans de politiques de confidentialité et d’attacher ces politiques a leurs données sensibles. La troisième contribution est le développement de PriServ, un service de confidentialité, base sur une DHT qui met en oeuvre PriMod afin de prévenir la violation de la confidentialité de données. Entre autres, PriServ utilise de techniques de confiance pour prédire le comportement des pairs
Online peer-to-peer (P2P) communities such as professional ones (e. G. , medical or research communities) are becoming popular due to increasing needs on data sharing. P2P environments offer valuable characteristics but limited guarantees when sharing sensitive data. They can be considered as hostile because data can be accessed by everyone (by potentially malicious peers) and used for everything (e. G. , for marketing or for activities against the owner’s preferences or ethics). This thesis proposes a privacy service that allows sharing sensitive data in P2P systems while protecting their privacy. The first contribution consists on analyzing existing techniques for data privacy in P2P architectures. The second contribution is a privacy model for P2P systems named PriMod which allows data owners to specify their privacy preferences in privacy policies and to associate them with their data. The third contribution is the development of PriServ, a privacy service located on top of DHT-based P2P systems which implements PriMod to prevent data privacy violations. Among others, PriServ uses trust techniques to predict peers behavior

La deuxième décennie du millénaire actuel peut être résumée en une courte phrase : l'essor des données. Le nombre de sources de données s'est multiplié : du streaming audio-vidéo aux réseaux sociaux et à l'Internet des Objets, en passant par les montres intelligentes, les équipements industriels et les véhicules personnels, pour n'en citer que quelques-unes. Le plus souvent, ces sources forment des réseaux afin d'échanger des informations. En conséquence directe, le domaine du Traitement de Signal sur Graphe a prospéré et a évolué. Son but : traiter et donner un sens à tout le déluge de données environnant. Dans ce contexte, le but principal de cette thèse est de développer des méthodes et des algorithmes capables d'utiliser des flots de données, de manière distribuée, afin d'inférer les réseaux sous-jacents qui relient ces flots. Ensuite, ces topologies de réseau estimées peuvent être utilisées avec des outils développés pour le Traitement de Signal sur Graphe afin de traiter et d'analyser les données supportées par des graphes. Après une brève introduction suivie d'exemples motivants, nous développons et proposons d'abord un algorithme en ligne, distribué et adaptatif pour l'inférence de topologies de graphes pour les flots de données qui sont linéairement dépendants. Une analyse de la méthode s'ensuit, afin d'établir des relations entre les performances et les paramètres nécessaires à l'algorithme. Nous menons ensuite une série d'expériences afin de valider l'analyse et de comparer ses performances avec celles d'une autre méthode proposée dans la littérature. La contribution suivante est un algorithme doté des mêmes capacités en ligne, distribuées et adaptatives, mais adapté à l'inférence de liens entre des données qui interagissent de manière non-linéaire. À ce titre, nous proposons un modèle additif simple mais efficace qui utilise l'usine du noyau reproduisant afin de modéliser lesdites non-linéarités. Les résultats de son analyse sont convaincants, tandis que les expériences menées sur des données biomédicales donnent des réseaux estimés qui présentent un comportement prédit par la littérature médicale. Enfin, une troisième proposition d'algorithme est faite, qui vise à améliorer le modèle non-linéaire en lui permettant d'échapper aux contraintes induites par l'additivité. Ainsi, le nouveau modèle proposé est aussi général que possible, et utilise une manière naturelle et intuitive d'imposer la parcimonie des liens, basée sur le concept de dérivés partiels. Nous analysons également l'algorithme proposé, afin d'établir les conditions de stabilité et les relations entre ses paramètres et ses performances. Une série d'expériences est menée, montrant comment le modèle général est capable de mieux saisir les liens non-linéaires entre les données, tandis que les réseaux estimés se comportent de manière cohérente avec les estimations précédentes
The second decade of the current millennium can be summarized in one short phrase: the advent of data. There has been a surge in the number of data sources: from audio-video streaming, social networks and the Internet of Things, to smartwatches, industrial equipment and personal vehicles, just to name a few. More often than not, these sources form networks in order to exchange information. As a direct consequence, the field of Graph Signal Processing has been thriving and evolving. Its aim: process and make sense of all the surrounding data deluge.In this context, the main goal of this thesis is developing methods and algorithms capable of using data streams, in a distributed fashion, in order to infer the underlying networks that link these streams. Then, these estimated network topologies can be used with tools developed for Graph Signal Processing in order to process and analyze data supported by graphs. After a brief introduction followed by motivating examples, we first develop and propose an online, distributed and adaptive algorithm for graph topology inference for data streams which are linearly dependent. An analysis of the method ensues, in order to establish relations between performance and the input parameters of the algorithm. We then run a set of experiments in order to validate the analysis, as well as compare its performance with that of another proposed method of the literature.The next contribution is in the shape of an algorithm endowed with the same online, distributed and adaptive capacities, but adapted to inferring links between data that interact non-linearly. As such, we propose a simple yet effective additive model which makes use of the reproducing kernel machinery in order to model said nonlinearities. The results if its analysis are convincing, while experiments ran on biomedical data yield estimated networks which exhibit behavior predicted by medical literature.Finally, a third algorithm proposition is made, which aims to improve the nonlinear model by allowing it to escape the constraints induced by additivity. As such, the newly proposed model is as general as possible, and makes use of a natural and intuitive manner of imposing link sparsity, based on the concept of partial derivatives. We analyze this proposed algorithm as well, in order to establish stability conditions and relations between its parameters and its performance. A set of experiments are ran, showcasing how the general model is able to better capture nonlinear links in the data, while the estimated networks behave coherently with previous estimates

Les systèmes de stockage distribués sont massivement utilisés dans le contexte actuel des grandes masses de données. En plus de gérer le stockage de ces données, ces systèmes doivent répondre à une quantité toujours plus importante de requêtes émises par des clients distants afin d’effectuer de la fouille de données ou encore de la visualisation. Une problématique majeure dans ce contexte consiste à répartir efficacement les requêtes entre les différents noeuds qui composent ces systèmes afin de minimiser le temps de traitement des requêtes ( temps maximum et en moyenne d’une requête, temps total de traitement pour toutes les requêtes...). Dans cette thèse nous nous intéressons au problème d’allocation de requêtes dans un environnement distribué. On considère que les données sont répliquées et que les requêtes sont traitées par les noeuds stockant une copie de la donnée concernée. Dans un premier temps, des solutions algorithmiques quasi-optimales sont proposées lorsque les communications entre les différents noeuds du système se font de manière asynchrone. Le cas où certains noeuds du système peuvent être en panne est également considéré. Dans un deuxième temps, nous nous intéressons à l’impact de la réplication des données sur le traitement des requêtes. En particulier, un algorithme qui adapte la réplication des données en fonction de la demande est proposé. Cet algorithme couplé à nos algorithmes d’allocation permet de garantir une répartition des requêtes proche de l’idéal pour toute distribution de requêtes. Enfin, nous nous intéressons à l’impact de la réplication quand les requêtes arrivent en flux sur le système. Nous procédons à une évaluation expérimentale sur la base de données distribuées Apache Cassandra. Les expériences réalisées confirment l’intérêt de la réplication et de nos algorithmes d’allocation vis-à-vis des solutions présentes par défaut dans ce système
Distributed data store are massively used in the actual context of Big Data. In addition to provide data management features, those systems have to deal with an increasing amount of queries sent by distant users in order to process data mining or data visualization operations. One of the main challenge is to evenly distribute the workload of queries between the nodes which compose these system in order to minimize the treatment time. In this thesis, we tackle the problem of query allocation in a distributed environment. We consider that data are replicated and a query can be handle only by a node storing the concerning data. First, near-optimal algorithmic proposals are given when communications between nodes are asynchronous. We also consider that some nodes can be faulty. Second, we study more deeply the impact of data replication on the query treatement. Particularly, we present an algorithm which manage the data replication based on the demand on these data. Combined with our allocation algorithm, we guaranty a near-optimal allocation. Finally, we focus on the impact of data replication when queries are received as a stream by the system. We make an experimental evaluation using the distributed database Apache Cassandra. The experiments confirm the interest of our algorithmic proposals to improve the query treatement compared to the native allocation scheme in Cassandra

Les deux dernières décennies ont été marquées par l’apparition de nouveaux concepts architecturaux entraînant une évolution vers les systèmes distribués. C’est une conséquence de l’augmentation de la capacité de stockage des mémoires et de calcul et de l’arrivée de réseaux à haut débit, notamment locaux à 1Gb/s. La tendance dominante est le développement de nouveaux systèmes, dits d’abord: multi-ordinateur, Réseau de Stations de Travail et plus récemment, « Peer-to-Peer Computing » ou « Grid Computing ». Afin de tirer le meilleur profit des potentialités offertes, de nouvelles structures de données spécifiques aux données réparties sont nécessaires. Dans ce contexte, Les Structures de Données Distribuées et Scalables (SDDS) sont une nouvelle classe de structures introduites spécifiquement pour la gestion de fichiers sur un multi¬ ordinateur. Un fichier SDDS peut s'étendre dynamiquement, au fur et à mesure des insertions, d'un seul site de stockage à tout nombre de sites interconnectés disponibles en pratique. Les algorithmes d'adressages d'une SDDS sont conçus spécifiquement pour être scalables, notamment par absence d'un répertoire ou index central. La répartition de données est transparente pour l'application. Les données manipulées peuvent être entièrement en RAM distribuée afin d’être accessibles bien plus vite qu’à partir des disques. Plusieurs SDDS ont été proposées. Les plus connues sont celles basées sur le hachage, celui linéaire (LH*) notamment, et celles utilisant le partitionnement par intervalle (RP*). Un prototype appelé SDDS-2000a été construit vers l’année 2000 au CERIA pour expérimenter avec les SDDS sur les réseaux locaux des PC sous Windows. Dans ce système, on retrouve les fonctions de base de gestion de données telles que la création de fichiers, l’insertion d’enregistrements ou encore la possibilité de requêtes parallèles. En se basant sur SDDS-2000, notre Thèse a pour objectif la conception et l’implantation de nouvelles fonctions pour celui ci. Ces fonctions sont destinées à la sauvegarde de données sur le disque, un traitement plus efficace de mises à jour, le traitement de concurrence ainsi que celui de la recherche par le contenu (scans). Enfin, pour mieux répondre au contexte P2P, il nous fallait introduire une certaine protection de données stockées, au moins contre une découverte accidentelle de leurs valeurs. Ceci nous a conduit au problème intéressant de recherche de données par l’exploration directe de leur contenu encodé, sans décodage local. Nous avons basé l’ensemble de nos fonctions sur une technique nouvelle dite de signatures algébriques. Nous détaillons la théorie et notre pratique de signatures algébriques tout au long de cette Thèse. Ainsi, une sauvegarde sur disque n’écrit que les parties de la RAM modifiées depuis la dernière sauvegarde. Le contrôle de concurrence est optimiste, sans verrouillage, pour de meilleures performances d’accès. L’enregistrement mis à jour n’est envoyé au serveur que si la donnée est réellement modifiée. Puis, les données stockées sont suffisamment encodées pour rendre impossible toute découverte accidentelle de leurs valeurs réelles sur les serveurs. Nous les encodons à l’aide d’une variante de signatures algébriques, les signatures cumulatives. Notre encodage possède notamment des propriétés accélérant diverses recherches de chaînes de caractères, par rapport à celles explorant les mêmes données sans encodage. D’une manière un peu surprenante, certaines recherches se révèlent expérimentalement plus rapides que par des algorithmes fondamentaux bien connus, tels que celui de Karp-Rabin. Nous présentons des mesures de performance prouvant l’efficacité de notre approche. Notre système, appelé SDS-2005, a été dès lors annoncé sur DbWorld. Il est disponible sur le site du CERIA pour les téléchargements non commerciaux. Les détails de nos travaux ont fait l’objet de cinq publications dans des conférences internationales [LMS03, LMS05a, LMS05b, M06, LMRS06]. Notre prototype a également été montré à de nombreux visiteurs chercheurs. Il a fait l’objet d’une démonstration vidéo, diffusée notamment à Microsoft Research (Montain View, USA) et d’une présentation lors des journées académiques Microsoft. Dans notre mémoire, nous présentons d’abord l'état de l'art sur les SDDSs, en se basant sur celui de systèmes de fichiers distribués. Puis nous discutons l'architecture système de SDDS-2005. Celle-ci emploie notamment des structures de données spécifiques pour RAM, ainsi que des processus légers qui gèrent les traitements répartis à travers des files d'attente asynchrones. On présente ensuite le concept de signatures algébriques. Puis on détaille l’usage pour la sauvegarde d’un fichier SDDS et la mise à jour d’enregistrements. Nous discutons ensuite les signatures cumulatives. On décrit l’encodage de nos enregistrements. On présente les différents types de recherche par contenu non-clé (scans) dans notre système notamment la recherche par le préfixe et celle partielle d’une chaîne de caractère (ang pattern matching ou string search…) à travers plusieurs algorithmes alternatifs. Nous présentons un nouvel algorithme dit par n-Gramme semblant particulièrement simple d’usage et rapide On décrit aussi la recherche du plus grand préfixe et de la plus grande chaîne commune. Nous montrons que les signatures cumulatives sont particulièrement efficaces pour la recherche de longues chaînes telles que les images, les empreintes, les codes DNA…En réflexion sur les perspectives, on discute l’utilisation de ces signatures pour la compression différentielles lors des mises à jour distribuées des données ainsi que la protection contre la corruption silencieuse de données stockées. Puis nous discutons l’analyse expérimentale de notre système. Les mesures montrent la scalabilité de notre système ainsi que les temps d’exécution de nos différentes fonctions. On finit par des conclusions, perspectives et les références bibliographiques. Les annexes montrent nos principales publications (pour la convenance des membres anglophones de notre jury tout particulièrement). On y montre aussi la description de l’interface offerte aux applications par SDDS-2005, annoncée sur DbWorld
Recent years saw emergence of new architectures, involving multiple computers. New concepts were proposed. Among most popular are those of a multicomputer or of a Network of Worksattion and more recently, of Peer to Peer and Grid Computing. This thesis consists on the design, implementation and performance measurements of a prototype SDDS manager, called SDDS-2005. It manages key based ordered files in distributed RAM of Windows machines forming a grid or P2P network. Our scheme can backup the RAM on each storage node onto the local disk. Our goal is to write only the data that has changed since the last backup. We interest also to update records and non key search (scans). Their common denominator was some application of the properties of new signature scheme based that we call algebraic signatures, which are useful in this context. Ones needs then to find only the areas that changed in the bucket since the last buckup. Our signature based scheme for updating records at the SDDS client should prove its advantages in client-server based database systems in general. It holds the promise of interesting possibilities for transactional concurrency control, beyond the mere avoidance of lost updates. We also update only data have been changed because of the using the algebraic signatures. Also, partly pre-computed algebraic signature of a string encodes each symbol by its cumulative signatures. They protect the SDDS data against incidental viewing by an unauthorized server’s administrator. The method appears attractive, it does not amply any storage overhead. It is also completly transparent for servers and occurs in client. Next, our cheme provide fast string search (match) directly on encoded data at the SDDS servers. They appear an alternative to known Karp-Rabin type schemes. Scans can explore the storage nodes in parallel. They match the records by entire non-key content or by its substring, prefix, longest common prefix or longest common string. The search complexity is almost O (1) for prefix search. One may use them also to detect and localize the silent corruption. These features should be of interest to P2P and grid computing. Then, we propose novel string search algorithm called n-Gramme search. It also appears then among the fastest known, e. G, probably often the faster one we know. It cost only a small fraction of existing records match, especially for larger strings search. The experiments prove high efficiency of our implementation. Our buckup scheme is substantially more efficient with the algebraic signatures. The signature calculus is itself substantially faster, the gain being about 30 %. Also, experiments prove that our cumulative pre-computing notably accelerates the string searchs which are faster than the partial one, at the expense of higher encoding/decoding overhead. They are new alternatives to known Karp-Rabin type schemes, and likely to be usually faster. The speed of string matches opens interesting perspectives for the popular join, group-by, rollup, and cube database operations. Our work has been subject of five publications in international conferences [LMS03, LMS05a, LMS05b, ML06, l&al06]. For convenience, we have included the latest publications. Also, the package termed SDDS-2005 is available for non-commercial use at http://ceria. Dauphine. Fr/. It builds up on earlier versions of the prototype, a cumulative effort of several folks and n-Gramme algorithm implementation. We have also presented our proposed prototype, SDDS-2005, at the Microsoft Research Academic Days 2006

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations n-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques.

Les utilisateurs des bases de données doivent faire face au problème de surcharge d’information lors de l’interrogation de leurs données, qui se traduit par un nombre de réponses trop élevé à des requêtes exploratoires. Pour remédier à ce problème, nous proposons un algorithme efficace et rapide, appelé ESRA (Explore-Select-Rearrange Algorithm), qui utilise les résumés SAINTETIQ pré-calculés sur l’ensemble des données pour regrouper les réponses à une requête utilisateur en un ensemble de classes (ou résumés) organisées hiérarchiquement. Chaque classe décrit un sous-ensemble de résultatsdont les propriétés sont voisines. L’utilisateur pourra ainsi explorer la hiérarchie pour localiser les données qui l’intéressent et en écarter les autres. Les résultats expérimentaux montrent que l’algorithme ESRA est efficace et fournit des classes bien formées (i. E. , leur nombre reste faible et elles sont bien séparées). Cependant, le modèle SAINTETIQ, utilisé par l’algorithme ESRA, exige que les données soient disponibles sur le serveur des résumés. Cette hypothèse rend inapplicable l’algorithme ESRA dans des environnements distribués où il est souvent impossible ou peu souhaitable de rassembler toutes les données sur un même site. Pour remédier à ce problème, nous proposons une collection d’algorithmes qui combinent deux résumés générés localement et de manière autonome sur deux sites distincts pour en produire un seul résumant l’ensemble des données distribuées, sans accéder aux données d’origine. Les résultats expérimentaux montrent que ces algorithmes sont aussi performants que l’approche centralisée (i. E. , SAINTETIQ appliqué aux données après regroupement sur un même site) et produisent des hiérarchies très semblables en structure et en qualité à celles produites par l’approche centralisée
Database systems are increasingly used for interactive and exploratory data retrieval. In such retrievals, users queries often result in too many answers, so users waste significant time and efforts sifting and sorting through these answers to find the relevant ones. In this thesis, we first propose an efficient and effective algorithm coined Explore-Select-Rearrange Algorithm (ESRA), based on the SAINTETIQ model, to quickly provide users with hierarchical clustering schemas of their query results. SAINTETIQ is a domain knowledge-based approach that provides multi-resolution summaries of structured data stored into a database. Each node (or summary) of the hierarchy provided by ESRA describes a subset of the result set in a user-friendly form based on domain knowledge. The user then navigates through this hierarchy structure in a top-down fashion, exploring the summaries of interest while ignoring the rest. Experimental results show that the ESRA algorithm is efficient and provides well-formed (tight and clearly separated) and well-organized clusters of query results. The ESRA algorithm assumes that the summary hierarchy of the queried data is already built using SAINTETIQ and available as input. However, SAINTETIQ requires full access to the data which is going to be summarized. This requirement severely limits the applicability of the ESRA algorithm in a distributed environment, where data is distributed across many sites and transmitting the data to a central site is not feasible or even desirable. The second contribution of this thesis is therefore a solution for summarizing distributed data without a prior “unification” of the data sources. We assume that the sources maintain their own summary hierarchies (local models), and we propose new algorithms for merging them into a single final one (global model). An experimental study shows that our merging algorithms result in high quality clustering schemas of the entire distributed data and are very efficient in terms of computational time

Au cours des dernières années, le volume des données qui sont capturées et générées a explosé. Les progrès des technologies informatiques, qui fournissent du stockage à bas prix et une très forte puissance de calcul, ont permis aux organisations d'exécuter des analyses complexes de leurs données et d'en extraire des connaissances précieuses. Cette tendance a été très importante non seulement pour l'industrie, mais a également pour la science, où les meilleures instruments et les simulations les plus complexes ont besoin d'une gestion efficace des quantités énormes de données. Le parallélisme est une technique fondamentale dans la gestion de données extrêmement volumineuses car il tire parti de l'utilisation simultanée de plusieurs ressources informatiques. Pour profiter du calcul parallèle, nous avons besoin de techniques de partitionnement de données efficaces, qui sont en charge de la division de l'ensemble des données en plusieurs partitions et leur attribution aux nœuds de calculs. Le partitionnement de données est un problème complexe, car il doit prendre en compte des questions différentes et souvent contradictoires telles que la localité des données, la répartition de charge et la maximisation du parallélisme. Dans cette thèse, nous étudions le problème de partitionnement de données, en particulier dans les bases de données parallèles scientifiques qui sont continuellement en croissance. Nous étudions également ces partitionnements dans le cadre MapReduce. Dans le premier cas, nous considérons le partitionnement de très grandes bases de données dans lesquelles des nouveaux éléments sont ajoutés en permanence, avec pour exemple une application aux données astronomiques. Les approches existantes sont limitées à cause de la complexité de la charge de travail et l'ajout en continu de nouvelles données limitent l'utilisation d'approches traditionnelles. Nous proposons deux algorithmes de partitionnement dynamique qui attribuent les nouvelles données aux partitions en utilisant une technique basée sur l'affinité. Nos algorithmes permettent d'obtenir de très bons partitionnements des données en un temps d'exécution réduit comparé aux approches traditionnelles. Nous étudions également comment améliorer la performance du framework MapReduce en utilisant des techniques de partitionnement de données. En particulier, nous sommes intéressés par le partitionnement efficient de données d'entrée avec l'objectif de réduire la quantité de données qui devront être transférées dans la phase intermédiaire, connu aussi comme " shuffle ". Nous concevons et mettons en œuvre une stratégie qui, en capturant les relations entre les tuples d'entrée et les clés intermédiaires, obtient un partitionnement efficace qui peut être utilisé pour réduire de manière significative le surcharge de communications dans MapReduce.

Les langages de quatrieme generation ont pour vocation de repondre a un besoins pour les utilisateurs finaux de developper eux-memes leurs applications. Cependant, la montee en puissance de la micro-informatique et, l'avenement des reseaux locaux font apparaitre la necessite de mettre en uvre des applications complexes. Pour cela, les developpeurs doivent disposer d'outils puissants, certes moins accessibles aux novices, mais bien plus adaptes aux professionnels du developpement. Une etude detaillee des concepts utilises dans les langages de quatrieme generation existants sert de base a la determination de l'environnement le mieux adapte pour le developpement, en milieu reparti, d'applications pointues et conviviales. Un environnement issu de cette etude est alors propose: mime est concu pour la mise en uvre, par des specialistes du developpement, d'applications complexes supportees par des reseaux de micros. Sa structure est organisee autour d'un administrateur offrant a des modules clients les ressources proposees par les differentes composantes du systeme. Les principaux outils integres au sein de l'environnement de developpement sont un sequenceur automatique de modules, un pre-processeur de compilation, un gestionnaire d'entrees-sorties s'appuyant sur une banque d'ecrans et un systeme de gestion de la base de donnees relationnel. Les applications pouvant etre distribuees sur plusieurs postes, un traitement cooperatif, base sur le partage de services sur le reseau a travers une architecture client-serveur, est implemente au sein de l'environnement, puis au sein des applications developpees. Le fait que les utilisateurs cooperent au moyen de ces applications distribuees fait apparaitre la necessite de rendre coherentes les multiples informations traitees et affichees par les differents postes du systeme. Cette coherence visuelle est assuree grace a un nouveau mode de verrouillage de la base de donnees permettant le rafraichissement immediat des ecrans contenant des donnees mises a jour par d'autres utilisateurs

Dans ce debut de millenaire, les efforts communs des mondes industriel et academique ont permis une premiere version du sequenÇage du genome humain. A l'ouverture de l'un de ces fichiers de sequence, le lecteur accede a un texte de plusieurs millions de caracteres 'a', 't', 'g', ou 'c', chacun symbolisant l'une des quatre bases azotes qui constituent l'adn. Cette succession de lettres met en exergue l'incomprehension que nous avons du langage de l'adn. Afin de mieux apprehender ce langage, des bases de donnees de sequences, d'annotations, d'experiences ont ete montees, de plus plusieurs outils de traitements d'information ont ete ecrits. La premiere partie de cette these s'attache a cette problematique d'integration d'outils bioinformatiques. L'approche adoptee pour l'integration d'outils est de fondre une architecture distribuee au sein meme du moteur de base de donnees. L'autre facette de l'integration concerne l'integration de donnees issues de differentes bases de donnees biologiques. De faÇon plus precise, notre graal est qu'un utilisateur puisse integrer ses donnees personnelles (provenant d'un fichier excel, d'un fichier texte,. . . ) avec les donnees des bases " institutionnelles " telles que celles du ncbi ou de swissprot. Enfin, nous lui proposons un outil d'integration semantique appele " lysa ". Cet outil est un des premiers qui propose a l'utilisateur d'explorer une base de donnees non pas via la structure de la base mais via les donnees contenues. Cette exploration a pour but de permettre a l'utilisateur de retrouver les liens " semantiques " qui existent entre les donnees
In this beginning of millennium, the efforts of the industrial and academic world allowed for a first version of the sequencing of the human genome. By opening one of these files of sequence, the reader reaches a text of several million characters “a”, “t”, “g”, or “c”, each one symbolizing one of the four bases which constitute the dna. This sequence of letters puts forward our misunderstanding of dna. In order better to tackle this language, a lot of databases of dna sequences, annotations, and experiments were built, several tools of treatments of information were written. The first part of this thesis resolves the integration problem of bioinformatic tools. The approach adopted for the integration of tools is to melt a distributed architecture within the basic data engine. The other facet of integration relates to the integration of data resulting from various biological databases. In a more precise way, our goal is that a user integrate his personal data (coming from an excel file, a text file,. . . ) with the data of the “institutional” bases such as those of the ncbi or swissprot. Lastly, we propose a semantic integration tool called “lysa”. This tool proposes not to explore a database through the structure of the base but through the data within. The purpose of this exploration is to make it possible for the user to find the “semantic” links between data

Cette thèse traite plusieurs aspects du traitement de requêtes dans un système relationnel d'intégration de données de type "peer-to-peer". Un tel système permet de partager des ressources hétérogènes et distribuées entre plusieurs sites autonomes et distants. Une resource est une collection de données, ou un programme, que son propriétaire veut partager avec d'autres utilisateurs. Des ressources différentes peuvent avoir des formats différents, p. Ex. , relationnel ou XML : elles seront toutes modéliséees comme des relations. Elles peuvent aussi avoir des capacités de traitement de requêtes très différentes : certaines peuvent évaluer des requêtes, d'autres permettrent uniquement d'accéder à leurs données, tandis que les ressources restreintes permettent d'obtenir des tuples uniquement en fournissant des valeurs pour certains attributs. Cette thèse apporte les contributions suivantes : 1. Modélisation : nous montrons comment utiliser le concept de tables à patterns d'accès pour modéliser des données relationelles, objet, ou XML, ainsi que des programmes. Nous étudions la faisabilité d'une requête SQL sur des tables à patterns d'accès, pour une sémantique de multi-ensemble. 2. Optimisation : nous décrivons l'espace de recherche de l'optimiseur pour des requêtes sur des tables à patterns d'accès. Nous en estimons la taille de manière analytique et experimentale, et décrivons deux algorithmes d'optimisation. 3. Exécution : nous proposons un opérateur BindJoin efficace pour les appels de programmes et les transferts de données volumineuses. Le BindJoin inclut un cache pour éviter des calculs ou des transferts redondants, et peut utiliser la présence des duplicatas pour améliorer son taux de sortie. 4. Translation : nous décrivons une extension de ce système relationnel, lui fournissant une interface utilisateur XML. En particulier, nous proposons une méthode de translation d'une requête XML sur cette interface vers une requête SQL sur les sources de données.

Ces dernières années, les données deviennent incertaines en raison du fleurissement des technologies de pointe qui participent continuellement et de plus en plus dans la production d’une grande quantité de données incertaines. Surtout, que certains nombres d’applications ou l’incertitude est omniprésentes sont distribuées dans la nature, e.g. Des réseaux de capteur distribués, l’extraction de l’information, l’intégration de données, le réseau social, etc. Par conséquent, malgré que ‘incertitudes a été étudier dans la littérature des bases de données centralisé, il reste toujours des défis à relever dans le contexte des bases de données distribuées. Dans ce travail, nous nous concentrons sur le type de données qui est composé d’un ensemble d’attributs descriptifs, qui ne sont ni numériques, ni en soi ordonnés en aucune façon, à savoir des données catégoriques. Nous proposons deux approches pour la gestion de données catégorielles incertaines dans un environnement distribué. Ces approches sont construites sur une technique d’indexation hiérarchique et des algorithmes distribués pour efficacement traiter certain types de requêtes sur des données incertaines dans un environnement distribué Dans la première approche, nous proposons une technique d’indexation distribuée basée sur la structure d’index inversée pour efficacement rechercher des données catégoriques incertaines dans un environnement distribué. En utilisant cette technique d’indexation, nous adressons deux types de requêtes sur les bases de données incertaines distribuées (1) une requête de seuils probabiliste distribuée, où les réponses obtenues satisfont l’exigence de seuil de probabilités (2) une requêtes probabiliste de meilleurs k-réponse, en assurant l’optimisation de transfert du tuples des sites interrogés au site de coordinateur en un temps réduit . Des expériences empiriques sont conduites pour vérifier l’efficacité et l’efficacité de la méthode proposée en termes de coûts de communication et le temps de réponse. La deuxième approche se concentre sur les requêtes Top-k , on propose un algorithme distribué à savoir TDUD. Son but est de trouves les meilleurs k réponses sur des données catégorielles incertaines distribuées en un seul tour seul de communication. Pour aboutir à ce but, nous enrichissons l’index incertain global proposé dans la première approche avec d’autres informations qui résument les indexes locaux afin de minimiser le coût de communication, De plus, en utilisant les moyennes de dispersion de probabilité de chaque site, on peut prévoir le nombre de sites qu’on doit interroger afin d’avoir les meilleurs k réponse, ainsi élaguer les sites qui ne fournis pas de réponse, ce qui engendre un meilleur temps d’exécution et moins de transfert de tuples. Des expériences vastes sont conduites pour vérifier l’efficacité de la méthode proposée en termes de coûts de communication et le temps de réponse. Nous montrons empiriquement que l’algorithme lié est presque optimal, dans lequel, il peut typiquement récupérer les meilleurs k-réponses en communiquant un nombre restreint de tuples dans un seul tour seul
In recent years, data has become uncertain due to the flourishing advanced technologies that participate continuously and increasingly in producing large amounts of incomplete data. Often, many modern applications where uncertainty occurs are distributed in nature, e.g., distributed sensor networks, information extraction, data integration, social network etc. Consequently, even though the data uncertainty has been studied in the past for centralized behavior, it is still a challenging issue to manage uncertainty over the data in situ. In this work, we focus on the type of data records that are composed of a set of descriptive attributes, which are neither numeric nor inherently ordered in any way namely categorical data. We propose two approaches to managing uncertain categorical data over distributed environments. These approaches are built upon a hierarchical indexing technique and a distributed algorithm to efficiently process queries on uncertain data in distributed environment In the first approach, we propose a distributed indexing technique based on inverted index structure for efficiently searching uncertain categorical data over distributed environments. By leveraging this indexing technique, we address two kinds of queries on the distributed uncertain databases (1) a distributed probabilistic thresholds query, where its answers are satisfy the probabilistic threshold requirement (2) a distributed top k-queries, optimizing, the transfer of the tuples from the distributed sources to the coordinator site and the time treatment. Extensive experiments are conducted to verify the effectiveness and efficiency of the proposed method in terms of communication costs and response time. The second approach is focuses on answering top-k queries and proposing a distributed algorithm namely TDUD. Its aim is to efficiently answer top-k queries over distributed uncertain categorical data in single round of communication. For that purpose, we enrich the global uncertain index provided in the first approach with richer summarizing information from the local indexes, and use it to minimize the amount of communication needed to answer a top-k query. Moreover, the approach maintains the mean sum dispersion of the probability distribution on each site which are then merged at the coordinator site. Extensive experiments are conducted to verify the effectiveness and efficiency of the proposed method in terms of communication costs and response time. We show empirically that the related algorithm is near-optimal in that it can typically retrieve the top-k query answers by communicating few k tuples in a single round

Les systèmes de gestion de données distribuées deviennent de plus en plus complexes. Ils interagissent avec des réseaux de dispositifs fixes et/ou mobiles, tels que des smartphones ou des tablettes, dispositifs hétérogènes, autonomes et possédant des limitations physiques. Ces dispositifs exécutent des applications permettant l'interaction des usagers (i.e. jeux virtuels, réseaux sociaux). Ces applications produisent et consomment des données à tout moment voire même en continu. Les caractéristiques de ces systèmes ajoutent des dimensions au problème de l'optimisation de requêtes, telles que la variabilité des objectifs d'optimisation, l'absence d'information sur les données (métadonnées) ou le manque d'une vision globale du système. Les techniques traditionnelles d'optimisation des requêtes n'abordent pas (ou très peu) les systèmes autonomes. Elles se basent sur les métadonnées et font des hypothèses très fortes sur le comportement du système. En plus, la majorité de ces techniques d'optimisation ciblent uniquement l'optimisation du temps d'exécution. La difficulté d'évaluation des requêtes dans les applications modernes incite à revisiter les techniques traditionnelles d'optimisation. Cette thèse fait face aux défis décris précédemment par l'adaptation du paradigme du Raisonnement à partir de cas (CBR pour Case-Based Reasoning) au problème de l'optimisation des requêtes. Cette adaptation, associée à une exploration pseudo-aléatoire de l'espace de solutions fournit un moyen pour optimiser des requêtes dans les contextes possédant très peu voire aucune information sur les données. Cette approche se concentre sur l'optimisation de requêtes en utilisant les cas générés précédemment dans l'évaluation de requêtes similaires. Un cas de requête et composé par : (i) la requête (le problème), (ii) le plan d'exécution (la solution) et (iii) les mesures de ressources utilisés par l'exécution du plan (l'évaluation de la solution). Cette thèse aborde également la façon que le processus CBR interagit avec le processus de génération de plan d'exécution de la requête qui doit permettre d'explorer l'espace des solutions. Ce processus utilise les heuristiques classiques et prennent des décisions de façon aléatoire lorsque les métadonnées viennent à manquer (e.g. pour l'ordre des jointures, la sélection des algorithmes, voire même le choix des protocoles d'acheminement de messages). Ce processus exploite également le CBR pour générer des plans pour des sous-requêtes, accélérant ainsi l'apprentissage de nouveaux cas. Les propositions de cette thèse ont été validées à l'aide du prototype CoBRA développé dans le contexte du projet UBIQUEST
Distributed data systems are becoming increasingly complex. They interconnect devices (e.g. smartphones, tablets, etc.) that are heterogeneous, autonomous, either static or mobile, and with physical limitations. Such devices run applications (e.g. virtual games, social networks, etc.) for the online interaction of users producing / consuming data on demand or continuously. The characteristics of these systems add new dimensions to the query optimization problem, such as multi-optimization criteria, scarce information on data, lack of global system view, among others. Traditional query optimization techniques focus on semi (or not at all) autonomous systems. They rely on information about data and make strong assumptions about the system behavior. Moreover, most of these techniques are centered on the optimization of execution time only. The difficulty for evaluating queries efficiently on nowadays applications motivates this work to revisit traditional query optimization techniques. This thesis faces these challenges by adapting the Case Based Reasoning (CBR) paradigm to query processing, providing a way to optimize queries when there is no prior knowledge of data. It focuses on optimizing queries using cases generated from the evaluation of similar past queries. A query case comprises: (i) the query, (ii) the query plan and (iii) the measures (computational resources consumed) of the query plan. The thesis also concerns the way the CBR process interacts with the query plan generation process. This process uses classical heuristics and makes decisions randomly (e.g. when there are no statistics for join ordering and selection of algorithms, routing protocols). It also (re)uses cases (existing query plans) for similar queries parts, improving the query optimization, and therefore evaluation efficiency. The propositions of this thesis have been validated within the CoBRa optimizer developed in the context of the UBIQUEST project

Depuis une vingtaine d'années, la masse de données générée par la biologie a cru de façon exponentielle. L'accumulation de ces informations a conduit à une hétérogénéité syntaxique et sémantique importante entre les sources. Intégrer ces données est donc devenu un des champs principaux de recherche en bases de données, puisque l'écriture de requêtes complexes joue un rôle important, en médecine prédictive par exemple. Les travaux présentés dans cette thèse se sont orientés autour de deux axes. Le premier axe s'intéresse à la jointure de données de source en source, qui automatise les extractions manuelles habituellement destinées à recouper les données. Cette méthode est basée sur une description des capacités des sources en logique des attributs. Le deuxième axe vise à développer une architecture de médiation BGLAV basée sur le modèle semi-structure, afin d'intégrer les sources de façon simple et flexible, en associant au système le langage XQuery
Over the past twenty years, the volume of data generated by genomics and biology has grown exponentially. Interoperation of publicly available or copyrighted datasources is difficult due to syntactic and semantic heterogeneity between them. Thus, integrating heterogeneous data is nowadays one of the most important field of research in databases, especially in the biological domain, for example for predictive medicine purposes. The work presented in this thesis is organised around two classes of integration problems. The first part of our work deals with joining data sets across several datasources. This method is based on a description of sources capabilities using feature logics. The second part of our work is a contribution to the development of a BGLAV mediation architecture based on semi-structured data, for an effortless and flexible data integration using the XQuery language

Nous nous intéressons aux systèmes d’informations où les participants (clients et fournisseurs) sont souvent autonomes, c. . D. Ils peuvent quitter le système à n’importe quel moment, et ont des intérêts particuliers pour certaines requêtes. Dans ces environnements, l’allocation de requêtes est un défi parce que les participants ont généralement certaines attentes qui ne sont pas seulement liées aux performances du système. Dans ce contexte, l’insatisfaction des participants est un problème car elle peut conduire les participants à quitter le système. Par conséquent, il est très important de satisfaire les intérêts des participants de sorte qu’ils soient satisfaits. Dans cette thèse, nous abordons ce problème et effectuons quatre contributions principales. Primo, nous fournissons un modèle pour caractériser la perception des participants par rapport le système et proposons des mesures qui permettent d’évaluer la qualité des méthodes d’allocation de requêtes. Secundo, nous proposons SbQA : une méthode d’allocation de requêtes qui permet d’équilibrer à la volée les intérêts du client et ceux du fournisseurs en base à leur satisfaction. Tertio, nous proposons SbQA : une version économique de SbQA qui permet de passer à l’échelle en nombre de médiateurs, de participants, et par conséquent, de requêtes traitées. Quarto, nous proposons SbQR : une méthode de réplication de requêtes qui permet de supporter des possibles pannes des participants, tout en préservant la satisfaction des participants
In large-scale distributed information systems, where participants (consumers and providers) are autonomous and have special interests for some queries, query allocation is a challenge. Much work in this context has focused on distributing queries among providers in a way that maximizes overall performance (typically throughput and response time). However, participants usually have certain expectations with respect to the mediator, which are not only performance-related. Such expectations mainly reflect their interests to allocate and perform queries, e. G. Their interests towards: providers (based on reputation for example), quality of service, topics of interests, and relationships with other participants. In this context, because of participants’ autonomy, dissatisfaction is a problem since it may lead participants to leave the mediator. Participant’s satisfaction means that the query allocation method meets its expectations. Thus, besides balancing query load, preserving the participants’ interests so that they are satisfied is also important. In this thesis, we address the query allocation problem in these environments and make the following main contributions. First, we provide a model to characterize the participants’ perception of the system regarding their interests and propose measures to evaluate the quality of query allocation methods. Second, we propose a framework for query allocation, called SbQA, that dynamically trades consumers’ interests for providers’ interests based on their satisfaction. Third, we propose an query allocation approach, called SbQA, that allows a query allocation method (specifically SbQA) to scale up in terms of the numbers of mediators, participants, and hence of performed queries. Fourth, we propose a query replication method, called SbQR, that allows to support participants’ failures when allocating queries while preserving participants’ satisfaction and good system performance. Last, but not least, we analytically and experimentally validate our proposals and demonstrate that they yield high efficiency while satisfying participants

Cette thèse propose une contribution en matière d'analyse de données, dans la perspective de systèmes informatiques distribués non-centralisés, pour le partage de données numériques. De tels systèmes se développent en particulier sur internet, possiblement à large échelle, mais aussi, par exemple, par des réseaux de capteurs. Notre objectif général est d'estimer la distribution de probabilité d'un jeu de données distribuées, à partir d'estimations locales de cette distribution, calculées sur des sous- jeux de données locaux. En d'autres termes, il s'est agi de proposer une technique pour agréger des estimés locaux pour en faire un estimé global. Notre proposition s'appuie sur la forme particulière que doivent prendre toutes les distributions de probabilité manipulées : elles doivent se formuler comme un mélange de lois gaussiennes multivariées. Notre contribution est une solution à la fois décentralisée et statistiquement robuste aux modèles locaux aberrants, pour mener à bien l'agrégation globale, à partir d'agrégations locales de mélanges de lois gaussiennes. Ces agrégations locales ne requièrent un accès qu'aux seuls paramètres des modèles de mélanges, et non aux données originales.