Le volume des données ne cesse de croître. À tel point qu'on parle aujourd'hui de "Big Data". La principale raison se trouve dans les progrès des outils informatique qui ont offert une grande flexibilité pour produire, mais aussi pour stocker des quantités toujours plus grandes. Les méthodes d'analyse de données ont toujours été confrontées à des quantités qui mettent en difficulté les capacités de traitement, ou qui les dépassent. Pour franchir les verrous technologiques associés à ces questions d'analyse, la communauté peut se tourner vers les techniques de calcul distribué. En particulier, l'extraction de motifs, qui est un des problèmes les plus abordés en fouille de données, présente encore souvent de grandes difficultés dans le contexte de la distribution massive et du parallélisme. Dans cette thèse, nous abordons deux sujets majeurs liés à l'extraction de motifs : les motifs fréquents, et les motifs informatifs (i.e., de forte entropie). / Le volume des données ne cesse de croître. À tel point qu'on parle aujourd'hui de "Big Data". La principale raison se trouve dans les progrès des outils informatique qui ont offert une grande flexibilité pour produire, mais aussi pour stocker des quantités toujours plus grandes.à l'extraction de motifs : les motifs fréquents, et les motifs informatifs (i.e., de forte entropie).

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. / Comparative genomics is essentially a form of data mining in large collections of n-ary relations between genomic elements. Increases in the number of sequenced genomes create a stress on comparative genomics that grows, at worse geometrically, for every increase in sequence data. Even modestly-sized labs now routinely obtain several genomes at a time, and like large consortiums expect to be able to perform all-against-all analyses as part of these new multi-genome strategies. In order to address the needs at all levels it is necessary to rethink the algorithmic frameworks and data storage technologies used for comparative genomics.To meet these challenges of scale, in this thesis we develop novel methods based on NoSQL and MapReduce technologies. Using a characterization of the kinds of data used in comparative genomics, and a study of usage patterns for their analysis, we define a practical formalism for genomic Big Data, implement it using the Cassandra NoSQL platform, and evaluate its performance. Furthermore, using two quite different global analyses in comparative genomics, we define two strategies for adapting these applications to the MapReduce paradigm and derive new algorithms. For the first, identifying gene fusion and fission events in phylogenies, we reformulate the problem as a bounded parallel traversal that avoids high-latency graph-based algorithms. For the second, consensus clustering to identify protein families, we define an iterative sampling procedure that quickly converges to the desired global result. For both of these new algorithms, we implement each in the Hadoop MapReduce platform, and evaluate their performance. The performance is competitive and scales much better than existing solutions, but requires particular (and future) effort in devising specific algorithms.

