Orientador : Prof. Dr. Eduardo Cunha de Almeida / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 26/02/2015 / Inclui referências / Resumo: MapReduce vem sendo utilizado amplamente na área de processamento de dados e Data Warehouse. Entre as muitas implementações do MapReduce disponíveis nos dias de hoje, o Apache Hadoop é o mais popular e possui código aberto. Hadoop também é usado amplamente como motor de muitos sistemas de processamento de consultas baseados em SQL, como o Apache Hive e PIG. Nesses sistemas, desenvolvedores podem processar consultas baseadas em SQL utilizando a escalabilidade do MapReduce. Neste contexto, desempenho e escalabilidade estão diretamente ligados aos parâmetros de configuração, que determinam o consumo de recursos e a eficiência do processamento. Hoje, as abordagens de ajuste de parâmetros analisam as tarefas durante sua execução e geram configurações de parâmetros baseadas em dados contidos em arquivos de log. Apesar de aumentar o desempenho, essa abordagem não é capaz de associar tarefas MapReduce similares para aplicar a configuração necessária. Assim, se tem dois problemas: (1) tarefas MapReduce recebem otimizações através de regras preestabelecidas sem se preocupar com a melhor alocação de recursos; (2) sequencias de tarefas MapReduce, como planos de consulta do Hive, recebem a mesma otimização mesmo que diferentes tarefas consumam diferentes recursos (problema nomeado de 'otimização uniforme'). A consequência de ambos os problemas _e a perda de desempenho, e o aumento do tempo de resposta e do consumo de recursos. Nesta dissertação apresenta-se uma abordagem que classifica tarefas MapReduce para aplicar otimizações através da similaridade de recursos automaticamente. Essa abordagem _e capaz de gerar grupos de tarefas que possuam consumo de recursos similares. Cada grupo criado _e associado a uma otimização específica que _e aplicada _as novas tarefas MapReduce. As duas principais contribuições são: (1) uma nova tarefa MapReduce recebe uma otimização apropriada sem a intervenção humana; (2) Tarefas de diferentes grupos recebem diferentes otimizações (abordagem chamada de 'otimização granular'). Experimentos mostram que nossa abordagem reduz o tempo de resposta em até 20% no melhor caso quando o benchmark TPC-H _e executado no Hive e Hadoop. Palavras-chave: Apache Hadoop, MapReduce, Otimização de Banco de Dados, Otimização Hive, Aprendizado de Máquina, Análise de Log / Abstract: MapReduce has been extensively used for data processing and analytics over the past years. Among the many MapReduce implementations available to date, the Apache Hadoop is one of the most popular due to its open source nature. Hadoop has been also used as data processing back-end by many SQL-like query processing systems, such as Apache Hive and PIG. In these systems, developers can leverage the declarative nature of query languages with the scalability of MapReduce processing. The scalability of Hadoop directly depends on proper performance tuning in order to squeeze computer resources for efficient data processing. To date, any Hadoop tuning approach relies on monitoring the execution of running programs for computing tuning setups based on execution data in log _les. While this approach can boost performance, it does not allow associating similar Hadoop programs to a similar tuning setup. This leads to two problems: (1) any upcoming program receives a single pre-computed tuning without any concern to what are the best computing resources to be allocated; (2) chains of running MapReduce programs, such as Hive query plans, tend to receive the same tuning setup, even if they eventually consume different computing resources (this problem is called 'uniform tuning'). The direct consequence of both problems is that they lead to poor performance, increase in response time and in resource consumption. This dissertation presents an approach for classifying MapReduce programs with similar resource consumption into groups. For each group, a specific tuning setup is associated that can be then re-applied to any upcoming program. This approach provides two main contributions: (1) an upcoming program receives a proper tuning on-the-y without human intervention; (2) programs from different groups receive different tuning setups (this approach is called '_ne-grained tuning'). Empirical experimentation shows that this approach reduces response time in 20% in the best case scenario when running the TPC-H benchmark on Hive and Hadoop. Keywords: Apache Hadoop, Apache Hive, MapReduce, Database Tuning, HiveQL Tuning, Machine Learning, Log Analysis

