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.

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.

Submitted by admin tede (tede@pucgoias.edu.br) on 2017-11-22T13:39:54Z No. of bitstreams: 1 André Luiz Alves.pdf: 760209 bytes, checksum: 09b516d6ffcca2c7f66578b275613b36 (MD5) / Made available in DSpace on 2017-11-22T13:39:54Z (GMT). No. of bitstreams: 1 André Luiz Alves.pdf: 760209 bytes, checksum: 09b516d6ffcca2c7f66578b275613b36 (MD5) Previous issue date: 2017-09-22 / The objective of this work is to compare a proposed algorithm based on the RANdom SAmple Consensus (RANSAC) method for selection of samples, selection of variables and simultaneous selection of samples and variables with the Sucessive Projections Algorithm (SPA) from a chemical data set in the context of multivariate calibration. The proposed method is based on the RANSAC method and Multiple Linear Regression (MLR). The predictive capacity of the models is measured using the Root Mean Square Error of Prediction (RMSEP). The results allow to conclude that the Successive Projection Algorithm improves the predictive capacity of Ransac. It is concluded that the SPA positively influences the Ransac algorithm for selection of samples, for selection of variables and also for simultaneous selection of samples and variables. / O objetivo do trabalho é comparar um algoritmo proposto baseado no método consenso de amostra aleatória (RANdom SAmple Consensus, RANSAC) para seleção de amostras, seleção de variáveis e seleção simultânea de amostras e variáveis com o algoritmo de projeções sucessivas (Sucessive Projections Algorithm, SPA) a partir de conjuntos de dados químicos no contexto da calibração multivariada. O método proposto é baseado no método RANSAC e regressão linear múltipla (Multiple Linear Regression, MLR). A capacidade preditiva dos modelos é medida empregando o erro de previsão da raiz quadrada do erro quadrático médio (Root Mean Square Error Of Prediction, RMSEP). Os resultados permitem concluir que o Algoritmo das Projeções Sucessivas melhora a capacidade preditiva do Ransac. Conclui-se que o SPA influi positivamente no algoritmo Ransac para seleção de amostras, para seleção de variáveis e também para seleção simultânea de amostras e variáveis.

Esta tese apresenta a arquitetura de um sistema de aprendizado, com um escalonador de tarefas que possibilita a utilização de vários métodos de classificação e validação, permitindo a distribuição dessas tarefas entre os módulos do sistema. Esta arquitetura está estruturada de forma que classificações obtidas através de uma técnica sejam reutilizadas em paralelo pelo mesmo algoritmo ou por outras técnicas, produzindo novas classificações através do refinamento dos resultados alcançados e ampliando o uso em bases de dados com características diferentes. O sistema foi estruturado em quatro partes denominadas, respectivamente, Módulo de Inicialização, Módulo de Validação, Módulo de Refinamento e Módulo Especial de Escalonamento. Em cada módulo, podem ser usados vários algoritmos para atender aos seus objetivos. A estrutura deste sistema permite sua configuração, utilizando diversos métodos, inclusive com técnicas de inteligência artificial. Com isso, é possível a obtenção de resultados mais precisos por meio da escolha do melhor método para cada caso. Os resultados apresentados neste trabalho foram obtidos a partir de bases conhecidas na literatura, o que possibilita comparar as implementações dos métodos tradicionais que foram adicionadas ao sistema e, principalmente, verificar a qualidade dos refinamentos produzidos pela integração de técnicas diferentes. Os resultados demonstram que através de um sistema de aprendizado, minimiza-se a complexidade na análise de grandes bases de dados, permitindo verificar bases com estruturas diferentes e aumentar os métodos aplicados na análise de cada estrutura. Isto favorece a comparação entre os métodos e proporciona resultados mais confiáveis. Para uniformizar os dados provenientes de bases distintas, foi elaborada a modelagem de dados do sistema, o que favorece a escalabilidade do sistema de maneira uniforme. / This thesis presents the architecture of a System Learning with a task scheduler, which makes possible the utilization of several classification and validation methods, allowing the distribution of tasks between the module systems. This architecture is structured of such way that the classifications obtained through a specific technique can be reutilized in parallel by the same algorithm or by other techniques, producing new classifications through the refinement of the results achieved and expanding the use in databases with different characteristics. The system was structured in four parts denominated, respectively, Initialization module; Validation module; Refinement module; and Especial scheduling module. In each module, various algorithms can be employed to reach its objectives. The structure of this system allows its configuration, utilizing various methods, including artificial intelligence techniques. Thus, it is possible to obtain more precise results through the choice of the best method to each case. The results presented in this work were obtained from basis that are known in the literature, which allows to compare the implementations of the traditional methods that were added to the system and, especially, to verify the quality of the refinements produced by the integration of different techniques. The results demonstrated that through a learning system, the complexity of the analysis of great databases is minimized, allowing to verify basis with different structures and to increase the methods applied in the analysis of each structure. It favors the comparison between the methodologies and provides more reliable results. To standardize the data originated of distinct bases, the data modelling system was elaborated, which will favor the uniform scalability of the system.

