La diversification des résultats de recherche (DRR) vise à sélectionner divers documents à partir des résultats de recherche afin de couvrir autant d’intentions que possible. Dans les approches existantes, on suppose que les résultats initiaux sont suffisamment diversifiés et couvrent bien les aspects de la requête. Or, on observe souvent que les résultats initiaux n’arrivent pas à couvrir certains aspects. Dans cette thèse, nous proposons une nouvelle approche de DRR qui consiste à diversifier l’expansion de requête (DER) afin d’avoir une meilleure couverture des aspects. Les termes d’expansion sont sélectionnés à partir d’une ou de plusieurs ressource(s) suivant le principe de pertinence marginale maximale. Dans notre première contribution, nous proposons une méthode pour DER au niveau des termes où la similarité entre les termes est mesurée superficiellement à l’aide des ressources. Quand plusieurs ressources sont utilisées pour DER, elles ont été uniformément combinées dans la littérature, ce qui permet d’ignorer la contribution individuelle de chaque ressource par rapport à la requête. Dans la seconde contribution de cette thèse, nous proposons une nouvelle méthode de pondération de ressources selon la requête. Notre méthode utilise un ensemble de caractéristiques qui sont intégrées à un modèle de régression linéaire, et génère à partir de chaque ressource un nombre de termes d’expansion proportionnellement au poids de cette ressource. Les méthodes proposées pour DER se concentrent sur l’élimination de la redondance entre les termes d’expansion sans se soucier si les termes sélectionnés couvrent effectivement les différents aspects de la requête. Pour pallier à cet inconvénient, nous introduisons dans la troisième contribution de cette thèse une nouvelle méthode pour DER au niveau des aspects. Notre méthode est entraînée de façon supervisée selon le principe que les termes reliés doivent correspondre au même aspect. Cette méthode permet de sélectionner des termes d’expansion à un niveau sémantique latent afin de couvrir autant que possible différents aspects de la requête. De plus, cette méthode autorise l’intégration de plusieurs ressources afin de suggérer des termes d’expansion, et supporte l’intégration de plusieurs contraintes telles que la contrainte de dispersion. Nous évaluons nos méthodes à l’aide des données de ClueWeb09B et de trois collections de requêtes de TRECWeb track et montrons l’utilité de nos approches par rapport aux méthodes existantes. / Search Result Diversification (SRD) aims to select diverse documents from the search results in order to cover as many search intents as possible. For the existing approaches, a prerequisite is that the initial retrieval results contain diverse documents and ensure a good coverage of the query aspects. In this thesis, we investigate a new approach to SRD by diversifying the query, namely diversified query expansion (DQE). Expansion terms are selected either from a single resource or from multiple resources following the Maximal Marginal Relevance principle. In the first contribution, we propose a new term-level DQE method in which word similarity is determined at the surface (term) level based on the resources. When different resources are used for the purpose of DQE, they are combined in a uniform way, thus totally ignoring the contribution differences among resources. In practice the usefulness of a resource greatly changes depending on the query. In the second contribution, we propose a new method of query level resource weighting for DQE. Our method is based on a set of features which are integrated into a linear regression model and generates for a resource a number of expansion candidates that is proportional to the weight of that resource. Existing DQE methods focus on removing the redundancy among selected expansion terms and no attention has been paid on how well the selected expansion terms can indeed cover the query aspects. Consequently, it is not clear how we can cope with the semantic relations between terms. To overcome this drawback, our third contribution in this thesis aims to introduce a novel method for aspect-level DQE which relies on an explicit modeling of query aspects based on embedding. Our method (called latent semantic aspect embedding) is trained in a supervised manner according to the principle that related terms should correspond to the same aspects. This method allows us to select expansion terms at a latent semantic level in order to cover as much as possible the aspects of a given query. In addition, this method also incorporates several different external resources to suggest potential expansion terms, and supports several constraints, such as the sparsity constraint. We evaluate our methods using ClueWeb09B dataset and three query sets from TRECWeb tracks, and show the usefulness of our proposed approaches compared to the state-of-the-art approaches.

