ARAÚJO NETO, Antônio Cavalcante. G2P-DBSCAN: Estratégia de Particionamento de Dados e de Processamento Distribuído fazer DBSCAN com MapReduce. 2016. 63 f. Dissertação (mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-03-22T19:21:02Z No. of bitstreams: 1 2016_dis_acaraujoneto.pdf: 5671232 bytes, checksum: ce91a85d087f63206ad938133c163560 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-04-25T12:33:12Z (GMT) No. of bitstreams: 1 2016_dis_acaraujoneto.pdf: 5671232 bytes, checksum: ce91a85d087f63206ad938133c163560 (MD5) / Made available in DSpace on 2016-04-25T12:33:12Z (GMT). No. of bitstreams: 1 2016_dis_acaraujoneto.pdf: 5671232 bytes, checksum: ce91a85d087f63206ad938133c163560 (MD5) Previous issue date: 2016 / Clustering is a data mining technique that brings together elements of a data set such so that the elements of a same group are more similar to each other than to those from other groups. This thesis studied the problem of processing the clustering based on density DBSCAN algorithm distributedly through the MapReduce paradigm. In the distributed processing it is important that the partitions are processed have approximately the same size, provided that the total of the processing time is limited by the time the node with a larger amount of data leads to complete the computation of data assigned to it. For this reason we also propose a data set partitioning strategy called G2P, which aims to distribute the data set in a balanced manner between partitions and takes into account the characteristics of DBSCAN algorithm. More Specifically, the G2P strategy uses grid and graph structures to assist in the division of space low density regions. Distributed DBSCAN the algorithm is done processing MapReduce two stages and an intermediate phase that identifies groupings that can were divided into more than one partition, called candidates from merging. The first MapReduce phase applies the algorithm DSBCAN the partitions individually. The second and checks correcting, if necessary, merge candidate clusters. Experiments using data sets demonstrate that true G2P-DBSCAN strategy overcomes the baseline adopted in all the scenarios, both at runtime and quality of obtained partitions. / Clusterizaçao é uma técnica de mineração de dados que agrupa elementos de um conjunto de dados de forma que os elementos que pertencem ao mesmo grupo são mais semelhantes entre si que entre elementos de outros grupos. Nesta dissertação nós estudamos o problema de processar o algoritmo de clusterização baseado em densidade DBSCAN de maneira distribuída através do paradigma MapReduce. Em processamentos distribuídos é importante que as partições de dados a serem processadas tenham tamanhos proximadamente iguais, uma vez que o tempo total de processamento é delimitado pelo tempo que o nó com uma maior quantidade de dados leva para finalizar a computação dos dados a ele atribuídos. Por essa razão nós também propomos uma estratégia de particionamento de dados, chamada G2P, que busca distribuir o conjunto de dados de forma balanceada entre as partições e que leva em consideração as características do algoritmo DBSCAN. Mais especificamente, a estratégia G2P usa estruturas de grade e grafo para auxiliar na divisão do espaço em regiões de baixa densidade. Já o processamento distribuído do algoritmo DBSCAN se dá por meio de duas fases de processamento MapReduce e uma fase intermediária que identifica clusters que podem ter sido divididos em mais de uma partição, chamados de candidatos à junção. A primeira fase de MapReduce aplica o algoritmo DSBCAN nas partições de dados individualmente, e a segunda verifica e corrige, caso necessário, os clusters candidatos à junção. Experimentos utilizando dados reais mostram que a estratégia G2P-DBSCAN se comporta melhor que a solução utilizada para comparação em todos os cenários considerados, tanto em tempo de execução quanto em qualidade das partições obtidas.

Resumo: Este trabalho apresenta um estudo comparativo sobre métodos de agrupamento, incluindo diferentes abordagens para segmentação de conjuntos de dados que utilizam métodos de agrupamento. As abordagens são baseadas nas duas técnicas de agrupamento mais populares, agrupamento particional e agrupamento hierárquico, e vêm introduzir heurísticas que, de alguma forma, levem à obtenção de um melhor resultado para o agrupamento. A partir das implementações de diversos métodos de agrupamento, este trabalho introduz uma nova heurística para a segmentação de imagens de profundidade por agrupamento, com o objetivo de melhorar o resultado da segmentação obtendo uma partição melhor para o agrupamento. A abordagem desenvolvida é baseada na extração de informações, para inicialização dos algoritmos de agrupamento, a partir de uma pré-segmentação da imagem usando deteção de bordas.

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / Clustering is a data mining technique that brings together elements of a data set such so that the elements of a same group are more similar to each other than to those from other groups. This thesis studied the problem of processing the clustering based on density DBSCAN algorithm distributedly through the MapReduce paradigm. In the distributed processing it is important that the partitions are processed have approximately the same size, provided that the total of the processing time is limited by the time the node with a larger amount of data leads to complete the computation of data assigned to it. For this reason we also propose a data set partitioning strategy called G2P, which aims to distribute the data set in a balanced manner between partitions and takes into account the characteristics of DBSCAN algorithm. More Specifically, the G2P strategy uses grid and graph structures to assist in the division of space low density regions. Distributed DBSCAN the algorithm is done processing MapReduce two stages and an intermediate phase that identifies groupings that can were divided into more than one partition, called candidates from merging. The first MapReduce phase applies the algorithm DSBCAN the partitions individually. The second and checks correcting, if necessary, merge candidate clusters. Experiments using data sets demonstrate that true G2P-DBSCAN strategy overcomes the baseline adopted in all the scenarios, both at runtime and quality of obtained partitions. / ClusterizaÃao à uma tÃcnica de mineraÃÃo de dados que agrupa elementos de um conjunto de dados de forma que os elementos que pertencem ao mesmo grupo sÃo mais semelhantes entre si que entre elementos de outros grupos. Nesta dissertaÃÃo nÃs estudamos o problema de processar o algoritmo de clusterizaÃÃo baseado em densidade DBSCAN de maneira distribuÃda atravÃs do paradigma MapReduce. Em processamentos distribuÃdos à importante que as partiÃÃes de dados a serem processadas tenham tamanhos proximadamente iguais, uma vez que o tempo total de processamento à delimitado pelo tempo que o nà com uma maior quantidade de dados leva para finalizar a computaÃÃo dos dados a ele atribuÃdos. Por essa razÃo nÃs tambÃm propomos uma estratÃgia de particionamento de dados, chamada G2P, que busca distribuir o conjunto de dados de forma balanceada entre as partiÃÃes e que leva em consideraÃÃo as caracterÃsticas do algoritmo DBSCAN. Mais especificamente, a estratÃgia G2P usa estruturas de grade e grafo para auxiliar na divisÃo do espaÃo em regiÃes de baixa densidade. Jà o processamento distribuÃdo do algoritmo DBSCAN se dà por meio de duas fases de processamento MapReduce e uma fase intermediÃria que identifica clusters que podem ter sido divididos em mais de uma partiÃÃo, chamados de candidatos à junÃÃo. A primeira fase de MapReduce aplica o algoritmo DSBCAN nas partiÃÃes de dados individualmente, e a segunda verifica e corrige, caso necessÃrio, os clusters candidatos à junÃÃo. Experimentos utilizando dados reais mostram que a estratÃgia G2P-DBSCAN se comporta melhor que a soluÃÃo utilizada para comparaÃÃo em todos os cenÃrios considerados, tanto em tempo de execuÃÃo quanto em qualidade das partiÃÃes obtidas.

Made available in DSpace on 2014-06-12T15:50:20Z (GMT). No. of bitstreams: 2 arquivo1962_1.pdf: 6205609 bytes, checksum: 86f9f23173b3ed39d6763c36b0c8bda9 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Nos últimos anos, assistimos um aumento do interesse pelo uso de FPGAs para aceleração de aplicações que apresentam desempenho limitado em software, devido à complexidade ou grande quantidade de dados a serem processados. Áreas como Processamento Digital de Sinais, Telecomunicações, Processamento de Imagens, Bioinformática e Computação Científica de Alto Desempenho têm tirado proveito desta tecnologia. Este interesse pode ser justificado por diversos fatores: As grandes melhorias introduzidas nos processos de microeletrônica que têm permitido a construção de FPGAs cada vez mais densos, capazes de comportar sistemas muito complexos com milhões de portas lógicas equivalentes. Além disso, estas melhorias têm permitido a construção de dispositivos que podem opera com freqüências de centenas de megahertz, permitindo implementações com altíssimo desempenho. Nos últimos anos, a velocidade dos processadores modernos se estabilizou na casa de 3GHz. Esta estagnação se deve, principalmente, a limitações na capacidade de dissipar o calor gerado em altas freqüências. Com isto, o atendimento das demandas por desempenho deve ser feito por meio da exploração de novas arquiteturas, que visem o paralelismo de tarefas, como são as arquiteturas de CPUs Multi-Cores e FPGAs. As implementações em FPGAs são capazes de realizar mais computação com menos consumo de energia, quando comparados a CPUs convencionais ou Multi-Cores. Isto cria vantagens estratégicas, pelo fato de que o consumo elevado de energia elétrica é um limitador para o aumento da capacidade de processamento em sistemas de alto desempenho, com impacto na viabilidade e custo de instalação, funcionamento e manutenção de sistemas. Sistemas Reconfiguráveis baseados em FPGAs correspondem, atualmente, a uma das arquiteturas alternativas que tem demonstrado bons desempenhos em diversas aplicações experimentais e em um número crescente de casos bem sucedidos de aplicações comerciais. Apesar destas vantagens e da alta capacidade de adaptação às aplicações, com exploração de paralelismo, o grande problema para a popularização do uso destes dispositivos está na dificuldade de programação a partir de descrições em alto nível, como C e C++. Em especial, o particionamento temporal das aplicações consiste em uma etapa fundamental para obtenção de qualidade da implementação. Este trabalho de Tese contribui para a redução da dificuldade de programação dos Sistemas de Computação Reconfiguráveis (SCR), propondo uma Metodologia de Particionamento Temporal que considera o reuso de componentes IP-Cores, escolhidos a partir de várias opções disponíveis em uma biblioteca de componentes, de forma a otimizar a utilização dos recursos do FPGA. Esta metodologia explora diversas possibilidades de implementação para as tarefas em hardware e diversos agrupamentos de tarefas em partições temporais. No melhor do nosso conhecimento, apenas dois métodos foram propostos na literatura, por Vemuri e Ouni, que tentam resolver os problemas de mapeamento de aplicação que são abordados. Entretanto, os resultados experimentais, descritos nesta Tese, demonstram as vantagens da nossa proposta. Além disso, a metodologia apresentada é a primeira, que tem-se notícia, que utiliza o método de busca Tabu Search para realização do particionamento temporal, integrado à escolha de componentes, a partir de uma biblioteca de IP-Cores

[pt] O problema de particionamento de grafos em cliques ocorre freqüentemente em diversas áreas tais como Ciências sociais, Ciências Econômicas, Biologia, Análise de Agrupamentos e em todas as áreas onde é necessário a classificação de elementos. Estuda-se aqui os principais algoritmos exatos e as principais heurísticas que constam na literatura. É feita uma análise do desempenho das heurísticas no pior caso e apresenta-se uma classe especial de problemas para os quais o seu desempenho é arbitrariamente ruim. Apresentam-se quatro novas heurísticas para o problema, duas delas baseadas nos métodos conhecidos por simulated anneling e por tabu search. Elas são comparadas entre si através da análise dos resultados de suas aplicações a problemas-teste, a problemas que ocorre na realidade e a classe de problemas especiais mencionada acima. / [en] The clique partitioning problem arise very often in many fields as Social Science, Economics, Biology, Cluster analysis and in all other fields that need a classification of elements. The main exact algorithms and heuristics that appear in the literature are studied. A especial class of instances of the clique partitioning problem for which the most comonly used heuristics perform arbitrarily bad is exhibited. Four new heuristics are presented and two of them are based on the known simulated anneling and tabu search methods. They are analised by their application to test-problems, real-life-problems and to the special class of instances mentioned above

Esta dissertação tem por objetivo apresentar uma abordagem baseada em técnicas de inteligência artificial para automatizar a etapa de particionamento de modelos em simulação distribuída. Essa abordagem utiliza os conceitos da computação evolutiva para o desenvolvimento de um algoritmo genético capaz de otimizar o processo de particionamento e auxiliar a tomada de decisões na tarefa de obtenção dos processos lógicos. Objetiva-se com sua aplicação minimizar o tempo de execução da simulação distribuída, evitando que o pior tempo de execução seja utilizado. Para alcançar esse objetivo, o particionamento apresentado como solução é caracterizado pelo balanceamento de carga e pela baixa latência de comunicação entre processos. Isso é possível porque o algoritmo genético utiliza informações contidas no modelo e na arquitetura de onde a simulação será executada. Esses padrões são utilizados para obter informações sobre a comunicação entre processos, a carga de processamento por centro de serviço e a capacidade de processamento das máquinas / This dissertation presents an approach based on intelligence artificial technics to automatize the model partitioning stage in distributed simulation. This approach makes uses evolutive computing concepts to developed a genetic algorithmic that can optimize the partitioning process and help to take decisions in the task to get the logical process. The propose of this algorithm is reduce to execution time the distributed simulation and to avoid the use of the worst execution time. To reach this target, the partitioning obtained has characteristics such as load balance and the low-communication interprocess. This is possible because the genetic algorithmic uses as input information from the model and the architect where the simulation with be executed. These inputs are used to get information about the interprocess communication, processing load per service center and processing capacity in the machines

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2013-07-16T01:05:17Z (GMT). No. of bitstreams: 1 213404.pdf: 1801799 bytes, checksum: d7472a645740185b751db6839980630e (MD5) / Neste trabalho é proposto um modelo linear de Fluxo em Redes para o problema de minimização de custos de produção e distribuição de Múltiplos Produtos Compostos. Neste modelo, restrições de acoplamento são consideradas para tratar a proporcionalidade existente entre os diversos fluxos que formam o produto composto, bem como as restrições de capacidade dos arcos pelos quais estes fluxos percorrem. A metodologia utilizada para solucionar o problema é baseada na estratégia de particionamento da matriz básica, e na implementação de uma especialização do método simplex dual para solucionar o problema particionado primal. Como solução inicial, é utilizada uma base construída por meio de um método heurístico que aloca fluxos em caminhos de custo mínimo. Para realização das operações de troca de base, a matriz ciclo é armazenada na forma produto da inversa, de modo a manter a esparsidade e a dimensão. Testes computacionais, contendo em torno de 200.000 restrições e 370.000 variáveis, aplicados à distribuição de produtos compostos de uma indústria do setor petroquímico, foram realizados com sucesso. Os resultados obtidos demonstram a eficiência computacional do algoritmo desenvolvido e a aplicabilidade do modelo formulado. Finalmente, recomendações são apresentadas para desenvolvimento de trabalhos futuros.

Esta dissertação tem por objetivo apresentar uma abordagem baseada em técnicas de inteligência artificial para automatizar a etapa de particionamento de modelos em simulação distribuída. Essa abordagem utiliza os conceitos da computação evolutiva para o desenvolvimento de um algoritmo genético capaz de otimizar o processo de particionamento e auxiliar a tomada de decisões na tarefa de obtenção dos processos lógicos. Objetiva-se com sua aplicação minimizar o tempo de execução da simulação distribuída, evitando que o pior tempo de execução seja utilizado. Para alcançar esse objetivo, o particionamento apresentado como solução é caracterizado pelo balanceamento de carga e pela baixa latência de comunicação entre processos. Isso é possível porque o algoritmo genético utiliza informações contidas no modelo e na arquitetura de onde a simulação será executada. Esses padrões são utilizados para obter informações sobre a comunicação entre processos, a carga de processamento por centro de serviço e a capacidade de processamento das máquinas / This dissertation presents an approach based on intelligence artificial technics to automatize the model partitioning stage in distributed simulation. This approach makes uses evolutive computing concepts to developed a genetic algorithmic that can optimize the partitioning process and help to take decisions in the task to get the logical process. The propose of this algorithm is reduce to execution time the distributed simulation and to avoid the use of the worst execution time. To reach this target, the partitioning obtained has characteristics such as load balance and the low-communication interprocess. This is possible because the genetic algorithmic uses as input information from the model and the architect where the simulation with be executed. These inputs are used to get information about the interprocess communication, processing load per service center and processing capacity in the machines

Orientador: Rahoma Sadeg Mohamed. / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Quimica / Made available in DSpace on 2018-07-26T18:59:21Z (GMT). No. of bitstreams: 1 Bernardo_Sergio_M.pdf: 6833714 bytes, checksum: 6c13c6f2afb52c3a75359803d1e039f9 (MD5) Previous issue date: 2000 / Resumo: A partição entre duas fases aquosas, contendo de 70 a 90% de água em cada fase, revelouse uma técnica adequada e conveniente para a purificação de biomoléculas, como aminoácidos e proteínas. Esta partição depende de diversos fatores: pH, massa molecular do polímero e temperatura. Recentemente, propôs-se a utilização de copolímeros do tipo bloco PEO-PPO-PEO para a fonnação de tais sistemas. O aumento da temperatura leva à auto-agregação destes copolímeros em micelas e à redistribuição das moléculas de água da fase contendo estes copolímeros, formando meios cujas características são ideais para a separação de biomoléculas hidrofóbicas. Este trabalho teve como objetivo obter dados experimentais sobre o comportamento de equilíbrio e a partição dos aminoácidos LTriptofano, L-Fenilalanina e L- Tirosina e da proteína Insulina Humana, em sistemas aquosos bifásicos (ATPS) contendo os polímeros PEG4600 e PEGIOOOO; os copolímeros F38, F68 e F88 e os sais de fosfato de potássio monobásico e dibásico, visando caracterizar os ATPS e identificar as variáveis tennodinâmicas que influenciam a partição das biomoléculas nestes sistemas. Os experimentos de partição foram organizados através de um planejamento fatorial, avaliando-se a influência das variáveis: temperatura (10, 25 e 40°C), pH (5, 7 e 9) e massa molecular dos polímeros e dos copolímeros no coeficiente de partição das biomoléculas acima citadas. Os resultados revelaram que a partição dos aminoácidos é influenciada pelo pH e pela temperatura, e que o L- Triptofano apresentou os maiores coeficientes de partição (K.=2,8) em relação aos demais aminoácidos, atribuído a sua maior característica hidrofóbica. A partição da molécula Insulina Humana também foi influenciada pela temperatura e pelo pH. Os valores altos dos coeficientes de partição da Insulina (K.=22) foram atribuídos às características dos copolímeros blocos. O estudo do comportamento de equilíbrio destes ATPS indicou que há um aumento na região bifásica com o aumento da concentração do sal de fosfato dibásico, representado pelo aumento do pH. Observou-se também que a composição global do sistema influencia o coeficiente de partição, obtendo-se um aumento nos valores de K com o aumento do comprimento da linha de amarração / Abstract: The partitioning between two aqueous phases, containing each phase ftom 70 to 90% of water, is considered a suitable and an appropriate technique for the purification of iomolecules like amino acids and proteins. This partitioning depends on different factors like pH, polymer molecular weight and temperature. Recently, the use of some types of copolymer PEO-PPO-PEO has been suggested in the formation of these systems. The increase in temperature origin the auto-aggregation of copolymers in micelles and the redistribution of the water molecules of the phase containing these copolymers, forming means which characteristics are ideaIs for a separation of hydrophobic biomolecules. The objective of this work was to obtain experimental data on the equilibrium behavior and partitioning of the amino acids L- Tryptophane, L-Phenylalanine and LTyrosine, and the protein Human Insulin, in Aqueous Two-Phase Systems (ATPS) containing polymers PEG4600 and PEGlOOOO, copolymers F38, F68 and F88 and salts such as monobasic and dibasic potassium phosphate, in order to identify the thermodynamics variables that influence on the biomolecules partitioning in these systems. The partitioning experiments were organized and carried out according to a Factorial Design Plan, evaluating the influence of the variables temperature (10, 25 and 40°C), pH ( 5, 7 and 9) and molecular weight of the polymer and copolymer in the biomolecules partition coefficients studied. Results showed that amino acids partitioning was influenced by pH and temperature. L-Tryptophane presented the highest partition coefficient (K=2,8) in comparison to other amino acids studied due to its higher hydrophobicity. The partition of the Human Insulin was also influenced by the temperature and pH. Human Insulin partition was found to be successful (K=22) which could be attributed to the use of copolymers blocks. The equilibrium behavior of these ATPS showed an increase in the two-phase region with the increase of the dibasic phosphate salt concentration due to the pH incremento Also was observed that the global composition of the system influence the partition coefficient, obtaining an increase the K values with the increasing of the tie line lengths, meaning an increasing in the copolymer proportion in the system / Mestrado / Engenharia de Processos / Mestre em Engenharia Química

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-27T17:11:09Z No. of bitstreams: 1 DANIEL CARDOSO DE SOUZA - TESE PPGEE 2006..pdf: 1923363 bytes, checksum: e0aa0e758bff14f247b303ddfe8d8f33 (MD5) / Made available in DSpace on 2018-07-27T17:11:09Z (GMT). No. of bitstreams: 1 DANIEL CARDOSO DE SOUZA - TESE PPGEE 2006..pdf: 1923363 bytes, checksum: e0aa0e758bff14f247b303ddfe8d8f33 (MD5) Previous issue date: 2006-12 / Capes / Este trabalho tem como objetivo propor um algoritmo de particionamento hardware/software otimizado. Trabalha-se com a hipótese de que algumas características específicas de certos algoritmos já publicados possam ser combinadas vantajosamente, levando ao aprimoramento de um algoritmo de particionamento de base, e conseqüentemente dos sistemas heterogêneos gerados por ele. O conjunto de otimizações propostas para serem realizadas nesse novo algoritmo consiste de: generalização das arquiteturas-alvo candidatas com a inclusão de FPGA’s para o particionamento, consideração precisa dos custos e potências das funções mapeadas em hardware, agendamento de sistemas com hardware reconfigurável dinamicamente, e consideração de múltiplas alternativas de implementação de um nó de aplicação em um mesmo processador. Essas otimizações são implementadas em sucessivas versões do algoritmo de particionamento proposto, que são testadas com duas aplicações de processamento de sinais. Os resultados do particionamento demonstram o efeito de cada otimização na qualidade do sistema heterogêneo obtido. / This work’s goal is to propose an optimized hardware/software partitioning algorithm. We work on the hypothesis that some specific features of certain published algorithms can be advantageously combined for the improvement of a base partitioning algorithm, and of its generated heterogeneous systems. The set of optimizations proposed for the achievement of this new algorithm encompass: generalization of candidate target architectures with the inclusion of FPGA’s for the partitioning, precise consideration of functions’ implementation costs and power consumptions in hardware, manipulation of systems with dynamically reconfigurable hardware, and consideration of multiple implementation alternatives for an application node in a given processor. These optimizations are implemented in successive versions of the proposed partitioning algorithm, which are tested with two signal processing applications. The partitioning results demonstrate the effect of each optimization on the achieved heterogeneous system quality. / Resumé: Cette thèse a pour but de proposer un algorithme de partitionnement matériel/logiciel optimisé. On travaille sur l’hypothèse de que quelques caractéristiques spécifiques à certains algorithmes déjà publiés puissent être combinées de façon avantageuse, menant à l’amélioration d’un algorithme de partitionnement de base et, par conséquence, des systèmes hétérogènes générés par cet algorithme. L’ensemble d’optimisations proposées pour être réalisées dans ce nouvel algorithme consiste en: généralisation des architecturescible candidates avec l’ajout de FPGA’s pour le partitionnement, considération précise des coûts et puissances des fonctions allouées en matériel, ordonnancement de systèmes au matériel dynamiquement reconfigurable, et prise en compte de plusieurs alternatives d’implémentation d’un noeud d’application dans un même processeur. Ces optimisations sont implémentées en versions successives de l’algorithme de partitionnement proposé, lesquelles sont testées avec deux applications de traitement du signal. Les résultats du partitionnement démontrent l’effet de chaque optimisation sur la qualité du système hétérogène obtenu.