Voici les éléments 1 - 7 sur 7
  • Publication
    Accès libre
    Using multiperspective observations to improve data quality in distributed systems
    Les systèmes pilotés par les données deviennent rapidement un paradigme de premier plan, l’avènement de l’IA et des systèmes cyber-physiques intelligents devenant une caractéristique déterminante de l’époque moderne. On dit souvent que la qualité des données qui entrent dans ces systèmes est le principal déterminant du comportement et des décisions qu’ils produisent. Il est donc primordial de fournir de meilleures stratégies de gestion et d’amélioration de la qualité des données pour les systèmes autonomes. Un autre attribut de l’infrastructure moderne basée sur les données est sa nature hautement distribuée. En effet, les déploiements de cloud, d’IoT et de continuum/fog sont presque omniprésents dans la pratique actuelle. Dans de nombreux cas, les systèmes pilotés par les données susmentionnés sont déployés sur ce type d’infrastructure en premier lieu. Nous voyons une opportunité de tirer parti de l’ubiquité des ressources de calcul distribuées pour ajouter une couche d’assurance qualité aux données. Notre travail s’inspire de deux sources principales. D’une part, la nécessité de collecter de manière cohérente des données brutes de haute qualité et des informations et mesures dérivées, en présence d’erreurs, de problèmes et d’autres interférences. D’autre part, nous nous inspirons de la fusion de données, une méthodologie couramment utilisée pour combiner des données provenant de différentes sources afin d’obtenir des informations de meilleure qualité que la somme de leurs parties. Nous envisageons une généralisation de la fusion de données à tous les formats d’ensembles de données, en particulier lorsqu’elles sont obtenues en doublons redondants par des observateurs indépendants. Nous appelons ce type d’observation une "observation multiperspective". Notre méthodologie de base consiste à concevoir, mettre en oeuvre et évaluer ce concept d’observation multi-perspective. La première partie est un système d’observateurs indépendants, représentés comme des noeuds dans une architecture distribuée, des collaborateurs dans un projet crowdsourcé ou même simplement des capteurs matériels dans une configuration traditionnelle de fusion de capteurs. Nous commençons par présenter la première partie de cette stratégie d’observation, l’acquisition de données. Nous présentons notre premier scénario motivant, qui consiste à suivre l’évolution de l’écosystème cloud-native dans un observatoire distribué "démocratique". Nous fournissons ensuite notre implémentation de cet observatoire et présentons son utilisation pour comprendre et améliorer le support matériel dans les images Docker. En outre, nous discutons de l’intégration de notre système d’acquisition de données avec des outils de reproductibilité et de preuve des données centrés sur la science des données. Ce travail nous permet également d’étudier les limites et les défis liés à l’obtention de données de la part d’observateurs indépendants. Nous utilisons nos résultats pour développer nos méthodologies dans la partie suivante de ce travail. Nous présentons ensuite la solution que nous proposons pour résoudre les problèmes de qualité des données découverts : Consensus centré sur les données (DCC). En utilisant notre système d’acquisition de données et les données que nous avons obtenues, nous développons une architecture de système pour fusionner les observations en une vue commune de la vérité, sur laquelle tous les observateurs sont d’accord. Nous étudions ensuite les algorithmes que nous pouvons utiliser pour y parvenir, ainsi que les implications de notre système en termes de performances. Enfin, nous nous concentrons sur les algorithmes eux-mêmes et présentons notre propre contribution à l’espace des électeurs définis par logiciel, l’algorithme de vote AVOC, et VDX, une spécification générique pour décrire les électeurs définis par logiciel. Nous évaluons notre contribution à la fois par rapport et en conjonction avec l’état de l’art dans un exemple de fusion de capteurs pour montrer que les algorithmes de vote peuvent en effet augmenter à la fois la qualité des résultats et la performance lorsqu’ils sont correctement combinés avec des approches de fusion de données standard. Dans l’ensemble, cette thèse présente la stratégie de l’observation multi-perspective dans une approche de bout en bout, de l’acquisition des données à la réconciliation des conflits et à la détermination des gains de qualité des données. Nous montrons où cette méthodologie est applicable et fournissons une mise en oeuvre du modèle ainsi qu’une évaluation de ses performances et de ses limites. ABSTRACT Data-driven systems are quickly becoming a prominent paradigm, with the advent of AI and smart cyber-physical systems becoming a defining characteristic of the modern day. It is often stated that the quality of data going into such systems is the primary determinant of the behaviour and decisions they produce. It is thus paramount to provide better strategies for managing and improving data quality for autonomic systems. Another attribute of modern data-driven infrastructure is its highly distributed nature. Indeed cloud, IoT and continuum/fog deployments are almost ubiquitous in current practice. In many cases, the above-mentioned data-driven systems are deployed to such infrastructure in the first place. We see an opportunity to leverage the ubiquity of distributed compute resources to add a layer of quality assurance to data. Our work is inspired by two main sources. On one hand, the need to consistently collect high-quality raw data and derived insights and metrics, in the presence of faults, issues and other interference. On the other hand, we draw inspiration from data fusion, a methodology commonly used to combine data from different sources to obtain insights of higher quality than the sum of its parts. We envision a generalisation of data fusion to all formats of datasets, particularly when obtained in redundant duplicates from independent observers. We call such an observation, a ’multiperspective observation’. Our core methodology is to design, implement and evaluate this concept of multiperspective observation. The first part is a system of independent observers, represented as nodes in a distributed architecture, collaborators in a crowdsourced project or even just hardware sensors in a traditional sensor-fusion setup. We begin by presenting the first part of this observation strategy, data acquisition. We show our first motivating scenario, tracking the evolution of the cloud-native ecosystem in a ’democratic’ distributed observatory. We then provide our implementation of this observatory and present its use in understanding and improving hardware support in Docker images. Further, we discuss the integration of our data acquisition system with data science-centric reproducibility and data provenance tooling. This work also serves to help us study the limitations and challenges of obtaining data from independent observers. We use our findings to develop our methodologies for the next part of this work. Then, we introduce our proposed solution to the discovered issues in data quality: Data-Centric Consensus (DCC). Using our data acquisition system and the data we obtained, we develop a system architecture to merge the observations into a common view of the truth, that all observers agree to. We then investigate the algorithms we can use to achieve this, and the performance implications of our system. Finally, we focus on the algorithms themselves, and present our own contribution to the space of software-defined voters, the AVOC voting algorithm, and VDX, a generic specification for describing software-defined voters. We evaluate our contribution both against and in conjunction with the state-of-the-art in a sensor fusion example to show that voting algorithms can indeed augment both output quality and performance when correctly combined with standard data fusion approaches. All in all, this thesis presents the strategy of multiperspective observation in an end-to-end approach, from acquiring data, to reconciling conflicts to determining the gains in data quality. We show where this methodology is applicable and provide model implementation and an evaluation of both its performance and limitations.
  • Publication
    Accès libre
    SoftwIre integration: an approach to service composition through distributed representations of arbitrary-length business ontologies
    (2016)
    Ludolph, Hendrik
    ;
    ;
    Babin, Gilbert
    La demande de logiciel à la demande (Software as a Service ou SaaS) est en constante augmentation. Afin de remplir cette demande, une prolifération d’offres de services de type third-party s’en suit. Pour les organisations il est crucial de trouver et sélectionner le service approprié pour l’incorporer dans le parc TI existant. Idéalement, cela est effectué de façon continue et flexible, l’objectif étant de toujours fournir le meilleur support possible.
    Pour faire face à cet enjeu, des standards modernes d’intégrations tels que ESB, SOA ou BPI ont été conçus pour permettre un couplage faible (loose coupling) entre les services. Par contre, il manque à ces standards la capacité de bien décrire et capter la sémantique des services. Cette sémantique serait nécessaire pour une intégration automatique adéquate. L’efficacité de ces standards dépend aussi considérablement de l’intervention humaine. Une nouvelle génération de techniques sémantiques telles que SAWSDL, OWL-S ou WSMO vise à corriger cette situation en utilisant des ontologies. Ces dernières sont basées sur des règles formelles d’inférence, ayant l’ambition de représenter et d’interpréter le sens des données. Cela devrait mener à une sélection et intégration automatique supérieure de services.
    Nous croyons cependant que connaître et interpréter requiert plus que la manipulation réglementée et impérative d’expressions symbolique arbitraires. Selon nous, les approches purement symboliques, autant syntaxiques que sémantiques, ne permettent pas de combiner automatisation et flexibilité. Ceci est d’autant plus vrai dans des environnements compétitifs. Dans ces environnements, les changements d’offres de services ne peuvent être ni anticipés, ni gérés de façon contrôlée. Des conditions inconnues ne peuvent être traitées que dans la mesure où elles ont été prédéfinies.
    Afin de surmonter cette contradiction, nous proposons une approche hybride symbolique/connexionniste. À cette fin, nous présentons un cadre conceptuel de sélection automatique de services, basée sur des descriptions de haut niveau des besoins d’affaires. Ces descriptions sont décrites par des ontologies. Par la suite, nous explorons une topologie spécifique de réseau neuronal artificiel, nommé LRAAM. Avec ce dernier, la structure compositionnelle des ontologies est transformée dans une représentation distribuée (i.e., réduite, micro-sémantique). Le LRAAM amène le système à générer une représentation “propre” ou “interne” des descriptions ontologiques de services. Celles-ci peuvent être utilisées pour des analyses de similarité. Un outil (OntoProc) a été conçu comme preuve de concept. Avec celui-ci, nous conduisons différentes expériences afin d’étudier la validité de l’approche. Les données produites par l’outil ont fait l’objet d’analyse de signification statistique.
    Se basant sur les expériences conduites, nous ne pouvons pas conclure que l’implémentation de LRAAM utilisée est une alternative fiable pour la sélection et l’intégration de services. Nous démontrons que sous certaines conditions, le LRAAM produit une sélection correcte de services. Cependant, il n’est pas possible d’arriver à la même conclusion pour des données d’entrée plus complexes. Nous discutons des ajustements à faire à l’implémentation afin d’augmenter la performance de l’outil.
    Malgré des résultats non-concluants, nous sommes toutefois convaincu que des approches purement symboliques d’intégration automatique sont trop contraignantes quand il s’agit des services de type third-party. La flexibilité sans intervention humaine se situe au-delà de leurs capacités. Encouragé par des développements récents dans le domaine du connexionnisme (e.g., Deep Learning), nous adhérons tout de même à la piste de recherche choisie. Nous le voyons comme faisant partie d’un nouveau paradigme, qui est de traiter des larges vecteurs pour remplacer la manipulation réglementée de symboles., The demand for Software as a Service is ever increasing. With this demand comes a proliferation of third-party service offerings to fulfill it. It thus becomes crucial for organizations to find and select the right service to be integrated into their existing tool landscapes. Ideally, this is done automatically and flexibly. The objective is to always provide the best possible support to changing business needs.
    Modern integration standards, such as ESB, SOA, or BPI evolved to face this challenge, e.g., through loose coupling. However, they lack description capabilities to adequately capture service semantics, needed for adequate automated service selection and integration. They also heavily depend on human expert intervention. Next generation semantic techniques, such as SAWSDL, OWL-S, or WSMO aim at correcting this situation. They use ontologies, which are based on formal rules of inference. These techniques claim to extract and interpret the meaning of data, thereby leading to more reliable automated service selection and integration.
    To us however, knowing and interpreting is more than imperative, rule-based manipulation of arbitrary symbolic expressions. Pure symbolic, either syntactic or formal-semantic, approaches will thus not provide the bridge between automation and flexibility. This is even more so in competitive environments. Here, changes in the input data of third-party services offerings can neither be anticipated, nor can technical control be exercised. Unknown conditions can thus only be processed to the extent they are predefined.
    To overcome this contradiction, we investigate a hybrid symbolic/connectionist approach. To this end, we provide a framework for automated service selection based on high-level business requirements, described by ontologies. Thereafter, we explore a specific supervised artificial neural network topology called LRAAM. With it, the compositional structure of the ontologies is transformed into a distributed (i.e., reduced, micro-semantic) representation. It shall enable the system to develop an “own” or “inner” representation of service descriptions, which are then used for similarity analysis. A tool (OntoProc) was developed as a proof of concept. With it, we conducted different experiments to explore the validity of the approach. The tool generated output data, which we submitted to significance tests.
    Based on the experiments, the current LRAAM implementation is not a reliable alternative for service selection and integration. We showed that the LRAAM performs correct selection of services under specific parameters. However, for more complex input data, it does not yet yield the expected results. We discussed adjustments to the implementation to improve OntoProc’s performance. Despite the inconclusive results, we are, nevertheless, convinced that purely symbolic approaches to automatic integration are too restrictive when independent third-party services are concerned. Flexibility without human intervention is beyond their capabilities. Encouraged by recent developments in the field of connectionism (e.g., Deep Learning), we adhere to the chosen research venue. We see it as part of a new paradigm of operating on large vectors (i.e., connectionism) to replace rule-based manipulation of symbols.
  • Publication
    Accès libre
    Load management in peer-to-peer systems: structures and algorithms
    (2010)
    Serbu, Sabina
    ;
    Dans cette thèse, nous présentons plusieurs techniques inédites pour la gestion de charge dans les systèmes pair-à-pair. Nous abordons deux types de systèmes pair-à-pair: les systèmes de recherche d’information (en particulier DHTs), où nous définissons de nouvelles solutions pour l’équilibrage de charge, et les systèmes de diffusion d’information, où nous définissons de nouvelles méthodes de réduction de charge. Tout d’abord, nous présentons le contexte des systèmes pair-à-pair et nous élaborons sur les solutions existantes en matière de gestion de charge. Nous les classifions en trois différentes catégories: le placement des objets, le trafic de routage et la sous-couche (underlay). Bien que les deux premières catégories visent avant tout les systèmes de recherche d’information, portant sur l’affectation objet-à-nœud et sur les stratégies de routage appliquées pour la recherche d’objet, la dernière catégorie est plus générale. Tout recouvrement (overlay), quel que soit son applicabilité, doit avoir une certaine connaissance de son sous-couche afin de pouvoir gérer sa charge de trafic. Nous apportons trois solutions à la gestion de charge dans les systèmes pair-à-pair. Nous proposons HyPeer, un recouvrement de type DHT avec équilibrage dans l’espace de noms qui offre un choix flexible entre plusieurs stratégies de routage. à cette fin, nous avons construit la structure de HyPeer uniforme et régulière, où les nœuds sont consciencieusement placés. Le but est de fournir une redondance des chemins (path redundancy), où les chemins ont des longueurs similaires. Avec plusieurs chemins entre deux nœuds, de nombreuses différentes stratégies de routage peuvent être appliquées. Nous proposons quatre stratégies visant les plus communs objectifs: chemin court, délai faible, tolérance de panne et, le plus important dans notre contexte, équilibrage de charge de routage. Nos stratégies atteignent toutes de très bons résultats au coût de juste quelques calculs locaux pour déterminer le saut suivant dans le chemin. En outre, le recouvrement soutient la définition de nouvelles stratégies de routage ou le raffinage des stratégies de routage existantes avec de nouvelles métriques. Pour les autres DHTs existants, nous proposons une solution d’équilibrage de charge de routage qui peut ˆêtre appliquée à tout recouvrement qui permet une flexibilité dans le choix des voisins. Notre solution est adaptative et elle est basée sur la réorganisation des liens (link reorganization): en fonction de la fluctuation de charge dans le système, les voisins les plus chargés sont écartés, le trafic étant dirigé vers des pairs moins chargés. Cette solution a peu de frais, ne génère pas de messages supplémentaires et la réorganisation des liens est déclenché que lorsque la charge atteint des valeurs trop élevées. Dans les systèmes de diffusion d’information, nous proposons une nouvelle stratégie pour réduire la charge au niveau sous-couche. Nous n’utilisons pas le hasard comme les stratégies classiques le font, ce qui génère une charge de trafic très grande dans la sous-couche. Nous considérons plutôt la conscience de proximité. Après une dispersion limitée de l’information dans le réseau, nous donnons la préférence aux routes courtes pour la livraison du message de diffusion. Notre solution permet de réduire considérablement la charge de trafic dans la sous-couche, tout en n’affectant pas le temps de diffusion., In this thesis, we present several novel techniques for load management in peer-to-peer systems. We tackle two types of peer-to-peer systems: information lookup systems (in particular DHTs), where we define new load balancing solutions, and information dissemination systems, where we define new methods for load reduction First, we introduce the context of peer-to-peer systems and we elaborate on the existing solutions on load management. We classify them into three different categories: object placement, traffic routing and underlay. While the first two categories are aimed mostly at information lookup systems, dealing with object-to-node assignment and the routing strategies to be applied for object lookup, the latter category is more general. Any overlay, regardless its applicability, needs to have some knowledge about its underlay in order to manage its traffic load. Our contributions to load management solutions are threefold. We propose HyPeer, a novel DHT overlay with namespace balancing that offers flexible-choice among several routing strategies. For this purpose, we have built the uniform and regular HyPeer structure, where the nodes are conscientiously placed in order to offer path redundancy at similar path lengths. Having multiple paths between any two nodes, many different routing strategies can be applied. We propose four routing strategies aiming the most common goals: short path length, low path delay, fault tolerance and, most important in our context, routing load balancing. They all achieve very good results at the cost of only few local computations to determine the next hop in the request path. Moreover, the overlay offers support for defining new routing strategies or for refining the existing routing strategies with new metrics. For other existing DHTs, we propose a routing balancing solution that can be applied to any overlay that allows flexibility in the choice of the neighbors. Our solution is adaptive and it is based on link reorganization: according to the load fluctuation in the system, the most loaded neighbors are discarded, the forwarding traffic being redirected to less loaded peers instead. This solution comes at low costs, no extra messages being involved and moreover triggering link reorganization only when the load reaches too high values. In information dissemination systems, we propose a novel strategy in order to reduce the load at the underlay level. We do not use complete randomness as classical strategies do, this generating too much traffic load at the underlay, instead we consider proximity awareness. After a limited seeding of the network, we give preference to the usage of short routes for delivering the dissemination message. Our solution significantly reduces the traffic load at the underlay, while not affecting the dissemination time.
  • Publication
    Accès libre
    Influence of language morphological complexity on information retrieval
    (2010)
    Dolamic, Ljiljana
    ;
    ;
    In this dissertation two aspects of information retrieval are elaborated. The frst involves the creation and evaluation of various linguistic tools for languages less studied than English, and in our case we have chosen to work with the two Slavic languages Czech and Russian, and three languages widely spoken on the Indian subcontinent, Hindi, Marathi and Bengali. To do so we compare various indexing strategies and IR models most likely to obtain the best possible performance. The second part involves an evaluation of the effectiveness of queries written in different languages when searching collections written in either English or French. To cross the language barriers we apply publicly available machine translation services, analyze the results and then explain the poor performances obtained by the translated queries.
  • Publication
    Accès libre
    Algorithms for statistical model selection and robust estimation
    (2009)
    Hofmann, Marc
    ;
    Computationally intensive algorithms for model selection and robust regression are considered. Particular emphasis is put on regression trees. The QR decomposition is the main computational tool to solve the linear models. Givens rotations are employed to compute the orthogonal factorizations. A new pipelineparallel strategy is proposed for computing the QR decomposition. Algorithms for computing the best subset regression models are investigated. The algorithms extend previously introduced exhaustive and heuristic strategies, which are aimed at solving large-scale model selection problems. An algorithm is proposed to compute the exact least trimmed squares regression. It can efficiently compute the LTS estimators for a range of coverage values. Thus, the coverage parameter h does not need to be known in advance, and the algorithm can be used to examine the degree of contamination of the data. The LTS algorithm is extended to solve the generalized LTS estimation problem of the GLM and SUR model. The singularity problem of the dispersion matrix is avoided by reformulating the estimation problem as a generalized linear least squares problem.
  • Publication
    Accès libre
    Visualisation scientifique collaborative
    (2007)
    Casera, Steve
    ;
    La visualisation scientifique est utilisée habituellement pour résoudre des problèmes complexes et analyser des données. La collaboration joue un rôle crucial dans le domaine de la visualisation scientifique. En effet, dans les domaines d’application concernés, il est fréquent que l’on doive recourir aux compétences d’un spécialiste situé à une certaine distance. Dans cette thèse, nous présentons les différentes notions jouant un rôle essentiel dans le domaine de la collaboration, puis nous montrons que, parmi les systèmes de visualisation scientifique collaborative actuellement disponibles, certains sont mieux adaptés à la collaboration alors que d’autres cherchent avant tout une grande efficacité. Nous présentons un système qui satisfait ces deux exigences. D'une part, il s'agit de mettre à disposition des outils efficaces permettant la collaboration, afin que tous les participants puissent intervenir et communiquer entre eux. D'autre part, l'utilisation de ces outils doit être intuitive et permettre une avance rapide dans le travail. Lorsque plusieurs participants collaborent à distance, il faut assurer que le temps d'attente pour l'affichage des objets graphiques soit le plus petit possible. Ceci doit être assuré pour tous les participants indépendamment de leur séparation physique. Afin de réduire ce temps d'attente, nous avons analysé les différentes possibilités de transmettre les données de visualisation entre les ordinateurs. Il en résulte plusieurs configurations possibles. Nous avons développé une heuristique qui, pour chaque action demandée par les participants, choisit une configuration adéquate. Concernant la facilité d’utilisation, nous avons développé des outils pour faciliter la collaboration. Pour vérifier la facilité d’utilisation de notre système, nous avons conduit une expérimentation lors de laquelle des participants ont utilisé notre système pour accomplir une tâche assez simple. Nous avons comparé les résultats obtenus en fonction des moyens mis à disposition. Nous n’avons pas pu mettre en évidence un effet significatif imputable à la disponibilité de nos outils. Cependant, il en est ressorti que l’audio, comparé au chat seul, permet d’améliorer les performances et de faciliter la communication.
  • Publication
    Accès libre
    Numerical algorithms for estimating least squares problems
    (2005)
    Yanev, Petko Ivanov
    ;
    The solution of least squares estimation problems is of great importance in the areas of numerical linear algebra, computational statistics and econometrics. The design and analysis of numerically stable and computationally efficient methods for solving such least squares problems is considered. The main computational tool used for the estimation of the least squares solutions is the QR decomposition, or the generalized QR decomposition. Specifically, emphasis is given to the design of sequential and parallel strategies for computing the main matrix factorizations which arise in the estimation procedures. The strategies are based on block-generalizations of the Givens sequences and efficiently exploit the structure of the matrices. An efficient minimum spanning tree algorithm is proposed for computing the QR decomposition of a set of matrices which have common columns. Heuristic strategies are also considered. Several computationally efficient sequential algorithms for block downdating of the least squares solutions are designed, implemented and analyzed. A parallel algorithm based on the best sequential approach for downdating the QR decomposition is also proposed. Within the context of block up-downdating, efficient serial and parallel algorithms for computing the estimators of the general linear and seemingly unrelated regression models after been updated with new observations are proposed. The algorithms are based on orthogonal factorizations and are rich in BLAS-3 computations. Experimental results which support the theoretical derived complexities of the new algorithms are presented. The comparison of the new algorithms with the corresponding LAPACK routines is also performed. The parallel algorithms utilize efficient load balanced distribution over the processors and are found to be scalable and efficient for large-scale least squares problems. It is expected that the proposed block-algorithms will facilitate the solution of computationally intensive statistical problems and the estimation of large scale linear models on serial and parallel computers.