L'indexation et la recherche efficiente de données complexes constitue un besoin croissant face à la taille et à la variété des bases de données actuelles. Nous proposons une structure d'index arborescent basée sur un partitionnement d'un espace métrique à base de boules et d'hyper-plans. Les performances de cet index sont évaluées expérimentalement sur des collections de complexités intrinsèques différentes. La parallélisation de l'algorithme de recherche des k plus proches voisins est également effectuée afin d'encore améliorer les performances.

No description available.

No description available.

This dissertation studies data privacy preservation in collaborative filtering based recommender systems and proposes several collaborative filtering models that aim at preserving user privacy from different perspectives. The empirical study on multiple classical recommendation algorithms presents the basic idea of the models and explores their performance on real world datasets. The algorithms that are investigated in this study include a popularity based model, an item similarity based model, a singular value decomposition based model, and a bipartite graph model. Top-N recommendations are evaluated to examine the prediction accuracy. It is apparent that with more customers' preference data, recommender systems can better profile customers' shopping patterns which in turn produces product recommendations with higher accuracy. The precautions should be taken to address the privacy issues that arise during data sharing between two vendors. Study shows that matrix factorization techniques are ideal choices for data privacy preservation by their nature. In this dissertation, singular value decomposition (SVD) and nonnegative matrix factorization (NMF) are adopted as the fundamental techniques for collaborative filtering to make privacy-preserving recommendations. The proposed SVD based model utilizes missing value imputation, randomization technique, and the truncated SVD to perturb the raw rating data. The NMF based models, namely iAux-NMF and iCluster-NMF, take into account the auxiliary information of users and items to help missing value imputation and privacy preservation. Additionally, these models support efficient incremental data update as well. A good number of online vendors allow people to leave their feedback on products. It is considered as users' public preferences. However, due to the connections between users' public and private preferences, if a recommender system fails to distinguish real customers from attackers, the private preferences of real customers can be exposed. This dissertation addresses an attack model in which an attacker holds real customers' partial ratings and tries to obtain their private preferences by cheating recommender systems. To resolve this problem, trustworthiness information is incorporated into NMF based collaborative filtering techniques to detect the attackers and make reasonably different recommendations to the normal users and the attackers. By doing so, users' private preferences can be effectively protected.

Motivated by increasing public awareness of possible abuse of confidential information, which is considered as a significant hindrance to the development of e-society, medical and financial markets, a privacy preserving data mining framework is presented so that data owners can carefully process data in order to preserve confidential information and guarantee information functionality within an acceptable boundary. First, among many privacy-preserving methodologies, as a group of popular techniques for achieving a balance between data utility and information privacy, a class of data perturbation methods add a noise signal, following a statistical distribution, to an original numerical matrix. With the help of analysis in eigenspace of perturbed data, the potential privacy vulnerability of a popular data perturbation is analyzed in the presence of very little information leakage in privacy-preserving databases. The vulnerability to very little data leakage is theoretically proved and experimentally illustrated. Second, in addition to numerical matrices, social networks have played a critical role in modern e-society. Security and privacy in social networks receive a lot of attention because of recent security scandals among some popular social network service providers. So, the need to protect confidential information from being disclosed motivates us to develop multiple privacy-preserving techniques for social networks. Affinities (or weights) attached to edges are private and can lead to personal security leakage. To protect privacy of social networks, several algorithms are proposed, including Gaussian perturbation, greedy algorithm, and probability random walking algorithm. They can quickly modify original data in a large-scale situation, to satisfy different privacy requirements. Third, the era of big data is approaching on the horizon in the industrial arena and academia, as the quantity of collected data is increasing in an exponential fashion. Three issues are studied in the age of big data with privacy preservation, obtaining a high confidence about accuracy of any specific differentially private queries, speedily and accurately updating a private summary of a binary stream with I/O-awareness, and launching a mutual private information retrieval for big data. All three issues are handled by two core backbones, differential privacy and the Chernoff Bound.

