Search

In recent years, applications in domains such as telecommunications, network security or large scale sensor networks showed the limits of the traditional store-then-process paradigm. In this context, Stream Processing Engines emerged as a candidate solution for all these applications demanding for high processing capacity with low processing latency guarantees. With Stream Processing Engines, data streams are not persisted but rather processed on the fly, producing results continuously. Current Stream Processing Engines, either centralized or distributed, do not scale with the input load due to single-node bottlenecks. Moreover, they are based on static configurations that lead to either under or over-provisioning. This Ph.D. thesis discusses StreamCloud, an elastic paralleldistributed stream processing engine that enables for processing of large data stream volumes. Stream- Cloud minimizes the distribution and parallelization overhead introducing novel techniques that split queries into parallel subqueries and allocate them to independent sets of nodes. Moreover, Stream- Cloud elastic and dynamic load balancing protocols enable for effective adjustment of resources depending on the incoming load. Together with the parallelization and elasticity techniques, Stream- Cloud defines a novel fault tolerance protocol that introduces minimal overhead while providing fast recovery. StreamCloud has been fully implemented and evaluated using several real word applications such as fraud detection applications or network analysis applications. The evaluation, conducted using a cluster with more than 300 cores, demonstrates the large scalability, the elasticity and fault tolerance effectiveness of StreamCloud.; En los útimos años, aplicaciones en dominios tales como telecomunicaciones, seguridad de redes y redes de sensores de gran escala se han encontrado con múltiples limitaciones en el paradigma tradicional de bases de datos. En este contexto, los sistemas de procesamiento de flujos de datos han emergido como solución a estas aplicaciones que demandan una alta capacidad de procesamiento con una baja latencia. En los sistemas de procesamiento de flujos de datos, los datos no se persisten y luego se procesan, en su lugar los datos son procesados al vuelo en memoria produciendo resultados de forma continua. Los actuales sistemas de procesamiento de flujos de datos, tanto los centralizados, como los distribuidos, no escalan respecto a la carga de entrada del sistema debido a un cuello de botella producido por la concentración de flujos de datos completos en nodos individuales. Por otra parte, éstos están basados en configuraciones estáticas lo que conducen a un sobre o bajo aprovisionamiento. Esta tesis doctoral presenta StreamCloud, un sistema elástico paralelo-distribuido para el procesamiento de flujos de datos que es capaz de procesar grandes volúmenes de datos. StreamCloud minimiza el coste de distribución y paralelización por medio de una técnica novedosa la cual particiona las queries en subqueries paralelas repartiéndolas en subconjuntos de nodos independientes. Ademas, Stream- Cloud posee protocolos de elasticidad y equilibrado de carga que permiten una optimización de los recursos dependiendo de la carga del sistema. Unidos a los protocolos de paralelización y elasticidad, StreamCloud define un protocolo de tolerancia a fallos que introduce un coste mínimo mientras que proporciona una rápida recuperación. StreamCloud ha sido implementado y evaluado mediante varias aplicaciones del mundo real tales como aplicaciones de detección de fraude o aplicaciones de análisis del tráfico de red. La evaluación ha sido realizada en un cluster con más de 300 núcleos, demostrando la alta escalabilidad y la efectividad tanto de la elasticidad, como de la tolerancia a fallos de StreamCloud.; In recent years...

Submitted by Christianne Fontes de Andrade (cfontes@ct.ufrj.br) on 2020-01-21T17:31:05Z No. of bitstreams: 1 885643.pdf: 3290217 bytes, checksum: cca372e81e33fbbc2e4f08363ef349f8 (MD5) Made available in DSpace on 2020-01-21T17:31:05Z (GMT). No. of bitstreams: 1 885643.pdf: 3290217 bytes, checksum: cca372e81e33fbbc2e4f08363ef349f8 (MD5) Previous issue date: 2018-06 Simulações computacionais em larga escala são caracterizadas pelo encadeamento de programas que executam modelos computacionais cada vez mais complexos. Muitos dos dados produzidos por esses programas precisam ser analisados pelos usuários do domínio científico a fim de validar as suas hipóteses científicas. Entretanto, esta não é uma tarefa trivial, pois outros programas precisam ser desenvolvidos para acessar e capturar esses dados científicos. Em muitos casos, os usuários também precisam relacionar dados produzidos por diferentes programas de simulação. Esta tese propõe uma abordagem capaz de monitorar, depurar e analisar o fluxo de elementos de dados produzido pelos diferentes programas de simulação. Propomos também uma arquitetura baseada em componentes, nomeada como ARMFUL, que permite extrair e relacionar dados científicos produzidos nessas diversas etapas por meio da abstração de fluxo de dados e de técnicas de captura de dados científicos. Os seus componentes podem ser instanciados em um sistema de workflows científicos (A-Chiron) ou uma biblioteca de componentes (DfAnalyzer). Avaliamos essas instâncias utilizando simulações em ambientes de processamento de alto desempenho. Os resultados experimentais mostram que a nossa abordagem introduz uma sobrecarga negligenciável em relação ao tempo de execução da simulação, além de permitir o processamento de consultas aos dados científicos. Large-scale computational simulations are characterized by the chaining of programs that execute increasingly complex computational models. Much of the data produced by these programs need to be analyzed by scientific domain users to validate their scientific hypotheses. However, it is not trivial since other programs must be developed to access and to capture these scientific data. In many cases, users also need to relate data produced by different simulation programs. This thesis proposes an approach that monitors, debugs, and analyzes the data element flow produced by different simulation programs. We also propose a component-based architecture, named as ARMFUL, to extract and relate scientific data generated in these several simulation steps considering a dataflow abstraction and techniques for scientific data capture. ARMFUL’s components can be instantiated on a scientific workflow system (e.g., A-Chiron) or a library of components (e.g., DfAnalyzer). We evaluate these instances using simulations in high performance computing environments. In our experimental results, our approach introduced a negligible overhead of the simulation execution time, and we perform complex queries to the scientific data.

