Ces dernières années ont connu un regain d'intérêt pour l'utilisation des graphes comme moyen fiable de représentation et de modélisation des données, et ce, dans divers domaines de l'informatique. En particulier, pour les grandes masses de données, les graphes apparaissent comme une alternative prometteuse aux bases de données relationnelles. Plus particulièrement, le recherche de sous-graphes s'avère être une tâche cruciale pour explorer ces grands jeux de données. Dans cette thèse, nous étudions deux problématiques principales. Dans un premier temps, nous abordons le problème de la détection de motifs dans les grands graphes. Ce problème vise à rechercher les k-meilleures correspondances (top-k) d'un graphe motif dans un graphe de données. Pour cette problématique, nous introduisons un nouveau modèle de détection de motifs de graphe nommé la Simulation Relaxée de Graphe (RGS), qui permet d’identifier des correspondances de graphes avec un certain écart (structurel) et ainsi éviter le problème de réponse vide. Ensuite, nous formalisons et étudions le problème de la recherche des k-meilleures réponses suivant deux critères, la pertinence (la meilleure similarité entre le motif et les réponses) et la diversité (la dissimilarité entre les réponses). Nous considérons également le problème des k-meilleures correspondances diversifiées et nous proposons une fonction de diversification pour équilibrer la pertinence et la diversité. En outre, nous développons des algorithmes efficaces basés sur des stratégies d’optimisation en respectant le modèle proposé. Notre approche est efficiente en terme de temps d’exécution et flexible en terme d'applicabilité. L’analyse de la complexité des algorithmes et les expérimentations menées sur des jeux de données réelles montrent l’efficacité des approches proposées. Dans un second temps, nous abordons le problème de recherche agrégative dans des documents XML. Pour un arbre requête, l'objectif est de trouver des motifs correspondants dans un ou plusieurs documents XML et de les agréger dans un seul agrégat. Dans un premier temps nous présentons la motivation derrière ce paradigme de recherche agrégative et nous expliquons les gains potentiels par rapport aux méthodes classiques de requêtage. Ensuite nous proposons une nouvelle approche qui a pour but de construire, dans la mesure du possible, une réponse cohérente et plus complète en agrégeant plusieurs résultats provenant de plusieurs sources de données. Les expérimentations réalisées sur plusieurs ensembles de données réelles montrent l’efficacité de cette approche en termes de pertinence et de qualité de résultat. / Recent years have witnessed a growing renewed interest in the use of graphs as a reliable means for representing and modeling data. Thereby, graphs enable to ensure efficiency in various fields of computer science, especially for massive data where graphs arise as a promising alternative to relational databases for big data modeling. In this regard, querying data graph proves to be a crucial task to explore the knowledge in these datasets. In this dissertation, we investigate two main problems. In the first part we address the problem of detecting patterns in larger graphs, called the top-k graph pattern matching problem. We introduce a new graph pattern matching model named Relaxed Graph Simulation (RGS), to identify significant matches and to avoid the empty-set answer problem. We formalize and study the top-k matching problem based on two classes of functions, relevance and diversity, for ranking the matches according to the RGS model. We also consider the diversified top-k matching problem, and we propose a diversification function to balance relevance and diversity. Moreover, we provide efficient algorithms based on optimization strategies to compute the top-k and the diversified top-k matches according to the proposed model. The proposed approach is optimal in terms of search time and flexible in terms of applicability. The analyze of the time complexity of the proposed algorithms and the extensive experiments on real-life datasets demonstrate both the effectiveness and the efficiency of these approaches. In the second part, we tackle the problem of graph querying using aggregated search paradigm. We consider this problem for particular types of graphs that are trees, and we deal with the query processing in XML documents. Firstly, we give the motivation behind the use of such a paradigm, and we explain the potential benefits compared to traditional querying approaches. Furthermore, we propose a new method for aggregated tree search, based on approximate tree matching algorithm on several tree fragments, that aims to build, the extent possible, a coherent and complete answer by combining several results. The proposed solutions are shown to be efficient in terms of relevance and quality on different real-life datasets

No description available.