Information retrieval aims to extract from a large collection of data a subset of information that is relevant to user’s needs. In this study, we are interested in information retrieval in Arabic-Language text documents. We focus on the Arabic language, its morphological features that potentially impact the implementation and performance of an information retrieval system and its unique characters that are absent in the Latin alphabet and require specialized approaches. Specifically, we report on the design, implementation and evaluation of the search functionality using the Vector Space Model with several weighting schemes. Our implementation uses the ISRI stemming algorithms as the underlying stemming technique and the general Arabic stop word list for building inverted indices for Arabic-language documents. We evaluate our implementation on a corpus consisting of selected technical papers published in Arabic-language journals. We use the Open Journal Systems (OJS) from the Public Knowledge Project as a repository for the corpus used in the evaluation. We evaluate the performance of our implementation of the search using a classic recall/precision approach and compare it to one of the default multilingual search functions supported in the OJS. Our experimental analysis suggests that stemming is an effective technique for searches in Arabic-language texts that improves the quality of the information retrieval system.

Cette thèse est consacrée aux tests statistiques, visant à comparer un vecteur de données numériques, indicées par l'ensemble des gènes du génome humain, à un certain ensemble de gènes, connus pour être associés par exemple à un type donné de cancer. Parmi les méthodes existantes, le test Gene Set Enrichment Analysis est le plus utilisé. Néanmoins, il a deux inconvénients. D'une part, le calcul des p-valeurs est coûteux et peu précis. D'autre part, il déclare de nombreux résultats significatifs, dont une majorité n'ont pas de sens biologique. Ces deux problèmes sont traités, par l'introduction de deux procédures statistiques nouvelles, les tests de Kolmogorov-Smirnov pondéré et doublement pondéré. Ces deux tests ont été appliqués à des données simulées et réelles, et leurs résultats comparés aux procédures existantes. Notre conclusion est que, au-delà leurs avantages mathématiques et algorithmiques, les tests proposés pourraient se révéler, dans de nombreux cas, plus informatifs que le test GSEA classique, et traiter efficacement les deux problèmes qui ont motivé leur construction. / Our focus is on statistical testing methods, that compare a given vector of numeric values, indexed by all genes in the human genome, to a given set of genes, known to be associated to a particular type of cancer for instance. Among existing methods, Gene Set Enrichment Analysis is the most widely used. However it has several drawbacks. Firstly, the calculation of p-values is very much time consuming, and insufficiently precise. Secondly, like most other methods, it outputs a large number of significant results, the majority of which are not biologically meaningful. The two issues are addressed here, by two new statistical procedures, the Weighted and Doubly Weighted Kolmogorov-Smirnov tests. The two tests have been applied both to simulated and real data, and compared with other existing procedures. Our conclusion is that, beyond their mathematical and algorithmic advantages, the WKS and DWKS tests could be more informative in many cases, than the classical GSEA test and efficiently address the issues that have led to their construction.

Ces dernières années ont été marquées par l'adoption en masse de XML comme format d'échange et de représentation des données stockées sur le web. Cette évolution s'est accompagnée du développement de langages pour l'interrogation et la manipulation des données XML et de la mise en œuvre de plusieurs systèmes pour le stockage et le traitement des ces dernières. Parmi ces systèmes, les moteurs mémoire centrale ont été développés pour faire face à des besoins spécifiques d'applications qui ne nécessitant pas les fonctionnalités avancées des SGBD traditionnels. Ces moteurs offrent les mêmes fonctionnalités que les systèmes traditionnels sauf que contrairement à ces derniers, ils nécessitent de charger entièrement les documents en mémoire centrale pour pouvoir les traiter. Par conséquent, ces systèmes sont limités quant à la taille des documents pouvant être traités. Dans cette thèse nous nous intéressons aux aspects liés à l'évolution des données XML et à la gestion de la dimension temporelle de celles-ci. Cette thèse comprend deux parties ayant comme objectif commun le développement de méthodes efficaces pour le traitement des documents XML volumineux en utilisant les moteurs mémoire centrale.Dans la première partie nous nous focalisons sur la mise à jour des documents XML statiques. Nous proposons une technique d'optimisation basée sur la projection XML et sur l'utilisation des schémas. La projection est une méthode qui a été proposée dans le cadre des requêtes afin de résoudre les limitations des moteurs mémoire centrale. Son utilisation pour le cas des mises à jour soulève de nouveaux problèmes liés notamment à la propagation des effets des mises à jours. La deuxième partie est consacrée à la construction et à la maintenance des documents temporels, toujours sous la contrainte d'espace. A cette contrainte s'ajoute la nécessité de générer des documents efficaces du point de vue du stockage. Notre contribution consiste en deux méthodes. La première méthode s'applique dans le cas général pour lequel aucune information n'est utilisée pour la construction des documents temporels. Cette méthode est conçue pour être réalisée en streaming et permet ainsi le traitement de document quasiment sans limite de taille. La deuxième méthode s'applique dans le cas où les changements sont spécifiés par des mises à jour. Elle utilise le paradigme de projection ce qui lui permet en outre de manipuler des documents volumineux de générer des documents temporels satisfaisant du point de vue du stockage.