High-throughput phenotyping platforms allow acquisition of quantitative data on thousands of plants required for genetic analyses in well-controlled environmental conditions. However, analysing these massive datasets and reproducing computational experiments require the use of new computational infrastructure and algorithms to scale.

As part of the selection of the best items in a multidimensional database,several kinds of query were defined. The skyline operator has the advantage of not requiring the definition of a scoring function in order to classify tuples. However, the property of monotony that this operator does not satify, (i) makes difficult to optimize its queries in a multidimensional context, (ii) makes hard to estimate the size of query result. This work proposes, first, to address the question of estimating the size of the result of a given skyline query, formulating estimators with good statistical properties (unbiased or convergent). Then, it provides two different approaches to optimize multidimensional skyline queries. The first leans on a well known database concept: functional dependencies. And the second approach looks like a data compression method. Both algorithms are very interesting as confirm the experimental results. Finally, we address the issue of skyline queries in dynamic data by adapting one of our previous solutions in this goal., Dans le cadre de la sélection de meilleurs éléments au sein d’une base de données multidimensionnelle, plusieurs types de requêtes ont été définies. L’opérateur skyline présente l’avantage de ne pas nécessiter la définition d’une fonction de score permettant de classer lesdits éléments. Cependant, la propriété de monotonie que cet opérateur ne présente pas, rend non seulement (i) difficile l’optimisation de ses requêtes dans un contexte multidimensionnel, mais aussi (ii) presque imprévisible la taille du résultat des requêtes. Ce travail se propose, dans un premier temps, d’aborder la question de l’estimation de la taille du résultat d’une requête skyline donnée, en formulant des estimateurs présentant de bonnes propriétés statistiques(sans biais ou convergeant). Ensuite, il fournit deux approches différentes à l’optimisation des requêtes skyline. La première reposant sur un concept classique des bases de données qui est la dépendance fonctionnelle. La seconde se rapprochant des techniques de compression des données. Ces deux techniques trouvent leur place au sein de l’état de l’art comme le confortent les résultats expérimentaux.Nous abordons enfin la question de requêtes skyline au sein de données dynamiques en adaptant l’une de nos solutions précédentes dans cet intérêt.

To tackle the exploratory nature of science and the dynamic process involved in scientific analysis, dynamic workflows have been identified as an open challenge as they are subject to continuous adaptation and improvement. In particular, they require the ability of adapting a scientific workflow, at runtime, based on external events such as human interaction. Supporting dynamic iteration is an important step towards dynamic workflows since user interaction with a workflow is iterative. However, current support for iteration in scientific workflows is static and does not allow for runtime changes in data such as filter criteria or error thresholds. In this thesis, we propose an algebraic approach to support data-centric iteration in dynamic workflows and a dynamic execution model for these operators. We introduce the concept of iteration lineage so that provenance data management is consistent with dynamic changes in the workflow. Lineage also enables scientists to interact with workflow data and configuration at runtime through two steering algorithms implemented in Chiron. We evaluate our approach using real large-scale workflows on a large-scale environment. The results show execution time savings up to 24 days when compared to a traditional non-iterative workflow execution. We also perform complex queries for partial result analysis along the iterations and we assess the max overhead introduced by our iterative model as 3.63% of execution time. The performance of our proposed steering algorithms run in less than 1 millisecond in the worst-case scenario we measured., Para lidar com a natureza exploratória da ciência e o processo dinâmico envolvido nas análises científicas, os sistemas de gerência de workflows dinâmicos são essenciais. Entretanto, workflows dinâmicos são considerados como um desafio em aberto, devido à complexidade em gerenciar o workflow em contínua adaptação, em tempo de execução, por eventos externos como a intervenção humana. Apoiar iterações dinâmicas é um passo importante na direção dos workflows dinâmicos uma vez que a interação entre o usuário e o workflow é iterativa. Porém, o apoio existente para iterações em workflows científicos é estático e não permite mudanças, em tempo de execução, nos dados do workflow, como critérios de filtros e margens de erro. Nesta tese, propomos uma abordagem algébrica para dar apoio a iterações centradas em dados em workflows dinâmicos. Propomos o conceito de linhagem da iteração de forma que a gerência dos dados de proveniência seja consistente com as interações com o workflow. A linhagem também possibilita que os cientistas interajam com os dados do workflow por meio de dois algoritmos implementados no sistema de workflows Chiron. Avaliamos a nossa abordagem utilizando workflows reais em ambientes de execução em larga escala. Os resultados mostram melhorias no tempo de execução de até 24 dias quando comparado com uma abordagem tradicional não iterativa. Realizamos consultas complexas aos resultados parciais ao longo das iterações do workflow. A nossa abordagem introduz uma sobrecarga de no máximo 3,63% do tempo de execução. O tempo para executar os algoritmos de interação também é menor que 1 milissegundo no pior cenário avaliado.