Le domaine biomédical est probablement le domaine où il y a les ressources les plus riches. Dans ces ressources, on regroupe les différentes expressions exprimant un concept, et définit des relations entre les concepts. Ces ressources sont construites pour faciliter l’accès aux informations dans le domaine. On pense généralement que ces ressources sont utiles pour la recherche d’information biomédicale. Or, les résultats obtenus jusqu’à présent sont mitigés : dans certaines études, l’utilisation des concepts a pu augmenter la performance de recherche, mais dans d’autres études, on a plutôt observé des baisses de performance. Cependant, ces résultats restent difficilement comparables étant donné qu’ils ont été obtenus sur des collections différentes. Il reste encore une question ouverte si et comment ces ressources peuvent aider à améliorer la recherche d’information biomédicale. Dans ce mémoire, nous comparons les différentes approches basées sur des concepts dans un même cadre, notamment l’approche utilisant les identificateurs de concept comme unité de représentation, et l’approche utilisant des expressions synonymes pour étendre la requête initiale. En comparaison avec l’approche traditionnelle de "sac de mots", nos résultats d’expérimentation montrent que la première approche dégrade toujours la performance, mais la seconde approche peut améliorer la performance. En particulier, en appariant les expressions de concepts comme des syntagmes stricts ou flexibles, certaines méthodes peuvent apporter des améliorations significatives non seulement par rapport à la méthode de "sac de mots" de base, mais aussi par rapport à la méthode de Champ Aléatoire Markov (Markov Random Field) qui est une méthode de l’état de l’art dans le domaine. Ces résultats montrent que quand les concepts sont utilisés de façon appropriée, ils peuvent grandement contribuer à améliorer la performance de recherche d’information biomédicale. Nous avons participé au laboratoire d’évaluation ShARe/CLEF 2014 eHealth. Notre résultat était le meilleur parmi tous les systèmes participants. / Health and biomedical area is probably the area where there are the richest domain resources. In these resources, different expressions are clustered into well defined concepts. They are designed to facilitate public access to the health information and are widely believed to be useful for biomedical information retrieval. However the results of previous works are highly mitigated: in some studies, concepts slightly improve the retrieval performance, while in some others degradations are observed. It is however difficult to compare the results directly due to the fact that they have been performed on different test collections. It is still unclear whether and how medical information retrieval can benefit from these knowledge resources. In this thesis we aim at comparing in the same framework two families of approaches to exploit concepts - using concept IDs as the representation units or using synonymous concept expressions to expand the original query. Compared to a traditional bag-of-words (BOW) baseline, our experiments on test collections show that concept IDs always degrades retrieval effectiveness, whereas the second approach can lead to some improvements. In particular, by matching the concept expressions as either strict or flexible phrases, some methods can lead to significant improvement over the BOW baseline and even over MRF model on most query sets. This study shows experimentally that when concepts are used in a suitable way, it can help improve the effectiveness of medical information retrieval. We participated at the ShARe/CLEF 2014 eHealth Evaluation Lab. Our result was the best among all the participating systems.

Nous étudions les réponses proches à des requêtes OLAP sur les entrepôts de données. Nous considérons les réponses relatives aux requêtes OLAP sur un schéma, comme les distributions avec la distance L1 et rapprocher les réponses sans stocker totalement l'entrepôt de données. Nous présentons d'abord trois méthodes spécifiques: l'échantillonnage uniforme, l'échantillonnage basé sur la mesure et le modèle statistique. Nous introduisons également une distance d'édition entre les entrepôts de données avec des opérations d'édition adaptées aux entrepôts de données. Puis, dans l'échange de données OLAP, nous étudions comment échantillonner chaque source et combiner les échantillons pour rapprocher toutes requêtes OLAP. Nous examinons ensuite un contexte streaming, où un entrepôt de données est construit par les flux de différentes sources. Nous montrons une borne inférieure de la taille de la mémoire nécessaire aux requêtes approximatives. Dans ce cas, nous avons les réponses pour les requêtes OLAP avec une mémoire finie. Nous décrivons également une méthode pour découvrir les dépendances statistique, une nouvelle notion que nous introduisons. Nous recherchons ces dépendances en basant sur l'arbre de décision. Nous appliquons la méthode à deux entrepôts de données. Le premier simule les données de capteurs, qui fournissent des paramètres météorologiques au fil du temps et de l'emplacement à partir de différentes sources. Le deuxième est la collecte de RSS à partir des sites web sur Internet. / We study the approximate answers to OLAP queries on data warehouses. We consider the relative answers to OLAP queries on a schema, as distributions with the L1 distance and approximate the answers without storing the entire data warehouse. We first introduce three specific methods: the uniform sampling, the measure-based sampling and the statistical model. We introduce also an edit distance between data warehouses with edit operations adapted for data warehouses. Then, in the OLAP data exchange, we study how to sample each source and combine the samples to approximate any OLAP query. We next consider a streaming context, where a data warehouse is built by streams of different sources. We show a lower bound on the size of the memory necessary to approximate queries. In this case, we approximate OLAP queries with a finite memory. We describe also a method to discover the statistical dependencies, a new notion we introduce. We are looking for them based on the decision tree. We apply the method to two data warehouses. The first one simulates the data of sensors, which provide weather parameters over time and location from different sources. The second one is the collection of RSS from the web sites on Internet.

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