Orientador : Prof. André Luiz Pires Guedes / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 26/08/2004 / Inclui referências : f. 65-67 / Resumo: Esta dissertação apresenta e discute os dois recentemente descobertos algoritmos de teste de perfeição de grafos. A parte central dos dois algoritmos e a mesma. Este núcleo que os dois algoritmos compartilham, que certamente e a parte mais complexa dos mesmos, foi discutido detalhadamente e implementado. Ate o momento, o autor desta dissertação não tem notícias de outras implementações destes algoritmos. A apresentação do algoritmo foi dividida em três partes distintas. A primeira parte agrupa vários algoritmos que testam pela presença de subgrafos específicos. A segunda parte estuda em detalhes o núcleo que os dois algoritmos compartilham. A terceira parte apresenta os dois algoritmos de teste de perfeição de grafos propriamente ditos. Adicionalmente, nesta dissertação foram definidos quatro parâmetros que podem ser associados a um grafo para exprimir seu grau de imperfeição. Estes parâmetros foram denotados p 1, p2, p3 e p4. O autor relacionou estes parâmetros com algumas operações que podem ser aplicadas a um grafo imperfeito para torna-lo perfeito. As operações utilizadas para definir estes parâmetros de foram a remoção de arestas do grafo (pi), a inversão de arestas no grafo (p2), a execução de remoção e inserção de arestas no grafo (p 3) e, finalmente, a remoção de vértices do grafo (p4). Mostrou-se que para qualquer grafo temos p4 < p3 < p1 e p4 < p3 < p2. Alem disso foram apresentados exemplos de grafos em que cada uma destas desigualdades pode ser estrita. O autor apresentou também alguns limitantes inferiores e superiores para estes parâmetros. Finalmente, utilizando um dos limitantes inferiores para p4, mostrou-se que existem grafos que são "bastante imperfeitos" . Mais especificamente, foi demonstrado que existem grafos com n vértices para os quais o número de vértices que deve ser removido n para tornás-lo perfeitos é pelo menos --;- - - lg (2n ). lg (2n) Palavras-chave: teoria dos grafos, algoritmos, teoria algorítmica dos grafos, grafos perfeitos, otimização combinatória. / Abstract: This dissertation presents and discusses two recently discovered algorithms th a t test if a graph is perfect. The core shared by the two algorithms is discussed in details and the results of its implementation are presented. It is worthwhile to mention th a t no other similar implementation is known so far. The presentation of the algorithms is divided into three parts. The first part presents several algorithms th a t test some particular subgraphs. The second part reviews the core of the algorithms and the third part presents the two algorithms for perfectness. Additionally, in this work it is defined four parameters th a t can measure how imperfect a graph is. These parameters are denoted p1, p2, p3 and p4. The defined parameters are related to some operations th a t can be applied to a graph to make it perfect. The following operations are considered: edge deletion (pi), edge insertion (p2), both deletion and insertion of edges (p 3) and, finally, vertex deletion (p4). It is shown th a t for any graph it holds th a t p4 < p3 < p 1 and p4 < p3 < p2. It is also shown examples of graphs where such inequalities are strict. Finally, some lower bounds and upper bounds for these paramenters are shown. As a consequence of a lower bound for p4 , the author shows th a t there are "highly" imperfect graphs. More precisely, there are graphs with n vertices where n , . . Keywords: graph theory, algorithms, algorithmic graph theory, perfect graphs, combinatorial optimization.