Recommendation systems (RS) and P2P are both complementary in easing large-scale data sharing: RS to filter and personalize users' demands, and P2P to build de-centralized large-scale data sharing systems. However, many challenges need to be overcome when building scalable, reliable and efficient RS atop P2P. In this work, we focus on large-scale communities, where users rate the con-tents they explore, and store in their local workspace high quality content related to their topics of interest. Our goal then is to provide a novel and efficient P2P-RS for this context. We exploit users' topics of interest (automatically extracted from users' contents and ratings) and social data (friendship and trust) as parameters to construct and maintain a social P2P overlay, and generate recommendations. The thesis addresses several related issues. First, we focus on the design of a scalable P2P-RS, called P2Prec, by leveraging collaborative- and content-based filter-ing recommendation approaches. We then propose the construction and maintenance of a P2P dynamic overlay using different gossip protocols. Our performance experi-mentation results show that P2Prec has the ability to get good recall with acceptable query processing load and network traffic. Second, we consider a more complex in-frastructure in order to build and maintain a social P2P overlay, called F2Frec, which exploits social relationships between users. In this new infrastructure, we leverage content- and social-based filtering, in order to get a scalable P2P-RS that yields high quality and reliable recommendation results. Based on our extensive performance evaluation, we show that F2Frec increases recall, and the trust and confidence of the results with acceptable overhead. Finally, we describe our prototype of P2P-RS, which we developed to validate our proposal based on P2Prec and F2Frec., Les systèmes de recommandation (RS) et le pair-à-pair (P2) sont complémen-taires pour faciliter le partage de données à grande échelle: RS pour filtrer et person-naliser les requêtes des utilisateurs, et P2P pour construire des systèmes de partage de données décentralisés à grande échelle. Cependant, il reste beaucoup de difficultés pour construire des RS efficaces dans une infrastructure P2P. Dans cette thèse, nous considérons des communautés en ligne à grande échelle, où les utilisateurs notent les contenus qu'ils explorent et gardent dans leur espace de travail local les contenus de qualité pour leurs sujets d'intérêt. Notre objectif est de construire un P2P-RS efficace pour ce contexte. Nous exploitons les sujets d'intérêt des utilisateurs (extraits automatiquement des contenus et de leurs notes) et les don-nées sociales (amitié et confiance) afin de construire et maintenir un overlay P2P so-cial. La thèse traite de plusieurs problèmes. D'abord, nous nous concentrons sur la conception d'un P2P-RS qui passe à l'échelle, appelé P2Prec, en combinant les ap-proches de recommandation par filtrage collaboratif et par filtrage basé sur le contenu. Nous proposons alors de construire et maintenir un overlay P2P dynamique grâce à des protocoles de gossip. Nos résultats d'expérimentation montrent que P2Prec per-met d'obtenir un bon rappel avec une charge de requêtes et un trafic réseau accep-tables. Ensuite, nous considérons une infrastructure plus complexe afin de construire et maintenir un overlay P2P social, appelé F2Frec, qui exploite les relations sociales entre utilisateurs. Dans cette infrastructure, nous combinons les aspects filtrage par contenu et filtrage basé social, pour obtenir un P2P-RS qui fournit des résultats de qualité et fiables. A l'aide d'une évaluation de performances extensive, nous mon-trons que F2Frec améliore bien le rappel, ainsi que la confiance dans les résultats avec une surcharge acceptable. Enfin, nous décrivons notre prototype de P2P-RS que nous avons implémenté pour valider notre proposition basée sur P2Prec et F2Frec.

The increase in popularity of the XML format for representing data brought multiple challenges to the data management community, in particular concerning efficient query evaluation. At the same time, XML technologies are highly connected to distribution and data exchange, leading to the need for new distributed data management techniques. We present some results of our work on issues related to XML query processing. We first introduce a new language for describing materialized views, called XML Access Modules or XAMs, and a complete approach for XQuery evaluation based on XAM-specified views. We then discuss optimization techniques for ActiveXML, a language for the integration of distributed XML streams. Finally, we discuss architectures for handling large volumes of XML data on distributed hash tables, in the KadoP and ViP2P platforms developed in the Gemo group.; Nous présentons des travaux autour de la thématique de l'évaluation efficace de requêtes XML. Une première partie est liée à l'optimisation de l'accès aux données XML dans des bases de données centralisées. La deuxième partie considère des architectures distribuées à grande échelle pour le partage de données XML.