La dernière décennie a montré un intérêt croissant pour les bâtiments intelligents. Les bâtiments traditionnels sont les principaux consommateurs d’une partie importante des ressources énergétiques, d'où le besoin de bâtiments intelligents a alors émergé. Ces nouveaux bâtiments doivent être conçus selon des normes de construction durables pour consommer moins. Ces bâtiments intelligents sont devenus l’un des principaux domaines d’application des environnements pervasifs. En effet, une infrastructure basique de construction de bâtiment intelligent se compose notamment d’un ensemble de capteurs sans fil. Les capteurs basiques permettent l’acquisition, la transmission et la réception de données. La consommation d’énergie élevée de l’ensemble de ces appareils est un des problèmes les plus difficiles et fait donc l’objet d’études dans ce domaine de la recherche. Les capteurs sont autonomes en termes d’énergie. Etant donné que la consommation d’énergie a un fort impact sur la durée de vie du service, il existe plusieurs approches dans la littérature. Cependant, les approches existantes sont souvent adaptées à une seule application de surveillance et reposent sur des configurations statiques pour les capteurs. Dans cette thèse, nous contribuons à la définition d’une architecture de surveillance déclaratif durable par l’optimisation énergétique des interactions entre requêtes applicative orientées service et réseau de capteurs sans fil. Nous avons choisi le bâtiment intelligent comme cas d’application et nous étudions donc un système de surveillance d’un bâtiment intelligent. Du point de vue logiciel, un système de surveillance peut être défini comme un ensemble d’applications qui exploitent les mesures des capteurs en temps réel. Ces applications sont exprimées dans un langage déclaratif sous la forme de requêtes continues sur les flux de données des capteurs. Par conséquent, un système de multi-applications nécessite la gestion de plusieurs demandes de flux de données suivant différentes fréquences d’acq/tx de données pour le même capteur sans fil, avec des exigences dynamiques requises par les applications. Comme une configuration statique ne peut pas optimiser la consommation d’énergie du système, nous proposons une approche intitulée Smart-Service Stream-oriented Sensor Management (3SoSM) afin d’optimiser les interactions entre les exigences des applications et l’environnement des capteurs sans fil, en temps réel. 3SoSM offre une configuration dynamique des capteurs pour réduire la consommation d’énergie tout en satisfaisant les exigences des applications en temps réel. Nous avons conduit un ensemble d’expérimentations effectuées avec un simulateur de réseau de capteurs sans fil qui ont permis de valider notre approche quant à l’optimisation de la consommation d’énergie des capteurs, et donc l’augmentation de la durée de vie de ces capteurs, en réduisant notamment les communications non nécessaires. / Recent researches and analysis reports declare that high energy consumption of buildings is major problem in developed countries. As a result, they show concretely that building energy management systems (BEMS) and deployed wireless sensor network environments are important for energy efficiency of building operations. In the literature, existing smart building management systems focus on energy consumption of the building, hardware deployed inside/outside of the building and network communication issues. They adopt static configurations for wireless sensor devices and proposed models are fitted to a single application. In this study, we propose a sustainable declarative monitoring architecture that focus on the energy optimisation of interactions between application service oriented queries and wireless sensor devices. We consider the monitoring system as a set of applications that exploit sensor measures in real time such as HVAC automation and control systems, real time supervision, security. These applications can be configured dynamically by the users or by the supervisor. In our approach, we take a data point of view: applications are declaratively expressed as a set of continuous queries on the sensor data stream. To achieve our objective of energy aware optimization of the monitoring architecture, we formalize sensor device configuration and fit data acquisition and data transmission to actual applications requirements. We present a complete monitoring architecture and an algorithm that handles dynamic sensor configuration. We introduce a platform that covers physical and also simulated wireless sensor devices.