Esta tese apresenta a arquitetura de um sistema de aprendizado, com um escalonador de tarefas que possibilita a utilização de vários métodos de classificação e validação, permitindo a distribuição dessas tarefas entre os módulos do sistema. Esta arquitetura está estruturada de forma que classificações obtidas através de uma técnica sejam reutilizadas em paralelo pelo mesmo algoritmo ou por outras técnicas, produzindo novas classificações através do refinamento dos resultados alcançados e ampliando o uso em bases de dados com características diferentes. O sistema foi estruturado em quatro partes denominadas, respectivamente, Módulo de Inicialização, Módulo de Validação, Módulo de Refinamento e Módulo Especial de Escalonamento. Em cada módulo, podem ser usados vários algoritmos para atender aos seus objetivos. A estrutura deste sistema permite sua configuração, utilizando diversos métodos, inclusive com técnicas de inteligência artificial. Com isso, é possível a obtenção de resultados mais precisos por meio da escolha do melhor método para cada caso. Os resultados apresentados neste trabalho foram obtidos a partir de bases conhecidas na literatura, o que possibilita comparar as implementações dos métodos tradicionais que foram adicionadas ao sistema e, principalmente, verificar a qualidade dos refinamentos produzidos pela integração de técnicas diferentes. Os resultados demonstram que através de um sistema de aprendizado, minimiza-se a complexidade na análise de grandes bases de dados, permitindo verificar bases com estruturas diferentes e aumentar os métodos aplicados na análise de cada estrutura. Isto favorece a comparação entre os métodos e proporciona resultados mais confiáveis. Para uniformizar os dados provenientes de bases distintas, foi elaborada a modelagem de dados do sistema, o que favorece a escalabilidade do sistema de maneira uniforme. / This thesis presents the architecture of a System Learning with a task scheduler, which makes possible the utilization of several classification and validation methods, allowing the distribution of tasks between the module systems. This architecture is structured of such way that the classifications obtained through a specific technique can be reutilized in parallel by the same algorithm or by other techniques, producing new classifications through the refinement of the results achieved and expanding the use in databases with different characteristics. The system was structured in four parts denominated, respectively, Initialization module; Validation module; Refinement module; and Especial scheduling module. In each module, various algorithms can be employed to reach its objectives. The structure of this system allows its configuration, utilizing various methods, including artificial intelligence techniques. Thus, it is possible to obtain more precise results through the choice of the best method to each case. The results presented in this work were obtained from basis that are known in the literature, which allows to compare the implementations of the traditional methods that were added to the system and, especially, to verify the quality of the refinements produced by the integration of different techniques. The results demonstrated that through a learning system, the complexity of the analysis of great databases is minimized, allowing to verify basis with different structures and to increase the methods applied in the analysis of each structure. It favors the comparison between the methodologies and provides more reliable results. To standardize the data originated of distinct bases, the data modelling system was elaborated, which will favor the uniform scalability of the system.