Orientador : Carlos Alberto Maziero / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 11/08/2017 / Inclui referências : p. 73-75 / Resumo: As redes centradas na informação (Information-Centric Networking - ICN) representam uma abordagem para aprimorar a infraestrutura da Internet, introduzindo dados nomeados como primitiva de rede. Os conteúdos tornam-se independentes de localização, aplicação, armazenamento e meios de transporte, permitindo o armazenamento em cache. Os benefícios esperados são melhorias na segurança, escalabilidade e redução da utilização de banda. Os conteúdos são nomeados pelos seus publicadores e precisam ser assinados digitalmente para garantir a sua integridade e proveniência. Para assinar os conteúdos, o publicador precisa utilizar os recursos disponibilizados por um sistema de infraestrutura de chaves públicas. Uma vez assinado, o conteúdo é servido aos clientes que devem recuperar a chave pública correspondente para validá-lo. Essa chave deve estar de acordo com as regras impostas pelo modelo de confiança adotado e precisa ser válida, ou seja, não pode ter sido revogada. Uma vez que uma chave é revogada, é necessário notificar os seus usuários. Este trabalho apresenta uma abordagem de um serviço para divulgação do status das chaves utilizadas para validação dos conteúdos. Este trabalho propõe um serviço distribuído e atualizado por replicação, visando melhorar sua robustez e diminuir o tempo necessário à propagação da informação do status das chaves na rede. Os principais resultados mostram que o serviço proposto pode reduzir significativamente o tempo de recuperação do status da chave, refletindo o estado atual do certificado. Os resultados também apontam que quando o consumidor recupera as informações de status da chave pelo serviço de consulta em vez do cache, ele obtém uma informação mais precisa. Palavras-chave: Segurança, Redes Centradas em Informações, Revogação de chaves. / Abstract: The Information Centric Networks (ICN) is an approach to improve the Internet infrastructure, introducing data named as network primitive. The contents are independent of location, application, transport, allowing the storage in cache. The expected benefits are improvements in security, scalability, and reduced bandwidth usage. The contents are named by their publishers and must be digitally signed to ensure their provenance. To sign the contents the publisher must use the resources provided by a public key infrastructure system. Once signed, the content is offered to customers, which should retrive the corresponding public key to validate it. This key must be valid in conformity with the rules enforced by the trust model and must be valid, i.e. it should not have been revoked. Once a key is revoked, its users should be notified. This paper proposes a service approach to disseminate key status information of the keys used to validate the contents. Main results shows that the proposed service is able to significantly reduce key status retrieval time, reflecting the actual state of the certificate. When the consumer retrieves the key status information by our query service instead of the cache, it gets a more accurate information. Keywords: Security, Information Centric Networking, Key Revocation.

Orientador : Prof. Dr. Marcos Sfair Sunye / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 05/07/2016 / Inclui referências : f. 59-64 / Resumo: A agregação da produção científica em um único ambiente digital institucional permite às instituições gerar indicadores internos de produção científica e tecnológica, realizar estudos através da aplicação de ferramentas de mineração de dados, bem como apoiar a implementação de políticas de gestão. Embora as instituições acadêmicas sejam as grandes produtoras de conhecimento científico, enfrentam dificuldades para identificar, agregar e quantificar o próprio conhecimento produzido em seus ambientes digitais e, por conseguinte definirem critérios precisos para planejamento e distribuição de recursos que fomentem a produção científica por parte de seu corpo docente. Este trabalho apresenta uma metodologia para carga automática de metadados e artigos científicos disponibilizados em acesso aberto e dispersos em periódicos científicos, em Repositórios Digitais Institucionais obtidos por meio de extração de dados contidos nos currículos dos docentes da Universidade Federal do Paraná, registrados na Plataforma Lattes, além de auxiliar a instituição no planejamento dos custos necessários para manutenção de seu ambiente digital, através da obtenção do volume de produção científica a ser armazenado em seu repositório digital institucional. Para efeito da implementação da proposta foi desenvolvido um conjunto de componentes para mineração de artigos científicos produzidos e disponibilizados em acesso aberto na plataforma DSpace. Palavras-chave: Acesso aberto. Colheita automatizada. Metadados. Mineração de dados. Publicações científicas. Repositórios digitais. / Abstract: The aggregation of scientific production in a single institutional digital environment allows institutions to generate internal indicators of scientific and technological production, conduct studies through the application of data mining tools as well as support the implementation of management policies. Although the academic instituitons have been the great cientific knowledge generators, they face dificulties in identifying, aggregating and quantifying their knowledge in their digital environments, and as a consequence to define precise criteria for planning and distributing resources that to encourage the cientific production by their researchers. This work proposes a methodology for the automatic loading of metadata and open access scientific articles, spread out in scientific journals in Institutional Digital Repositories, obtained through extraction of data contained in the curricula registered in the Lattes Platform of teachers of Federal University of Paraná. A further objective is to assist the institution for planning the costs required to maintain their digital environment by obtaining the volume of scientific production to be stored in its institutional digital repository. For the purpose of implementation, a set of components was developed for data mining of scientific articles produced and made available in open access on DSpace. Keywords: Automated harvesting. Data mining. Digital repositories. Metadata. Open access. Scientific publications.