Le volume de données disponibles dans les systèmes d'information est de plus en plus important et pour autant, nous n'avons jamais autant essayer d'interconnecter cette information pour en extraire de la connaissance sans véritable succès généralisable. L'origine du problème est multiple. Tout d'abord, l'information est représentée dans des structures différentes. Ensuite, les vocabulaires utilisés pour exprimer les données sont hétérogènes. Enfin, la qualité de l'information est souvent trop mauvaise pour utiliser une information et en déduire des connaissances. Ce diagnostic est d'autant plus vrai dans le cadre du partage d'information dans le domaine biomédical où il reste difficile de s'entendre sur des représentations (structures et vocabulaires) pivots d'un domaine de la médecine, et donc où il apparaît difficile de résoudre le problème du partage d'information par l'imposition de standard de codage et de structuration de l'information. Plus récemment, l'introduction de la sémantique dans des processus de partage d'information, nous offre la possibilité de mettre en oeuvre des représentations pivots indépendantes de la structuration ou du nommage d'une donnée. Cette thèse s'inscrit dans cette problématique de partage de données biomédicales dans le cadre de l'évaluation de l'évolution de la résistance des bactéries aux antibiotiques en Europe. L'hypothèse générale de travail que nous proposons est la suivante: comment partager de l'information biomédicale de manière non ambigüe, en temps réel, et à la demande en Europe. Cette hypothèse pose diverses problématiques que nous abordons dans ce mémoire. La problématique de la qualité des données. Celle de la représentation des données à travers leur structure, leur vocabulaire et de leur sémantique. Nous aborderons aussi les problèmes d'alignement de données aux ontologies de domaine et de la fédération de données aidée d'ontologie. Enfin, nous présenterons un système d'interopérabilité sémantique basé sur des règles qui aborde le problème d'alignement sémantique de systèmes hétérogènes appliqué à notre domaine. Nous discuterons finalement de l'apport de la sémantique pour le partage d'information et des limites des outils et méthodes actuels.

Les formats RSS et Atom sont moins connus du grand public que le format HTML pour la publication d'informations sur le Web. Néanmoins les flux RSS sont présents sur tous les sites qui veulent publier des flux d'informations évolutives et dynamiques. Ainsi, les sites d'actualités publient des milliers de fils RSS/Atom, souvent organisés dans différentes thématiques (politique, économie, sports, société...). Chaque blog possède son propre flux RSS, et des sites de micro-blogage comme Twitter ou de réseaux sociaux comme Facebook publient les messages d'utilisateurs sous forme de flux RSS. Ces immenses quantités de sources de données continues sont accessibles à travers des agrégateurs de flux comme Google Reader, des lecteurs de messages comme Firefox, Thunderbird, mais également à travers des applications mash-up comme Yahoo! pipes, Netvibes ou Google News. Dans cette thèse, nous présentons ROSES -Really Open Simple and Efficient Syndication-, un modèle de données et un langage de requêtes continues pour des flux RSS/Atom. ROSES permet aux utilisateurs de créer des nouveaux flux personnalisés à partir des flux existants sur le web à travers un simple langage de requêtes déclaratif. ROSES est aussi un système capable de gérer et traiter des milliers de requêtes d'agrégation ROSES en parallèle et un défi principal traité dans cette thèse est le passage à l'échelle par rapport au nombre de requêtes. En particulier, on propose une nouvelle approche d'optimisation multi-requête fondée sur la factorisation des filtres similaires. Nous proposons deux algorithmes de factorisation: (i) STA, une adaptation d'un algorithme d'approximation pour calculer des arbres de Steiner minimaux [CCC+98], et (ii) VCA, un algorithme glouton qui améliore le coût CPU d'optimisation du précédant. Nous avons validé notre approche d'optimisation avec un important nombre de tests sur des données réelles.