Made available in DSpace on 2014-07-29T14:57:47Z (GMT). No. of bitstreams: 1 dissertacao thiago b de oliveira 2010.pdf: 575961 bytes, checksum: 7a5a7e195780fa853d33c7629520df2a (MD5) Previous issue date: 2010-12-15 / The demand for spatial data processing systems that support the creation of massive applications has steadily grown in the increasingly ubiquitous computing world. These demands aims to explore the large amount of existing data to assist people s daily lives and provide new tools for business and government. Most of the current solutions to process spatial data do not meet the scalability needed, and thus new solutions that efficiently use distributed computing resources are needed. This work presents a distributed and scalable system called DSI-RTree, which implements a distributed index to process spatial data in a cluster of computers. We also have done a review of details related to the construction of the distributed spatial index, by addressing issues such as the size of data partitions, how that partitions are distributed and the impact of these definitions in the message flow on the cluster. An equation to calculate the size of the partitions based on the size of data sets is proposed, to ensure efficiently query processing on the proposed architecture. We have done some experiments running window queries in spatial data sets of 33,000 and 158,000 polygons and the results showed a scalability greater than linear. / Em face de um mundo computacional ubíquo cada vez mais possível, tem crescido constantemente a necessidade de sistemas de processamento de dados espaciais que suportem a criação de aplicações massivas para explorar a grande quantidade de dados existente, a fim de auxiliar a vida cotidiana das pessoas e prover novas ferramentas para empresas e governo. Soluções atuais de processamento, em sua maioria, não possuem a escalabilidade necessária para atender esta demanda e novas soluções distribuídas que usam eficientemente os recursos computacionais são necessárias. Este trabalho apresenta o DSIRTree, um sistema distribuído e escalável, que implementa a indexação e processamento distribuído de dados espaciais em um cluster de computadores. Uma avaliação de parâmetros da construção do índice espacial distribuído é realizada, abordando aspectos como o tamanho das partições criadas, a forma de distribuição destas partições e o impacto destas definições na troca de mensagens entre as máquinas do cluster. Uma fórmula para cálculo do tamanho das partições conforme o tamanho dos datasets é proposta, a fim de garantir eficiência no processamento de consultas na arquitetura projetada. Testes práticos do sistema mostraram uma escalabilidade maior que linear no processamento de consultas de janela em datasets espaciais de 32 e 158 mil polígonos.

Submitted by Ricardo Cedraz Duque Moliterno (ricardo.moliterno@uefs.br) on 2017-11-28T21:38:06Z No. of bitstreams: 1 dissertacao-versao-final.pdf: 2717503 bytes, checksum: a1476bba65482b40daa1a139191ea912 (MD5) / Made available in DSpace on 2017-11-28T21:38:06Z (GMT). No. of bitstreams: 1 dissertacao-versao-final.pdf: 2717503 bytes, checksum: a1476bba65482b40daa1a139191ea912 (MD5) Previous issue date: 2017-07-17 / With the popularization of databases containing objects with spatial and textual information (spatio-textual object), the interest in new queries and techniques for retrieving these objects have increased. In this scenario, the main query is the the top-k spatio-textual query. This query retrieves the k best spatio-textual objects considering the distance of the object to the query location and the textual similarity between the query keywords and the textual information of the objects. However, most the studies related to top-k spatio-textual query are performed in centralized environments, not addressing real world problems such as scalability. In this paper, we study different strategies for partitioning the data and processing the top-k spatio-textual query in a distributed environment. We evaluate each strategy in a real distributed environment, employing real datasets. / Com a populariza??o de bases de dados contendo objetos que possuem informa??o espacial e textual (objeto espa?o-textual), aumentou o interesse por novas consultas e t?cnicas capazes de recuperar esses objetos de forma eficiente. Uma das principais consultas para objetos espa?o-textuais ? a consulta espa?o-textual top-k. Essa consulta visa recuperar os k melhores objetos considerando a dist?ncia do objeto at? um local informado na consulta e a similaridade textual entre palavras-chave de busca e a informa??o textual dos objetos. No entanto, a maioria dos estudos para consultas espa?o-textual top-k assumem ambientes centralizados, n?o abordando problemas frequentes em aplica??es do mundo real como escalabilidade. Nesta disserta??o s?o estudadas diferentes formas de particionar os dados e o impacto destes particionamentos no processamento da consulta espa?o-textual top-k em um ambiente distribu?do. Todas as estrat?gias propostas s?o avaliadas em um ambiente distribu?do real, utilizando dados reais.