Nous proposons une approche pour ajouter des propriétés non-fonctionnelles (traitement d'exceptions, atomicité, sécurité, persistance) à des coordinations de services. L'approche est basée sur un Modèle de Politiques Actives (AP Model) pour représenter les coordinations de services avec des propriétés non-fonctionnelles comme une collection de types. Dans notre modèle, une coordination de services est représentée comme un workflow compose d'un ensemble ordonné d'activité. Chaque activité est en charge d'implante un appel à l'opération d'un service. Nous utilisons le type Activité pour représenter le workflow et ses composants (c-à-d, les activités du workflow et l'ordre entre eux). Une propriété non-fonctionnelle est représentée comme un ou plusieurs types de politiques actives, chaque politique est compose d'un ensemble de règles événement-condition-action qui implantent un aspect d'un propriété. Les instances des entités du modèle, politique active et activité peuvent être exécutées. Nous utilisons le type unité d'exécution pour les représenter comme des entités dont l'exécution passe par des différents états d'exécution en exécution. Lorsqu'une politique active est associée à une ou plusieurs unités d'exécution, les règles vérifient si l'unité d'exécution respecte la propriété non-fonctionnelle implantée en évaluant leurs conditions sur leurs états d'exécution. Lorsqu'une propriété n'est pas vérifiée, les règles exécutant leurs actions pour renforcer les propriétés en cours d'exécution. Nous avons aussi proposé un Moteur d'exécution de politiques actives pour exécuter un workflow orientés politiques actives modélisé en utilisant notre AP Model. Le moteur implante un modèle d'exécution qui détermine comment les instances d'une AP, une règle et une activité interagissent entre elles pour ajouter des propriétés non-fonctionnelles (NFP) à un workflow en cours d'exécution. Nous avons validé le modèle AP et le moteur d'exécution de politiques actives en définissant des types de politiques actives pour adresser le traitement d'exceptions, l'atomicité, le traitement d'état, la persistance et l'authentification. Ces types de politiques actives ont été utilisés pour implanter des applications à base de services fiables, et pour intégrer les données fournies par des services à travers des mashups.

De nombreuses applications distribuées partagent la même nécessité de traiter des flux de données de façon continue, par ex. la surveillance de réseau ou la gestion de réseaux de capteurs. Dans ce contexte, un problème important et difficile concerne le traitement de requêtes continues de jointure qui nécessite de maintenir une fenêtre glissante sur les données la plus grande possible, afin de produire le plus possible de résultats probants. Dans cette thèse, nous proposons une nouvelle méthode pair-à-pair, DHTJoin, qui tire parti d'une Table de Hachage Distribuée (DHT) pour augmenter la taille de la fenêtre glissante en partitionnant les flux sur un grand nombre de nœuds. Contrairement aux solutions concurrentes qui indexent tout les tuples des flux, DHTJoin n'indexe que les tuples requis pour les requêtes et exploite, de façon complémentaire, la dissémination de requêtes. DHTJoin traite aussi le problème de la dynamicité des nœuds, qui peuvent quitter le système ou tomber en panne pendant l'exécution. Notre évaluation de performances montre que DHTJoin apporte une réduction importante du trafic réseau, par rapport aux méthodes concurrentes.