No / A two-tiered architecture with resource-rich master nodes at the upper tier and resource-poor sensor nodes at the lower tier is expected to be adopted in large scale sensor networks. In a hostile environment, adversaries are more motivated to compromise the master nodes to break the authenticity and completeness of query results, whereas it is lack of light and secure query processing protocol in tiered sensor networks at present. In this paper, we study the problem of verifiable fine-grained top- queries in two-tiered sensor networks, and propose a novel verification scheme, which is named Verification Scheme for Fine-grained Top- Queries (VSFTQ). To make top- query results verifiable, VSFTQ establishes relationships among data items of each sensor node using their orders, which are encrypted together with the scores of the data items and the interested time epoch number using distinct symmetric keys kept by each sensor node and the network owner. Both theoretical analysis and simulation results show that VSFTQ can not only ensure high probability of detecting forged and/or incomplete query results, but also significantly decrease the amount of verification information when compared with existing schemes.

De nos jours, nous assistons à l’émigration du Web de données vers le Web orienté services. L’amélioration des capacités et fonctionnalités des moteurs actuels de recherche sur le Web, par des techniques efficaces de recherche et de sélection de services, devient de plus en plus importante. Dans cette thèse, dans un premier temps, nous proposons un cadre de composition de services Web en tenant compte des préférences utilisateurs. Le modèle fondé sur la théorie des ensembles flous est utilisé pour représenter les préférences. L’approche proposée est basée sur une version étendue du principe d’optimalité de Pareto. Ainsi, la notion des top-k compositions est introduite pour répondre à des requêtes utilisateurs de nature complexe. Afin d’améliorer la qualité de l’ensemble des compositions retournées, un second filtre est appliqué à cet ensemble en utilisant le critère de diversité. Dans un second temps, nous avons considéré le problème de la sélection des services Web en présence de préférences émanant de plusieurs utilisateurs. Une nouvelle variante, appelée Skyline de services à majorité, du Skyline de services traditionnel est défini. Ce qui permet aux utilisateurs de prendre une décision « démocratique » conduisant aux services les plus appropriés. Un autre type de Skyline de services est également discuté dans cette thèse. Il s’agit d’un Skyline de Services de nature graduelle et se fonde sur une relation de dominance floue. Comme résultat, les services Web présentant un meilleur compromis entre les paramètres QoS sont retenus, alors que les services Web ayant un mauvais compromis entre les QoS sont exclus. Finalement, nous avons aussi absorbé le cas où les QoS décrivant les services Web sont entachés d’incertitude. La théorie des possibilités est utilisée comme modèle de l’incertain. Ainsi, un Skyline de Services possibilité est proposé pour permettre à l’utilisateur de sélectionner les services Web désirés en présence de QoS incertains. De riches expérimentations ont été conduites afin d’évaluer et de valider toutes les approches proposées dans cette thèse / As we move from a Web of data to a Web of services, enhancing the capabilities of the current Web search engines with effective and efficient techniques for Web services retrieval and selection becomes an important issue. In this dissertation, we present a framework that identifies the top-k Web service compositions according to the user fuzzy preferences based on a fuzzification of the Pareto dominance relationship. We also provide a method to improve the diversity of the top-k compositions. An efficient algorithm is proposed for each method. We evaluate our approach through a set of thorough experiments. After that, we consider the problem of Web service selection under multiple users preferences. We introduce a novel concept called majority service skyline for this problem based on the majority rule. This allows users to make a “democratic” decision on which Web services are the most appropriate. We develop a suitable algorithm for computing the majority service skyline. We conduct a set of thorough experiments to evaluate the effectiveness of the majority service skyline and the efficiency of our algorithm. We then propose the notion of α-dominant service skyline based on a fuzzification of Pareto dominance relationship, which allows the inclusion of Web services with a good compromise between QoS parameters, and the exclusion ofWeb services with a bad compromise between QoS parameters. We develop an efficient algorithm based on R-Tree index structure for computing efficiently the α-dominant service skyline. We evaluate the effectiveness of the α-dominant service skyline and the efficiency of the algorithm through a set of experiments. Finally, we consider the uncertainty of the QoS delivered by Web services. We model each uncertain QoS attribute using a possibility distribution, and we introduce the notion of pos-dominant service skyline and the notion of nec-dominant service skyline that facilitates users to select their desired Web services with the presence of uncertainty in their QoS. We then developappropriate algorithms to efficiently compute both the pos-dominant service skyline and nec-dominant service skyline. We conduct extensive sets of experiments to evaluate the proposed service skyline extensions and algorithms