Orientador : Prof. Dr. Fabiano Silva / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 31/08/2016 / Inclui referências : f. 63-67 / Resumo: Raciocínio baseado em Casos (CBR) e um método para resolver problemas com recuperação de solucões para problemas anteriores. CBR demanda uma representacão de conhecimento que permite o resolvedor a buscar casos similareas atraves de uma pergunta e a taxa de similaridade e dado pela distancia em uma estrutura de arvore, uma ontologia. O objetivo da presente pesquisa e utilizar CBR como uma ferramenta pedagógica atraves de quatro pilares: Raciocínio Baseado em Casos, Representacao de conhecimento, Informatica Educacional e a mediacao do erro na educacao. Considera-se erro como uma questao de importancia no desenvolvimento pedagogico, entao isso deve ser mediado. A mediacao de erro e utilizada como um guia para uma classificaçao quantitativa de exercícios, levando em consideraçao quantas vezes um exercício foi respondido erroneamente, a distancia entre os exercícios da suas similaridades. Esse tipo de classificacao automatica para exercícios em sistemas de apoio educacional e uma das principais contribuições dessa pesquisa. Este trabalho sugere que o ciclo CBR e profícuo no desenvolvimento de uma ferramenta para criaçao automatica de exames. Palavras-chave: raciocínio baseado em casos, mediacao por erros, representacao do conhecimento, informatica educacional. / Abstract: Case-based Reasoning (CBR) is a method for solving problems with similar retained solutions. CBR demands a knowledge representation that allows the reasoner to find similar cases by a query and the similarity rate is given by a distance in hierarchical tree structure, an ontology. The main goal of this research is to use CBR as a pedagogical tool supported by three pillars: Case-based reasoning, Knowledge representation and Error Mediation in Education. It is considered that the error has a role of importance in the pedagogical development, so it has to be mediated. The error mediation is used as a rule for a quantitative way of exercises classification, it takes into account how many times an exercise have been uncorrected answered, the distance between exercises gives the similarity between them. This kind of automatically classification for exercises in a educational support systems is one of the main contributions of this research. This work suggests that the CBR cycle is useful in the designing of a tool for automatic creation of exams. Keywords: case-based reasoning, error mediation, knowlodge representation, educational informatics.

Orientador : Prof. Dr. Daniel Weingaertner / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 10/08/2016 / Inclui referências : f. 59-62 / Área de concentração: Ciência da computação / Resumo: A crescente importância do uso de GPUs para computação de propósito geral em supercomputadores faz com que o bom suporte a GPUs seja uma característica valiosa de frameworks de software para computação de alto desempenho como o waLBerla. waLBerla é um framework de software altamente paralelo que suporta uma ampla gama de fenômenos físicos. Embora apresente um bom desempenho em CPUs, testes demonstraram que as suas soluções de comunicação para GPU têm um desempenho ruim. Neste trabalho são apresentadas soluções para melhorar o desempenho, a eficiência do uso de memória e a usabilidade do waLBerla em supercomputadores baseados em GPU. A infraestrutura de comunicação proposta para GPUs NVIDIA com suporte a CUDA mostrou-se 25 vezes mais rápida do que o mecanismo de comunicação para GPU disponíveis anteriormente no waLBerla. Nossa solução para melhorar a eficiência do uso de memória da GPU permite usar 55% da memória necessária por uma abordagem simplista, o que possibilita executar simulações com domínios maiores ou usar menos GPUs para um determinado tamanho de domínio. Adicionalmente, levando-se em consideração que o desempenho de kernels CUDA se mostrou altamente sensível ao modo como a memória da GPU é acessada e a detalhes de implementação, foi proposto um mecanismo de indexação flexível de domínio que permite configurar as dimensões dos blocos de threads. Além disso, uma aplicação do Lattice Boltzmann Method (LBM) foi desenvolvida com kernels CUDA altamente otimizados a fim de se realizar todos os experimentos e testar todas as soluções propostas para o waLBerla. Palavras-chave: HPC, GPU, CUDA, Comunicação, Memória, Lattice Boltzmann Method, waLBerla. / Abstract: The increasing importance of GPUs for general-purpose computation on supercomputers makes a good GPU support by High-Performance Computing (HPC) software frameworks such as waLBerla a valuable feature. waLBerla is a massively parallel software framework that supports a wide range of physical phenomena. Although it presents good performance on CPUs, tests have shown that its available GPU communication solutions perform poorly. In this work, we present solutions for improving waLBerla's performance, memory usage e_ciency and usability on GPUbased supercomputers. The proposed communication infrastructure for CUDA-enabled NVIDIA GPUs executed 25 times faster than the GPU communication mechanism previously available on waLBerla. Our solution for improving GPU memory usage e_ciency allowed for using 55% of the memory required by a naive approach, which makes possible for running simulations with larger domains or using fewer GPUs for a given domain size. In addition, as CUDA kernel performance showed to be very sensitive to the way data is accessed in GPU memory and kernel implementation details, we proposed a flexible domain indexing mechanism that allows for configuring thread block sizes. Finally, a Lattice Boltzmann Method (LBM) application was developed with highly optimized CUDA kernels in order to carry out all experiments and test all proposed solutions for waLBerla. Keywords: HPC, GPU, CUDA, Communication, Memory, Lattice Boltzmann Method, waLBerla.