En informatique ubiquitaire, l'observation du monde physique et de son "contexte" (une représentation haut niveau de la situation physique) est essentielle. Il existe de nombreux moyens pour observer le contexte. Typiquement, cela consiste en un traitement en plusieurs étapes commençant par la récupération de données brutes issues de capteurs. Diverses technologies de capteurs sont utilisées pour la récupération d'informations de bas niveau sur les activités physiques en cours. Ces données sont ensuite rassemblées, analysées et traitées ailleurs dans les systèmes d'information afin d'offrir une reconnaissance de contexte. Les applications déployées réagissent alors en fonction du contexte/de la situation détecté(e). Parmis les capteurs utilisés, les tags RFID, une technologie émergente, permettent de créer un lien virtuel direct entre les objets physiques et les systèmes d'information. En plus de stocker des identifiants, ils offrent un espace mémoire générique aux objets auxquels ils sont attachés, offrant de nouvelles possibilités d'architectures en informatique omniprésente. Dans cette thèse, nous proposons une approche originale tirant parti de l'espace mémoire offerts aux objets réels par les tags RFID. Dans notre approche, les objets supportent directement le système d'information. Ce type d'intégration permet de réduire les communications requises par le traitement à distance. Pour ce faire, des données sémantiques sont tout d'abord attachées aux objets afin de les rendre auto-descriptifs. Ainsi, les données pertinentes concernant une entité physique sont directement disponibles pour un traitement local. Les objets peuvent ensuite être liés virtuellement grâce à des structures de données dédiées ou ad hoc et distribuées sur les objets eux-mêmes. Ce faisant, le traitement des données peut se faire de façon directe. Par exemple, certaines propriétés peuvent être vérifiées localement sur un ensemble d'objets. Une relation physique peut être déduite directement de la structure de données, d'où le nom de "structures de données tangibles". Vis-à-vis des approches conventionnelles tirant parti des identifiants, notre approche offrent des avantages en termes de vie privée, de mise à l'échelle, d'autonomie et d'indépendance vis-à-vis des infrastructures. Le défi se situe au niveau de son expressivité limitée à cause du faible espace mémoire disponible sur les tags RFID. Les principes sont validés dans deux prototypes aux applications différentes. Le premier prototype est développé dans le domaine de la gestion de déchets afin d'aider le tri et d'améliorer le recyclage. Le deuxième offre des services supplémentaires, tels qu'une assistance lors du montage et de la vérification d'objets composés de plusieurs parties, grâce aux structures de données distribuées sur les différentes parties. / Pervasive computing or ambient computing aims to integrate information systems into the environment, in a manner as transparent as possible to the users. It allows the information systems to be tightly coupled with the physical activities within the environment. Everyday used objects, along with their environment, are made smarter with the use of embedded computing, sensors etc. and also have the ability to communicate among themselves. In pervasive computing, it is necessary to sense the real physical world and to perceive its “context” ; a high level representation of the physical situation. There are various ways to derive the context. Typically, the approach is a multi-step process which begins with sensing. Various sensing technologies are used to capture low level information of the physical activities, which are then aggregated, analyzed and computed elsewhere in the information systems, to become aware of the context. Deployed applications then react, depending on the context situation. Among sensors, RFID is an important emerging technology which allows a direct digital link between information systems and physical objects. Besides storing identification data, RFID also provides a general purpose storage space on objects, enabling new architectures for pervasive computing. In this thesis, we defend an original approach adopting the later use of RFID i.e. a digital memory integrated to real objects. The approach uses the principle where the objects self-support information systems. This way of integration reduces the need of communication for remote processing. The principle is realized in two ways. First, objects are piggybacked with semantic information, related to itself ; as self-describing objects. Hence, relevant information associated with the physical entities are readily available locally for processing. Second, group of related objects are digitally linked using dedicated or ad-hoc data structure, distributed over the objects. Hence, it would allow direct data processing - like validating some property involving the objects in proximity. This property of physical relation among objects can be interpreted digitally from the data structure ; this justifies the appellation “Tangible Data Structures”. Unlike the conventional method of using identifiers, our approach has arguments on its benefits in terms of privacy, scalability, autonomy and reduced dependency with respect to infrastructure. But its challenge lies in the expressivity due to limited memory space available in the tags. The principles are validated by prototyping in two different application domains. The first application is developed for waste management domain that helps in efficient sorting and better recycling. And the second, provides added services like assistance while assembling and verification for composite objects, using the distributed data structure across the individual pieces.