Η ανάπτυξη των peer-to-peer βάσεων δεδομένων και η δυναμική εισαγωγή των συστημάτων αποθήκευσης σε νέφη υπολογιστών (cloudstores) ως τα κυρίαρχα μεγάλης κλίμακας συστήματα διαχείρισης δεδομένων, έχουν οδηγήσει τους ερευνητές να εξετάσουν το πρόβλημα της υποστήριξης πολύπλοκων ερωτημάτων με ένα πλήρως αποκεντρωμένο τρόπο. Περίπλοκα ερωτήματα επιλογής (select), συνένωσης join, καθώς και βαθμολογημένα ερωτήματα έχουν κεντρίσει το ενδιαφέρον της κοινότητας διαχείρισης δεδομένων. Ανάμεσα στις τάξεις των ερωτημάτων αυτών είναι το κεντρικής σημασίας top-k join. To κατανεμημένο top-k join, δεν έχει μελετηθεί επαρκώς, αν και συναντάται πολύ συχνά σε πραγματικό φόρτο εργασίας σε πολλά εμπορικά και άλλα συστήματα βάσεων δεδομένων. Με την εργασία αυτή αντιμετωπίζουμε τέτοιου είδους ερωτήματα πάνω σε δεδομένα που είναι κατανεμημένα σε ένα μεγάλου κλίμακας δίκτυο. Οι συνεισφορές μας με αυτήν την εργασία περιλαμβάνουν: (α) ένα νέο κατανεμημένο ευρετήριο, που επιτρέπει την πρόσβαση σε πλειάδες με τυχαίο και διατεταγμένο τρόπο, (β) ένα σύνολο αλγόριθμων για βαθμολογημένα ερωτημάτατα συνένωσης join. Οι αλγόριθμοί μας στηρίζονται στην προσαρμογή γνωστών αλγοριθμών κατωφλίου για βαθμολογημένο join σε κατανεμημένο περιβάλλον, (γ) μία νέα χρήση των Bloom φίλτρων και ιστογραμμάτων για την περαιτέρω μείωση του εύρους ζώνης που καταναλώνουν οι παραπάνω αλγόριθμοι, καθώς και απόδειξη για το ότι οι αλγόριθμοί μας που βασίζονται σε φίλτρα Bloom και ιστογράμματα παράγουν το σωστό top-k αποτέλεσμα, (δ) μια σε βάθος συζήτηση του σχεδιασμού των αλγορίθμων μας και θεμάτων που συνδέονται με τις επιδόσεις και τα trade-offs. Επιπλέον διερευνούμε την αποτελεσματικότητα και την ποιότητα των προτεινόμενων λύσεων μέσα από μία αναλυτική πειραματική αξιολόγηση, δείχνοντας τις περιπτώσεις που ο κάθε αλγόριθμός μας είναι κατάλληλος σε μαζικώς κατανεμημένα και αποκεντρωμένα περιβάλλοντα, ενώ τονίζουμε τα trade-offs που προκύπτουν. / The advent of peer-to-peer databases and the recent rise of cloudstores as key large-scale data management paradigms, have led researchers to look into the problem of supporting complex queries in a fully decentralized manner. Among the classes of queries considered in related centralized work, there is one that stands out as largely overlooked in widely distributed settings, albeit very common in real-world workloads: top-k joins. With this work we tackle such queries over data distributed across an internet-scale network. Our contributions include: (a) a novel distributed indexing scheme, allowing access to tuples in both a random and an ordered manner; (b) a set of query processing algorithms based on a novel adaptation of rank-join and threshold algorithms, appropriate for use in a distributed environment; (c) a novel use of Bloom Filters and histograms to further reduce the bandwidth consumption of the above algorithms; a proof that ensures that our algorithms based on Bloom filters and histograms produce the correct top-k results; and (d) an in-depth discussion of the design space and related performance trade-offs. We further investigate the efficiency and quality of the proposed solutions through an elaborate experimental evaluation, showcasing their appropriateness for widely-distributed and massively decentralized environments and highlighting related trade-offs.