Orientadora : Profª Drª Silvia Regina Vergílio / Co-orientadora : Profª Drª Thelma Elita Colanzi Lopes / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 23/10/2014 / Inclui referências / Resumo: O projeto da Arquitetura de Linha de Produto (PLA) é uma tarefa complexa, influenciada por diversos fatores, como por exemplo, a modularização de características e a extensibilidade da PLA. Tais fatores, muitas vezes, são avaliados de acordo com diferentes métricas. Dessa forma, o projeto de PLA pode ser visto como um problema de otimização e tal categoria de problema vem sendo resolvida com sucesso em um campo de pesquisa chamado Search Based Software Engineering (SBSE), fazendo uso de meta-heurísticas como Algoritmos Genéticos. Diante deste fato, Colanzi [16] propôs uma abordagem chamada Multi-Objective Approach for Product-Line Architecture Design (MOA4PLA), a qual é implementada pela ferramenta denominada OPLA-Tool (Optimization for PLA Tool). Tal ferramenta é constituída de diferentes módulos, dentre estes, apenas um foi implementado por Colanzi [16]. Este trabalho implementa outros três módulos essenciais da ferramenta OPLA-Tool, que tornam a utilização da abordagem possível na prática: OPLA-Encoding, OPLA-Decoding e OPLA-GUI. Tais módulos fornecem recursos que automatizam diversas atividades da abordagem MOA4PLA, como por exemplo, leitura e instanciação de uma arquitetura em memória, geração das soluções encontradas para que seja possível sua visualização e uma interface gráfica, tornando seu uso mais produtivo. A implementação e integração de tais módulos foram avaliadas utilizando PLAs reais, os resultados obtidos mostram a utilidade da OPLA-Tool, que contribui para a redução de esforço em projetos de PLA e para a melhoria das mesmas. Palavras-chave: Ferramenta de Suporte; Arquitetura de Linha de Produto; Algoritmos Evolutivos Multiobjetivos. / Abstract: The design of Product Line Architecture (PLA) is a complex task, which is influenced by several factors, such as feature modularization and PLA extensibility. Such factors are often evaluated according to different types of metrics. Thus, the PLA design can be seen as an optimization problem. This category of problem has been successfully solved in the research field named Search Based Software Engineering (SBSE) that uses metaheuristics, such as Genetic Algorithms. In this context, Colanzi [16] proposed an approach named Multi-Objective Approach for Product-Line Architecture Design (MOA4PLA), to be supported by a tool named OPLA-Tool (Optimization for PLA Tool). This tool is composed by different modules and only one of these modules has been implemented in [16]. This work implements three essential modules of OPLA-Tool, which offer automated support to allow the use of MOA4PLA in practice: OPLA-Encoding, OPLA-Decoding and OPLAGUI. Such modules provide features that automate many tasks of MOA4PLA approach, such as reading and instantiation of a PLA in memory, generation of solutions in order to be possible their visualization, and a graphical interface, making the use of MOA4PLA more productive. The implementation and integration of such modules were evaluated using real PLAs. The obtained results show the usefulness of OPLA-Tool, which contributes to reduce the effort spent in the PLA design and improvement. Keywords: Tool Support; Product Line Architecture Design; Multi-objective Evolutionary Algorithms

