Doctorat en philosophie et lettres / info:eu-repo/semantics/nonPublished

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.

La mise en registre 3D (opération parfois appelée alignement) est un processus de transformation d’ensembles de données 3D dans un même système de coordonnées afin d’en aligner les éléments communs. Deux ensembles de données alignés ensemble peuvent être les scans partiels des deux vues différentes d’un même objet. Ils peuvent aussi être deux modèles complets, générés à des moments différents, d’un même objet ou de deux objets distincts. En fonction des ensembles de données à traiter, les méthodes d’alignement sont classées en mise en registre rigide ou non-rigide. Dans le cas de la mise en registre rigide, les données sont généralement acquises à partir d’objets rigides. Le processus de mise en registre peut être accompli en trouvant une seule transformation rigide globale (rotation, translation) pour aligner l’ensemble de données source avec l’ensemble de données cible. Toutefois, dans le cas non-rigide, où les données sont acquises à partir d’objets déformables, le processus de mise en registre est plus difficile parce qu’il est important de trouver à la fois une transformation globale et des déformations locales. Dans cette thèse, trois méthodes sont proposées pour résoudre le problème de mise en registre non-rigide entre deux ensembles de données (représentées par des maillages triangulaires) acquises à partir d’objets déformables. La première méthode permet de mettre en registre deux surfaces se chevauchant partiellement. La méthode surmonte les limitations des méthodes antérieures pour trouver une grande déformation globale entre deux surfaces. Cependant, cette méthode est limitée aux petites déformations locales sur la surface afin de valider le descripteur utilisé. La seconde méthode est s’appuie sur le cadre de la première et est appliquée à des données pour lesquelles la déformation entre les deux surfaces est composée à la fois d’une grande déformation globale et de petites déformations locales. La troisième méthode, qui se base sur les deux autres méthodes, est proposée pour la mise en registre d’ensembles de données qui sont plus complexes. Bien que la qualité que elle fournit n’est pas aussi bonne que la seconde méthode, son temps de calcul est accéléré d’environ quatre fois parce que le nombre de paramètres optimisés est réduit de moitié. L’efficacité des trois méthodes repose sur des stratégies via lesquelles les correspondances sont déterminées correctement et le modèle de déformation est exploité judicieusement. Ces méthodes sont mises en oeuvre et comparées avec d’autres méthodes sur diverses données afin d’évaluer leur robustesse pour résoudre le problème de mise en registre non-rigide. Les méthodes proposées sont des solutions prometteuses qui peuvent être appliquées dans des applications telles que la mise en registre non-rigide de vues multiples, la reconstruction 3D dynamique, l’animation 3D ou la recherche de modèles 3D dans des banques de données. / Three-dimensional registration (sometimes referred to as alignment or matching) is the process of transforming many 3D data sets into the same coordinate system so as to align overlapping components of these data sets. Two data sets aligned together can be two partial scans from two different views of the same object. They can also be two complete models of an object generated at different times or even from two distinct objects. Depending on the generated data sets, the registration methods are classified into rigid registration or non-rigid registration. In the case of rigid registration, the data is usually acquired from rigid objects. The registration process can be accomplished by finding a single global rigid transformation (rotation, translation) to align the source data set with the target data set. However, in the non-rigid case, in which data is acquired from deformable objects, the registration process is more challenging since it is important to solve for both the global transformation and local deformations. In this thesis, three methods are proposed to solve the non-rigid registration problem between two data sets (presented in triangle meshes) acquired from deformable objects. The first method registers two partially overlapping surfaces. This method overcomes some limitations of previous methods to solve large global deformations between two surfaces. However, the method is restricted to small local deformations on the surface in order to validate the descriptor used. The second method is developed from the framework of the first method and is applied to data for which the deformation between the two surfaces consists of both large global deformation and small local deformations. The third method, which exploits both the first and second method, is proposed to solve more challenging data sets. Although the quality of alignment that is achieved is not as good as the second method, its computation time is accelerated approximately four times since the number of optimized parameters is reduced by half. The efficiency of the three methods is the result of the strategies in which correspondences are correctly determined and the deformation model is adequately exploited. These proposed methods are implemented and compared with other methods on various types of data to evaluate their robustness in handling the non-rigid registration problem. The proposed methods are also promising solutions that can be applied in applications such as non-rigid registration of multiple views, 3D dynamic reconstruction, 3D animation or 3D model retrieval.