Dans cette thèse, nous nous intéressons à l'évaluation efficace de requêtes top-k continues sur des flux d'informations textuelles avec des feedbacks utilisateurs. La première contribution est une généralisation des modèles de requêtes top-k continues proposés dans l'état de l'art. Cette généralisation est fondée sur une famille des scores non-homogènes définis comme une combinaison linéaire de scores d'importance de l'information (indépendants des requêtes) et de scores de pertinence du contenu avec une décroissance continue de score reflétant la fraîcheur de l'information. La deuxième contribution est la définition et la mise en ¿uvre de structures de données en mémoire pour l'indexation et l'évaluation de cette nouvelle famille de requêtes top-k continues. Nos expériences montrent que notre solution est évolutive et, limitées aux fonctions homogènes, surpasse les performances d'autres solutions. Dans la deuxième partie de cette thèse, nous considérons le problème de l'intégration des signaux de feedback à notre famille de scores non-homogènes. Nous proposons un nouveau cadre général pour l'évaluation de ces requêtes du "web en temps réel" (real-time web queries) avec un ensemble d'algorithmes minimisant le coût d'évaluation d'un signal de feedback utilisateur dynamique sur un item d'information. Enfin, nous présentons MeowsReader, notre prototype de recommandation d'actualités qui intègre l'ensemble des résultats obtenus et illustre comment une classe générale de requêtes continues top-k propose une abstraction appropriée pour la modélisation et le filtrage continu d'information sur le web "temps-réel". / In this thesis, we are interested in efficient evaluation techniques of continuous top-k queries over text and feedback streams featuring generalized scoring functions which capture dynamic ranking aspects. As a first contribution, we generalize state of the art continuous top-k query models, by introducing a general family of non-homogeneous scoring functions combining query-independent item importance with query-dependent content relevance and continuous score decay reflecting information freshness. Our second contribution consists in the definition and implementation of efficient in-memory data structures for indexing and evaluating this new family of continuous top-k queries. Our experiments show that our solution is scalable and outperforms other existing state of the art solutions, when restricted to homogeneous functions. Going a step further, in the second part of this thesis we consider the problem of incorporating dynamic feedback signals to the original scoring function and propose a new general real-time query evaluation framework with a family of new algorithms for efficiently processing continuous top-k queries with dynamic feedback scores in a real-time web context. Finally, putting together the outcomes of these works, we present MeowsReader, a real-time news ranking and filtering prototype which illustrates how a general class of continuous top-k queries offers a suitable abstraction for modelling and implementing continuous online information filtering applications combining keyword search and real-time web activity.

The sheer volume as well as the schema complexity of today’s graph databases impede the users in formulating queries against these databases and often cause queries to “fail” by delivering empty answers. To support users in such situations, the concept of differential queries can be used to bridge the gap between an unexpected result (e.g. an empty result set) and the query intention of users. These queries deliver missing parts of a query graph and, therefore, work with such scenarios that require users to specify a query graph. Based on the discovered information about a missing query subgraph, users may understand which vertices and edges are the reasons for queries that unexpectedly return empty answers, and thus can reformulate the queries if needed. A study showed that the result sets of differential queries are often too large to be manually introspected by users and thus a reduction of the number of results and their ranking is required. To address these issues, we extend the concept of differential queries and introduce top-k differential queries that calculate the ranking based on users’ preferences and therefore significantly support the users’ understanding of query database management systems. The idea consists of assigning relevance weights to vertices or edges of a query graph by users that steer the graph search and are used in the scoring function for top-k differential results. Along with the novel concept of the top-k differential queries, we further propose a strategy for propagating relevance weights and we model the search along the most relevant paths.