Orientador : Prof. Dr. Eduardo Todt / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 30/08/2017 / Inclui referências : f. 115-124 / Resumo: Detectores de Ponto de Interesse (POI) são partes fundamentais de um Sistema Visual de Mapeamento e Localização Simultâneos (VSLAM). Pontos de interesse na imagem são usados pela odometria visual para estimar o deslocamento de um robô por meio do movimento de câmera. Além disso, o robô pode reconhecer lugares já visitados pela correspondência de pontos de interesse entre imagens. Avaliar a qualidade destes detectores no sentido de determinar qual o melhor para ser utilizado em determinado ambiente, é de extrema importância ao VSLAM, pois a qualidade do mapa gerado pelo sistema depende de robustos pontos de interesse encontrados nas imagens. Um novo detector de pontos de interesse conhecido como IGFTT apresenta resultados promissores em relação aos métodos clássicos como SURF, SIFT, ORB e outros. O presente trabalho avalia o novo algoritmo de detecção de pontos de interesse IGFTT em função do desempenho de um sistema Visual SLAM, comparando-o com os detectores mais populares na comunidade acadêmica como o SIFT, SURF, FAST, AGAST, GFTT, entre outros. É utilizada uma base pública como benchmark em conjunto com um sistema de VSLAM de código aberto. A qualidade do detector é determinada em função do mapa gerado pelo VSLAM, do tempo de processamento, da taxa de repetibilidade dos pontos de interesse, da probabilidade de sobrevivência destes em frames futuros e da quantidade de nós sucessivos no grafo de cena. Os testes demonstram as qualidades e as deficiências do algoritmo IGFTT. Os resultados de cada detector para cada teste são ranqueados de forma global e demonstram a acurácia geral dos algoritmos. No ranking obtido, SURF apresenta-se em primeiro lugar, em segundo lugar o IGFTT2, melhoria do algoritmo testado, e em terceiro o IGFTT. A acurácia do detector é definida pelo Erro da Trajetória Absoluta e apresenta o algoritmo GFTT com 0,278 metros de erro obtendo o melhor resultado e IGFTT, o pior resultado com 0,944 metros de erro, e o algoritmo IGFTT2 obteve um erro de 0,712 metros. Em tempo de processamento por frame nas fases de detecção, descrição e correspondência dos pontos de interesse, IGFTT obteve o melhor desempenho consumindo em média 52,1 milissegundos, demonstrando ser extremamente rápido. IGFTT alcançou a segunda melhor colocação em relação a taxa de repetibilidade e probabilidade dos POIs, atrás do SURF. E quanto à taxa de nós do grafo de cena em sequência, IGFTT obteve o melhor resultado com 47,07%. SURF conseguiu uma taxa de 39,30% porém destes, somente 1,33% não tiveram poses atribuídas pelo sistema RGBDSLAM. De forma geral, o detector de pontos de interesse IGFTT é veloz em termos de tempo de processamento e estável, dada dispersão dos seus resultados conforme variedade de sequências sob testes. Palavras-chave: Detectores de Pontos de Interesse, Odometria Visual, Visual SLAM, Avaliação de Detectores de Pontos de Interesse. / Abstract: Keypoints Detectors are fundamental parts of a Visual Simultaneous Localization and Mapping System or VSLAM. Keypoints in the image are used by visual odometry to estimate the displacement of a robot by means of camera movement. Furthermore, the robot can recognize places already visited by matching keypoints between images. To evaluate the quality of these detectors in order to determine the best to be used in a particular environment, it is of extreme importance to SLAM, since the quality of the map generated by the system depends on robust keypoints found in the images. The present work evaluates the new algorithm of keypoints detection IGFTT as a function of the performance of a Visual SLAM system, comparing it with the most popular detectors in the academic community such as SIFT, SURF, FAST, AGAST, GFTT, among others. A public database is used as a benchmark in conjunction with an open source VSLAM system. The quality of the detector is determined by the VSLAM generated map, runtime processing, keypoints repeatability rate, they survival probability rate in future frames and the number of successive nodes in the scene graph. The tests demonstrate the qualities and shortcomings of the IGFTT algorithm. The results of each detector for each test are globally ranked and demonstrate the overall accuracy of the algorithms. In the obtained ranking, SURF presents first, secondly the IGFTT2, improvement of the algorithm tested, and thirdly the IGFTT. The accuracy of the detector is defined by the Absolute Trajectory Error and presents the GFTT algorithm with 0.278 meters of error obtaining the best result and IGFTT, the worst result with 0.944 meters of error, and IGFTT2 algorithm obtained an error of 0.712 meters. In runtime processing per frame in the phases of detection, description and correspondence of keypoints, IGFTT obtained the best performance consuming in average 52.1 milliseconds, proving to be extremely fast. IGFTT achieved the second best placement in relation to the repeatability and probability rate of POIs, behind SURF. As for the node rate of the scene graph in sequence, IGFTT obtained the best result with 47.07%. SURF achieved a rate of 39.30% but of these, only 1.33% had no poses attributed by the system RGBDSLAM. In general, the IGFTT keypoint detector is fast in terms of time processing and stable, given its dispersion of results according to the variety of sequences under test. Keywords: Keypoints Detectors, Visual Odometry, Visual SLAM, Keypoints Detectors Evaluation.