En droit positif belge, il n'existe aucun principe général permettant l'appropriation de l'information.

.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations n-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques. / Comparative genomics is essentially a form of data mining in large collections of n-ary relations between genomic elements. Increases in the number of sequenced genomes create a stress on comparative genomics that grows, at worse geometrically, for every increase in sequence data. Even modestly-sized labs now routinely obtain several genomes at a time, and like large consortiums expect to be able to perform all-against-all analyses as part of these new multi-genome strategies. In order to address the needs at all levels it is necessary to rethink the algorithmic frameworks and data storage technologies used for comparative genomics.To meet these challenges of scale, in this thesis we develop novel methods based on NoSQL and MapReduce technologies. Using a characterization of the kinds of data used in comparative genomics, and a study of usage patterns for their analysis, we define a practical formalism for genomic Big Data, implement it using the Cassandra NoSQL platform, and evaluate its performance. Furthermore, using two quite different global analyses in comparative genomics, we define two strategies for adapting these applications to the MapReduce paradigm and derive new algorithms. For the first, identifying gene fusion and fission events in phylogenies, we reformulate the problem as a bounded parallel traversal that avoids high-latency graph-based algorithms. For the second, consensus clustering to identify protein families, we define an iterative sampling procedure that quickly converges to the desired global result. For both of these new algorithms, we implement each in the Hadoop MapReduce platform, and evaluate their performance. The performance is competitive and scales much better than existing solutions, but requires particular (and future) effort in devising specific algorithms.

Le contexte international de la pharmacoépidémiologie, marqué par la mise en œuvre d’un nombre croissant d’études multi-sources, a fait émerger un certain nombre de questionnements autour de la gestion de données conflictuelles ou de l’impact des choix méthodologiques sur les résultats.Accroître la confiance dans ces études observationnelles et renforcer leur crédibilité face aux données issues des essais cliniques représente un enjeu majeur, qui dépend étroitement de la robustesse des conclusions produites. Dans ce domaine, la mesure de l’exposition médicamenteuse revêt donc une importance toute particulière, tant pour des études portant sur l’estimation d’un risque ou d’un critère d’efficacité, que lors de la description des modalités d’utilisation en vie réelle. L’exposition médicamenteuse reste un phénomène complexe qui se caractérise la plupart du temps par des cycles discontinus, marqués par des évolutions de doses et la présence de médicaments concomitants. Compte tenu des caractéristiques pharmacodynamiques et pharmacocinétiques / The multinational context of pharmacoepidemiology, and the resulting increased number ofmulti-sources studies have generated concerns in relation with conflicting results and the question of the impact of methodological choices on study results. Increasing the confidence in the conclusions derived from these observational studies is a crucial issue, which is closely related to the robustness of the evidence produced. In this area, impact of drug exposure measurement and risk window might be crucial.Drug exposure is mostly characterized by discontinuous episodes, marked by changes in doses and presence of concomitant medications. Considering the pharmacokinetic and pharmacodynamics characteristics specific to each individual drug, the way in which the drug exposure is presented is of great importance. However, methods used for handling drug exposure episodes in electronic healthcare databases are varying widely according studies. However, the impact of these methods

Dans cette thèse, nous nous intéressons à des problèmes à la croisée de deux domaines, les bases de données et les bases de connaissances. Nous considérons deux problèmes équivalents concernant les requêtes conjonctives avec négation : l'inclusion de requêtes et l'évaluation d'une requête booléenne sous l'hypothèse du monde ouvert. Nous reformulons ces problèmes sous la forme d'un problème de déduction dans un fragment de la logique du premier ordre. Puis nous raffinons des schémas d'algorithmes déjà existants et proposons de nouveaux algorithmes. Pour les étudier et les comparer expérimentalement, nous proposons un générateur aléatoire et analysons l'influence des différents paramètres sur la difficulté des instances du problème étudié. Finalement, à l'aide de cette méthodologie expérimentale, nous comparons les apports des différents raffinements et les algorithmes entre eux. / In this thesis, we consider problems at the intersection of two areas: databases and knowledge bases. We focus on two equivalent problems on conjunctive queries with negation : query containment and query answering with boolean queries while making the open-world assumption. We reformulate these problems as a problem of deduction in a first order logic fragment. Then we refine existing algorithm schemes and propose new algorithms. To study and compare them experimentally, we propose a random generator and we analyze the influence of parameters on problem instances difficulty. Finally, we analyse the contributions of the different refinements and we compare experimentally the algorithms.