De nombreuses recherches empiriques montrent que la façon dont les locuteurs et locutrices parlent peut varier en fonction du contexte, des dispositions mentales des locuteurs·trices, du type de la relation interpersonnelle (horizontale ou verticale) qu’entretiennent interlocuteurs·trices, de l’environnement culturel, etc. Mais en continuant d’exposer le grand public à des données incomplètes s’appuyant sur des stéréotypes de genres, les médias continuent d’entretenir l’idée, que les hommes et les femmes parlent différemment ; il y a donc une discordance entre la réalité des pratiques langagières et la représentation que les individus s’en font (Freed 2014). Notre étude du masculin et du féminin dans quatre séries de BDs de science-fiction franco-belges a pour but de vérifier si les héros et héroïnes de ces quatre séries sont représenté·e·s selon des stéréotypes de genre. Concernant le physique, comment héroïnes et héros sont-ils représentés ? Y a-t-il une frontière nette entre représentation de la féminité et de la masculinité ? Et, concernant la requête du type demande de faire, les héroïnes et héros formulent-ils différemment leurs requêtes ? Ces trois questions nous permettent de savoir si le lectorat des quatre séries de BDs analysées est exposé aux stéréotypes de genre. Les seuls stéréotypes de genre exposés s’appliquent aux corps et au vêtements (sauf dans une série). Pour le reste, attitudes, comportements, façons de parler, les stéréotypes sont globalement évacués. Il en ressort que la féminité et la masculinité s’inscrivent sur un continuum du genre. Pour ce qui est de la requête, dans deux séries les héroïnes se distinguent de leurs partenaires masculins du point de vue du fond de la requête (c.-à-d. de son objet), mais pas du point de vue de la forme et ce schéma est un corrélat de l’absence de leadership des partenaires masculins et révèle l’état mental de ces derniers ou la crainte de la prise de risque. Nous parlons alors de schémas de requêtes différenciées (et non genrées). Dans la troisième BD, le schéma des requêtes est genré dans la forme (et non dans le fond) dans la mesure où l’héroïne emploie davantage de requêtes indirectes que le héros, mais ce schéma n’est aucunement corrélé au manque de pouvoir de l’héroïne, qui, bien au contraire, jouit d’un grand pouvoir symbolique (probablement raison pour laquelle, le fond de ses requêtes est identique à celui du héros). Dans la quatrième série, celle où la représentation corporelle des hommes et des femmes est globalement similaire, on ne trouve ni schéma de requête genré ni schéma de requête différencié. La variation stylistique qui caractérise la nature directe ou indirecte des requêtes des personnages fictifs étudiés est fonction de l’urgence de la situation (contextuel), de leur expertise ou pouvoir (relation verticale) ou de leur état mental. Ils et elles privilégient la sauvegarde des faces à mesure que le caractère anxiogène du contexte de l’énonciation s’éloigne ou s’ils·elles entretiennent une relation interpersonnelle horizontale avec leur(s) allocutaire(s). Nos résultats sur la requête sont ainsi conformes avec les recherches empiriques : dans un cas ils illustrent la manifestation d’un des aspects du style langagier féminin et dans les trois autres, ils invalident l’existence de stéréotypes langagiers féminins dans le sens ou ces derniers sont dépassés par le contexte situationnel ou la relation interpersonnelle. / A significant number of case studies have shown that the way individuals speak, be they men or women, varies according to variables as the kind of relationship (vertical or horizontal) existing between interlocutors, mental state of speakers, context, culture and so forth. However, as Freed (2014) states, the mass media keep exposing their large audience to incomplete or erroneous data and stereotypes concerning the way men and women speak. Thus, individuals keep thinking that there is such a thing as «women and men speak differently». To put it in a nutshell, the way men and women speak is at odds with what occurs in reality. Our study about masculinity and femininity within four series of Franco-Belgian science-fictional comics aims at verifying how masculinity and femininity are represented in the four heroines and their male counterpart or partner(s). On the ground of non-linguistics representation, how are the female and male characters represented ? And does a clear line delineate masculinity and femininity ? Second, on the ground of linguistics, do the heroines phrase their requests differently than do the hero or male partner(s) ? In other words, are female characters more enclined than male characters to formulate indirect requests ? These three questions lead us to determine if the lectorate is exposed to gendered stereotypes. Our results show that stereotypes are only confined into the bodies (and at a certain point, the clothing). Other than that, attitudes and the way the characters speak are not bound to gendered stereotypes. Concerning the analysis of the requests, in two of our series, there is a difference between the requests made by the heroine and the ones made by the male in terms of the content of the requests. Therefore, we say that their request schema is not gendered but differentiated. That is to say, the content of the requests made by the males is correlated to their lack of power and reveal either their mental states or their being concerned with risk taking. In the third comic, we observe indeed a gendered schema of requests between the heroine and her male counterpart, the latter phrasing more direct requests. Conversely to the two previously mentioned comics, here, the stylish gendered request schema is not correlated with the heroine lack of power, that’s probably why both characters’ content of requests is the same. In the fourth series, which is the one where men and women are almost physically alike, we neither observe differentiated pattern of request nor gendered pattern of requests. Globally, in the four series, male and female characters articulate direct requests according to the emergency (contextual), their expertise or power (vertical relationship with interlocutor) or their mental state ; moreover, they indulge themselves into face-saving speech strategies as the emergency diminishes or disappears or if they have an horizontal type of relationship with their interlocutors. Thus, the variation is either stylistic or due to interpersonal relationship. Our results are not at odds with the empirical data : in one case, they illustrate the display of one aspect of the feminine language stereotype, and in the three other ones they invalidate the existence of stereotyped language styles in the sense that the stereotypes are overcome by the context or the interpersonal relationship.

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