Orientador : Prof. Aldri Luiz dos Santos / Co-orientadora : Profª. Michele Nogueira Lima / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 18/08/2014 / Inclui referências / Resumo: A Internet das coisas (IoT) é fruto de uma revolução tecnológica que representa o futuro da computação e da comunicação, sendo identificada como uma das tecnologias emergentes que mudará nossa forma de vida. As redes IoT são formadas por objetos heterogêneos (nós) com alguma inteligência, isto é, com capacidade de processamento que lhes permitem, entre outras tarefas, enviar e receber informações através da rede. Entretanto, cada vez mais objetos estarão interligados com aparelhos digitais, veículos e demais, e a presença deles tende a crescer em nossas vidas trazendo mais comodidade e facilidade. A IoT ligará todos esses objetos, assim como ligará outros que não pertencem à computação podendo ser fixos ou móveis. Visto que os objetos que compõem a IoT possuem recursos limitados, estes se tornarão vulneráveis a vários tipos de ataques, sendo o ataque sinkhole um dos mais destrutivos nas redes. Contudo, as soluções existentes para a proteção e segurança contra os ataques sinkhole geram um elevado consumo de recursos e usam mecanismos complexos para garantir um bom desempenho. Desta forma, este trabalho propõe um sistema de detecção de intrusão, chamado de INTI (Detecção Intrução contra ataques SiNkhole sobre 6LoWPAN para a InterneT das CoIsas) para identificar a presença de ataques sinkhole no serviço de roteamento na IoT. Além disso, INTI visa mitigar os efeitos adversos encontrados em IDSs que perturbam o seu desempenho como falsos positivos e negativos, também como os elevados consumos de recursos. O INTI combina o uso dos mecanismos como o uso de watchdog, reputação e confiança. O mecanismo de watchdog possibilita o monitoramento das atividades dos outros nós durante o encaminhamento de pacotes. A reputação e a confiança colaboram para determinar os dispositivos considerados confiáveis e não confiáveis na rede IoT. Estes mecanismos são utilizados para a detecção de ataques sinkhole, analisando o comportamento dos dispositivos. O sistema INTI foi avaliado em dois cenários realísticos de IoT, e nesses cenários os resultados obtidos mostram a eficácia do INTI em termos de taxa de detecção de ataques, o número de falsos negativos e falsos positivos e da eficiência na taxa de entrega, na latência e no consumo de energia. Palavras-chave: IDS, IoT, segurança, proteção, ataques sinkhole, watchdog, reputação. / Abstract: The Internet of Things (IoT) is the result of a technological revolution that represents the future of computing and communication, being identified as one of the emerging technologies that will change our way of life. The IoT networks are formed by heterogeneous objects (nodes) with some intelligence, that is, with processing capabilities that enable them, among other tasks, send and receive information across the network. However, more and more objects are interconnected with digital devices, vehicles and other equipment, and their presence tends to grow in our lives bringing more convenience and ease. The IoT will connect all of these devices as well as bind other objects that do not belong to the digital world and that can be fixed or mobile. Since the objects that make up the IoT have limited resources, they become vulnerable to various attacks, and the sinkhole attack is one of the most destructive in the networks. However, existing solutions for the protection and security against sinkhole attacks generate a high consumption of resources and use complex mechanisms to ensure good performance. Thus, this dissertation proposes an intrusion detection system, called INTI (intrusion detection against sinkhole attacks on 6LoWPAN for IoT), to identify the presence of sinkhole attacks on the routing services in IoT. Moreover, INTI aims to mitigate adverse effects found in IDS that disturb its performance, suck as false positive and negative as well as the high resource cost. The INTI system combines the use of mechanisms such as watchdog, reputation and trust. The watchdog mechanism enables the monitoring the activities of other nodes for packet forwarding. The reputation and trust mechanisms collaborate to determine the devices considered reliable and unreliable in IoT network.These mechanisms are used for detection of attackers, by analyzing the behavior of devices. The INTI system was evaluated in two realistic scenarios of IoT, and these scenarios the results show the effectiveness of INTI in terms of attack detection rate, the number of false negatives and false positives and efficiency in the delivery rate, latency and energy consumption. Keywords: IDS, IoT, security, safety, sinkhole attacks, watchdog, reputation.