Au cours des dernières années, le volume des données qui sont capturées et générées a explosé. Les progrès des technologies informatiques, qui fournissent du stockage à bas prix et une très forte puissance de calcul, ont permis aux organisations d'exécuter des analyses complexes de leurs données et d'en extraire des connaissances précieuses. Cette tendance a été très importante non seulement pour l'industrie, mais a également pour la science, où les meilleures instruments et les simulations les plus complexes ont besoin d'une gestion efficace des quantités énormes de données.Le parallélisme est une technique fondamentale dans la gestion de données extrêmement volumineuses car il tire parti de l'utilisation simultanée de plusieurs ressources informatiques. Pour profiter du calcul parallèle, nous avons besoin de techniques de partitionnement de données efficaces, qui sont en charge de la division de l'ensemble des données en plusieurs partitions et leur attribution aux nœuds de calculs. Le partitionnement de données est un problème complexe, car il doit prendre en compte des questions différentes et souvent contradictoires telles que la localité des données, la répartition de charge et la maximisation du parallélisme.Dans cette thèse, nous étudions le problème de partitionnement de données, en particulier dans les bases de données parallèles scientifiques qui sont continuellement en croissance. Nous étudions également ces partitionnements dans le cadre MapReduce.Dans le premier cas, nous considérons le partitionnement de très grandes bases de données dans lesquelles des nouveaux éléments sont ajoutés en permanence, avec pour exemple une application aux données astronomiques. Les approches existantes sont limitées à cause de la complexité de la charge de travail et l'ajout en continu de nouvelles données limitent l'utilisation d'approches traditionnelles. Nous proposons deux algorithmes de partitionnement dynamique qui attribuent les nouvelles données aux partitions en utilisant une technique basée sur l'affinité. Nos algorithmes permettent d'obtenir de très bons partitionnements des données en un temps d'exécution réduit comparé aux approches traditionnelles.Nous étudions également comment améliorer la performance du framework MapReduce en utilisant des techniques de partitionnement de données. En particulier, nous sommes intéressés par le partitionnement efficient de données d'entrée / During the last years, the volume of data that is captured and generated has exploded. Advances in computer technologies, which provide cheap storage and increased computing capabilities, have allowed organizations to perform complex analysis on this data and to extract valuable knowledge from it. This trend has been very important not only for industry, but has also had a significant impact on science, where enhanced instruments and more complex simulations call for an efficient management of huge quantities of data.Parallel computing is a fundamental technique in the management of large quantities of data as it leverages on the concurrent utilization of multiple computing resources. To take advantage of parallel computing, we need efficient data partitioning techniques which are in charge of dividing the whole data and assigning the partitions to the processing nodes. Data partitioning is a complex problem, as it has to consider different and often contradicting issues, such as data locality, load balancing and maximizing parallelism.In this thesis, we study the problem of data partitioning, particularly in scientific parallel databases that are continuously growing and in the MapReduce framework.In the case of scientific databases, we consider data partitioning in very large databases in which new data is appended continuously to the database, e.g. astronomical applications. Existing approaches are limited since the complexity of the workload and continuous appends restrict the applicability of traditional approaches. We propose two partitioning algorithms that dynamically partition new data elements by a technique based on data affinity. Our algorithms enable us to obtain very good data partitions in a low execution time compared to traditional approaches.We also study how to improve the performance of MapReduce framework using data partitioning techniques. In particular, we are interested in efficient data partitioning of the input datasets to reduce the amount of data that has to be transferred in the shuffle phase. We design and implement a strategy which, by capturing the relationships between input tuples and intermediate keys, obtains an efficient partitioning that can be used to reduce significantly the MapReduce's communication overhead.