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