Orientador : Prof. Dr. Luiz Carlos Pessoa Albini / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 22/08/2014 / Inclui referências / Resumo: As redes tolerantes a atrasos e desconexões (DTN) são formadas por nos moveis ad hoc cujas características de mobilidade impõem serias restrições para o encaminhamento e entrega de mensagens. Uma característica importante das DTNs e a conectividade intermitente, resultado das frequentes desconexões causadas pela mobilidade e topologia esparsa. Nesses cenários, a entrega de mensagens torna-se um desafio, pois elas podem ser retidas por longos períodos ou nunca serem entregues ao destinatário. As propostas existentes para melhorar a taxa de entrega de mensagens nesses cenários alteram os protocolos de roteamento, fazendo verifica.ao de integridade a cada salto. Isso resulta em sobrecarga no roteamento e em um custo computacional muitas vezes impraticável. Este trabalho propõe um esquema, denominado EMCOD, que visa reduzir o tempo para entrega de mensagens e a sobrecarga de processamento, em redes caracterizadas por longos atrasos e que sofrem perdas de pacotes. O esquema utiliza codificação de rede e intercalação de dados para criação de mensagens menores que são encaminhadas pela rede. A reconstrução dos dados originais e feita a partir da recepção de algumas mensagens, não sendo necessário aguardar o recebimento de todas. Utilizando Reed-Solomon para codificação de dados, o EMCOD .e capaz de reduzir o tempo para recuperação dos dados originais em mais de 50%, em cenários que sofrem altas taxas de perdas de pacotes. A sobrecarga computacional adicionada pelo processo de codificação e compensada pela capacidade de recuperação dos dados originais, sem que seja necessário reenviar as mensagens perdidas. Devido a essa capacidade, e possível reduzir a sobrecarga na rede em mais de 60%, em cenários que possuem altos índices de perda de mensagens. O EMCOD altera a estrutura da camada de Agregação, mas não interfere no funcionamento das demais camadas. Assim, e possível realizar o roteamento das mensagens através de nos que não implementem o esquema proposto. Palavras-chave: DTN, codificação de rede, redução de tempo, baixa sobrecarga. / Abstract: Delay and Disruption Tolerant Networks (DTN) are made up of mobile ad hoc nodes, and it is exactly that mobility that imposes major message routing and delivery restrictions. Another important characteristic of DTNs is its intermittent connectivity, resulting from frequent disconnections, which in turn are caused by mobility and scattered topologies. In these scenarios, message delivery becomes a challenge, considering they can be detained for long periods or never get delivered to its destination. Existing solutions to improve message delivery rates in such scenarios modify routing protocols to perform integrity verification with each hop. This results in routing overloads and, too often, unrealistic processing costs. This research proposes a schema, named EMCOD, that decreases message delivery times, and also minimizes processing overloads in networks burdened by long delays and packet losses. The schema uses data encoding and interleaving to create smaller messages, which are then routed through the network. The original data is then reassembled from some of the messages received, without the need to wait for the retrieval of all messages. Using Reed-Solomon codes to encode the data, EMCOD is capable of reducing original data retrieval times by more than 50%, in scenarios with high packet loss rates. The processing overload resulting from the encoding procedures is offset by the data retrieval capabilities, without the need to resend lost messages. This capability effectively decreases network overloads by more than 60%, in scenarios subject to high message loss rates. EMCOD modifies the structure of the Bundle Layer, without interfering with the remaining layers, making it possible to route the messages through nodes that don’t implement the proposed schema. Keywords: DTN, network encoding, time reduction, low overhead.