La théorie des fonctions des croyances offre des outils puissants pour modéliser et traiter les informations imparfaites. En effet, cette théorie peut représenter l'incertitude,l'imprécision et l'ignorance. Dans ce contexte, les données sont stockées dans des bases de données spécifiques qu'on appelle les bases de données crédibilistes. Une base de donnée crédibiliste a deux niveaux d'incertitudes: (i) l'incertitude au niveau des attributs qui se manifeste à travers des degrés de véracité sur les hypothèses des attributs; (ii) l'incertitude au niveau des tuples représentée par des intervalles de confiance sur l'existence des tuples au sein de la table en question. D'autre part, la base de donnée crédibiliste peut être modélisée sous deux formes: (i) la forme compacte caractérisée par un ensemble d'attributs et un ensemble de tuples; (ii) la forme des mondes possibles représentée par un ensemble de base de données candidates où chaque base candidate est une représentation possible de la base de donnée compacte. Interroger la représentation des mondes possibles est une étape fondamentale pour valider les méthodes d'interrogation sur la base compacte crédibiliste. En effet, un modèle de base de donnée est dit système fort si le résultat de l'interrogation de sa représentation compacte est équivalent au résultat de l'interrogation de sa représentation des mondes possibles.Cette thèse est une étude sur les fondements des bases de données crédibilistes. Les contributions sont résumées comme suit:(i) La modélisation et l'interrogation de la base crédibiliste (EDB): Nous mettons en pratique le modèle compacte de la base de données (EDB) en proposant une implémentation objet-relationnelle, ce qui permet d'introduire l'interrogation de ce modèle avec les opérateurs relationnels. D'autres part, nous présentons le formalisme, les algorithmes et les expérimentations d'autres types de requêtes :les top-k évidentiel et le skyline évidentiel que nous appliquons sur des données réelles extraites de la plateforme Tripadvisor.(ii) La modélisation de la base de données sous sa forme des mondes possibles: Nous modélisons la forme de mondes possibles de la base de données (EDB) en traitant les deux niveaux d'incertitudes (niveau attributs et niveau tuples).(iii) La modélisation et l'interrogation de la base de données crédibiliste (ECD): Après avoir prouvé que le modèle des bases de données (ED B) n'est pas un système de représentation fort, nous développons le modèle de la base de données crédibiliste conditionnelle nommée (ECD). Nous présentons le formalisme de l’interrogation sur les deux formes (compacte et mondes possibles) de la base de données (ECD). Finalement, nous discutons les résultats de ces méthodes d'interrogation et les spécificités du modèle (ECD). / The theory of belief functions (a.k.a, the Evidence Theory) offers powerful tools to mode! and handle imperfect pieces of information. Thus, it provides an adequate framework able to represent conjointly uncertainty, imprecision and ignorance. In this context, data are stored in a specific database model called evidential databases. An evidential database includes two levels of uncertainty: (i) the attribute level uncertainty expressed via some degrees of truthfulness about the hypotheses in attributes; (ii) the tuple level uncertainty expressed through an interval of confidence about the existenceof the tuple in the table. An evidential database itself can be modeled in two forms:(i) the compact form represented as a set of attributes and a set of tuples; (ii) the possible worlds' form represented as a set of candidate databases where each candidate is a possible representation of the imperfect compact database. Querying the possible worlds' form is a fundamental step in order to check the querying methods over the compact one. In fact, a model is said to be a strong representation system when results of querying its compact form are equivalent to results of querying its non compact form.This thesis focuses on foundations of evidential databases in both modeling and querying. The main contributions are summarized as follows:(i) Modeling and querying the compact evidential database (EDB): We implement the compact evidential database (EDB) using the object-relational design which allows to introduce the querying of the database model under relational operators. We also propose the formalism, the algorithms and the experiments of other typesof queries: the evidential top-k and the evidential skyline that we apply over a real dataset extracted from TripAdvisor.(ii) Modeling the possible worlds' form of (EDB): We model the possible worlds' form of the evidential database (EDB) by treating both levels of uncertainty (the tuple leve! and the attribute level).(iii) Modeling and querying the evidential conditional database (ECD): After provingt hat the evidential database (EDB) is not a strong representation system, we develop a new evidential conditional database model named (ECD). Thus, we present the formalism of querying the compact and the possible worlds' forms of the (ECD) to evaluate the querying methods under relational operators. Finally, we discuss the results of these querying methods and the specificities of the (ECD)model.

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.