Avec l'avènement du « big data », de nombreuses répercussions ont eu lieu dans tous les domaines de la technologie de l'information, préconisant des solutions innovantes remportant le meilleur compromis entre coûts et précision. En théorie des graphes, où les graphes constituent un support de modélisation puissant qui permet de formaliser des problèmes allant des plus simples aux plus complexes, la recherche pour des problèmes NP-complet ou NP-difficils se tourne plutôt vers des solutions approchées, mettant ainsi en avant les algorithmes d'approximations et les heuristiques alors que les solutions exactes deviennent extrêmement coûteuses et impossible d'utilisation.Nous abordons dans cette thèse deux problématiques principales: dans un premier temps, le problème du partitionnement des graphes est abordé d'une perspective « big data », où les graphes massifs sont partitionnés en streaming. Nous étudions et proposons plusieurs modèles de partitionnement en streaming et nous évaluons leurs performances autant sur le plan théorique qu'empirique. Dans un second temps, nous nous intéressons au requêtage des graphes distribués/partitionnés. Dans ce cadre, nous étudions la problématique de la « recherche agrégative dans les graphes » qui a pour but de répondre à des requêtes interrogeant plusieurs fragments de graphes et qui se charge de la reconstruction de la réponse finale tel que l'on obtient un « matching approché » avec la requête initiale / With the advent of the "big data", many repercussions have taken place in all fields of information technology, advocating innovative solutions with the best compromise between cost and accuracy. In graph theory, where graphs provide a powerful modeling support for formalizing problems ranging from the simplest to the most complex, the search for NP-complete or NP-difficult problems is rather directed towards approximate solutions, thus Forward approximation algorithms and heuristics while exact solutions become extremely expensive and impossible to use. In this thesis we discuss two main problems: first, the problem of partitioning graphs is approached from a perspective big data, where massive graphs are partitioned in streaming. We study and propose several models of streaming partitioning and we evaluate their performances both theoretically and empirically. In a second step, we are interested in querying distributed / partitioned graphs. In this context, we study the problem of aggregative search in graphs, which aims to answer queries that interrogate several fragments of graphs and which is responsible for reconstructing the final response such that a Matching approached with the initial query