Ce manuscrit présente certains de mes travaux de recherche en matière de gestion de données, réalisés au sein de l'équipe bases de données STORM du laboratoire Logiciels, Systèmes, Réseaux de l'IMAG. Ils ont été effectués depuis 1995 (et jusqu'à 2003), année de ma prise de fonctions en tant que Maître de Conférences à l'Institut National Polytechnique (INP) de Grenoble, en poste à l'Ecole Nationale Supérieure d'Informatique et de Mathématiques Appliquées de Grenoble(ENSIMAG). Mes travaux concernent des aspects système --- gestion de cache et duplication de données, support transactionnels, parmi d'autres. Ils contribuent d'une part à l'extension des fonctions des SGBD et d'autre part à la conception de services séparés utilisables indépendamment d'un SGBD. Mon point de vue porte sur la diversification du panorama des architectures des systèmes de gestion de données. J'ai d'abord travaillé dans l'introduction de fonctions déductives et actives dans les SGBD pour ensuite m'orienter vers des solutions plus ouvertes, des intergiciels de gestion de données distribuées sur des unités fixes et mobiles.

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.

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.

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.

Dans tous les domaines, le progrès scientifique repose de plus en plus sur la capacité à exploiter des volumes de données toujours plus gigantesques. Alors que leur volume augmente, la gestion de ces données se complexifie. Un point clé est la gestion du cycle de vie des données, c'est à dire les diverses opérations qu'elles subissent entre leur création et leur disparition : transfert, archivage, réplication, suppression, etc. Ces opérations, autrefois simples, deviennent ingérables lorsque le volume des données augmente de manière importante, au vu de l'hétérogénéité des logiciels utilisés d'une part, et de la complexité des infrastructures mises en œuvre d'autre part.Nous présentons Active Data, un méta-modèle, une implémentation et un modèle de programmation qui permet de représenter formellement et graphiquement le cycle de vie de données présentes dans un assemblage de systèmes et d'infrastructures hétérogènes, en exposant naturellement la réplication, la distribution et les différents identifiants des données. Une fois connecté à des applications existantes, Active Data expose aux utilisateurs ou à des programmes l'état d'avancement des données dans leur cycle de vie, en cours d'exécution, tout en gardant leur trace lorsqu'elles passent d'un système à un autre.Le modèle de programmation Active Data permet d'exécuter du code à chaque étape du cycle de vie des données. Les programmes écrits avec Active Data ont à tout moment accès à l'état complet des données, à la fois dans tous les systèmes et dans toutes les infrastructures sur lesquels elles sont distribuées. Nous présentons des évaluations de performance et des exemples d'utilisation qui attestent de l'expressivité du modèle de programmation et de la qualité de l'implémentation. Enfin, nous décrivons l'implémentation d'un outil de Surveillance des données basé sur Active Data pour l'expérience Advanced Photon Source qui permet aux utilisateurs de suivre la progression de leurs données, d'automatiser la plupart des tâches manuelles, d'obtenir des notifications pertinente parmi une masse gigantesque d'événements, ainsi que de détecter et corriger de nombreuses erreurs sans intervention humaine.Ce travail propose des perspectives intéressantes, en particulier dans les domaines de la provenance des données et de l'open data, tout en facilitant la collaboration entre les scientifiques de communautés différentes. / In all domains, scientific progress relies more and more on our ability to exploit ever growing volumes of data. However, as datavolumes increase, their management becomes more difficult. A key point is to deal with the complexity of data life cycle management,i.e. all the operations that happen to data between their creation and there deletion: transfer, archiving, replication, disposal etc.These formerly straightforward operations become intractable when data volume grows dramatically, because of the heterogeneity ofdata management software on the one hand, and the complexity of the infrastructures involved on the other.In this thesis, we introduce Active Data, a meta-model, an implementation and a programming model that allow to represent formally and graphically the life cycle of data distributed in an assemblage of heterogeneous systems and infrastructures, naturally exposing replication, distribution and different data identifiers. Once connected to existing applications, Active Data exposes the progress of data through their life cycle at runtime to users and programs, while keeping their track as it passes from a system to another.The Active Data programming model allows to execute code at each step of the data life cycle. Programs developed with Active Datahave access at any time to the complete state of data in any system and infrastructure it is distributed to.We present micro-benchmarks and usage scenarios that demonstrate the expressivity of the programming model and the implementationquality. Finally, we describe the implementation of a Data Surveillance framework based on Active Data for theAdvanced Photon Source experiment that allows scientists to monitor the progress of their data, automate most manual tasks,get relevant notifications from huge amount of events, and detect and recover from errors without human intervention.This work provides interesting perspectives in data provenance and open data in particular, while facilitating collaboration betweenscientists from different communities.

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. / Nominative medical data exchange is a growing challenge containing numerous technical, legislative or relationship barriers. New advanced technologies, in the particular field of grid computing, offer a new approach to handle medical data exchange. The development of the gLite grid middleware within the EGEE project opened new perspectives in distributed data access and database federation. The main requirements of a medical data exchange system, except the high level of security, come from the way to collect and provide data. The original client-server model of computing has many drawbacks regarding data ownership, updates, control, availability and scalability. The method described in this dissertation uses another philosophy in accessing medical data. Using the grid security layer and a robust user access authentication and control system, we build up a dedicated grid network able to federate distributed medical databases. In this way, data owners keep control over the data they produce.This approach is therefore not totally straightforward, especially for patient identification and medical data linkage which is an open problem even in centralized medical systems. A new method is then proposed to handle these specific issues in a highly distributed environment. The Sentinelle project (RSCA) constitutes the applicative framework of this project in the field of cancer screening in French Auvergne region. The first objective is to allow anatomic pathology reports exchange between laboratories and screening structures compliant with pathologists’ requirements and legal issues. Then, the second goal is to provide a framework for epidemiologists to access high quality medical data for statistical studies and global epidemiology.

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.