L’externalisation de données d’entreprise ou individuelles chez un fournisseur de cloud, par exemple avec l’approche Database-as-a-Service, est pratique et rentable. Mais elle introduit un problème majeur: comment préserver la confidentialité des données externalisées, tout en prenant en charge les requêtes expressives des utilisateurs. Une solution simple consiste à crypter les données avant leur externalisation. Ensuite, pour répondre à une requête, le client utilisateur peut récupérer les données cryptées du cloud, les décrypter et évaluer la requête sur des données en texte clair (non cryptées). Cette solution n’est pas pratique, car elle ne tire pas parti de la puissance de calcul fournie par le cloud pour évaluer les requêtes.Dans cette thèse, nous considérons un type important de requêtes, les requêtes top-k, et le problème du traitement des requêtes top-k sur des données cryptées dans le cloud, tout en préservant la vie privée. Une requête top-k permet à l’utilisateur de spécifier un nombre k de tuples les plus pertinents pour répondre à la requête. Le degré de pertinence des tuples par rapport à la requête est déterminé par une fonction de notation.Nous proposons d’abord un système complet, appelé BuckTop, qui est capable d’évaluer efficacement les requêtes top-k sur des données cryptées, sans avoir à les décrypter dans le cloud. BuckTop inclut un algorithme de traitement des requêtes top-k qui fonctionne sur les données cryptées, stockées dans un nœud du cloud, et retourne un ensemble qui contient les données cryptées correspondant aux résultats top-k. Il est aidé par un algorithme de filtrage efficace qui est exécuté dans le cloud sur les données chiffrées et supprime la plupart des faux positifs inclus dans l’ensemble renvoyé. Lorsque les données externalisées sont volumineuses, elles sont généralement partitionnées sur plusieurs nœuds dans un système distribué. Pour ce cas, nous proposons deux nouveaux systèmes, appelés SDB-TOPK et SD-TOPK, qui permettent d’évaluer les requêtes top-k sur des données distribuées cryptées sans avoir à les décrypter sur les nœuds où elles sont stockées. De plus, SDB-TOPK et SD-TOPK ont un puissant algorithme de filtrage qui filtre les faux positifs autant que possible dans les nœuds et renvoie un petit ensemble de données cryptées qui seront décryptées du côté utilisateur. Nous analysons la sécurité de notre système et proposons des stratégies efficaces pour la mettre en œuvre.Nous avons validé nos solutions par l’implémentation de BuckTop, SDB-TOPK et SD-TOPK, et les avons comparé à des approches de base par rapport à des données synthétiques et réelles. Les résultats montrent un excellent temps de réponse par rapport aux approches de base. Ils montrent également l’efficacité de notre algorithme de filtrage qui élimine presque tous les faux positifs. De plus, nos systèmes permettent d’obtenir une réduction significative des coûts de communication entre les nœuds du système distribué lors du calcul du résultat de la requête. / Outsourcing corporate or individual data at a cloud provider, e.g. using Database-as-a-Service, is practical and cost-effective. But it introduces a major problem: how to preserve the privacy of the outsourced data, while supporting powerful user queries. A simple solution is to encrypt the data before it is outsourced. Then, to answer a query, the user client can retrieve the encrypted data from the cloud, decrypt it, and evaluate the query over plaintext (non encrypted) data. This solution is not practical, as it does not take advantage of the computing power provided by the cloud for evaluating queries.In this thesis, we consider an important kind of queries, top-k queries,and address the problem of privacy-preserving top-k query processing over encrypted data in the cloud.A top-k query allows the user to specify a number k, and the system returns the k tuples which are most relevant to the query. The relevance degree of tuples to the query is determined by a scoring function.We first propose a complete system, called BuckTop, that is able to efficiently evaluate top-k queries over encrypted data, without having to decrypt it in the cloud. BuckTop includes a top-k query processing algorithm that works on the encrypted data, stored at one cloud node,and returns a set that is proved to contain the encrypted data corresponding to the top-k results. It also comes with an efficient filtering algorithm that is executed in the cloud on encypted data and removes most of the false positives included in the set returned.When the outsourced data is big, it is typically partitioned over multiple nodes in a distributed system. For this case, we propose two new systems, called SDB-TOPK and SD-TOPK, that can evaluate top-k queries over encrypted distributed data without having to decrypt at the nodes where they are stored. In addition, SDB-TOPK and SD-TOPK have a powerful filtering algorithm that filters the false positives as much as possible in the nodes, and returns a small set of encrypted data that will be decrypted in the user side. We analyze the security of our system, and propose efficient strategies to enforce it.We validated our solutions through implementation of BuckTop , SDB-TOPK and SD-TOPK, and compared them to baseline approaches over synthetic and real databases. The results show excellent response time compared to baseline approaches. They also show the efficiency of our filtering algorithm that eliminates almost all false positives. Furthermore, our systems yieldsignificant reduction in communication cost between the distributed system nodes when computing the query result.