Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Agrupamento baseado em densidade: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Linha 120:
Em é apresentado uma implementação paralela do ''DBScan'' com uma abordagem mestre-escravo: enquanto o núcleo mestre realiza a etapa de assimilação de grupos, os escravos respondem a consultas de vizinhança usando a estrutura ''R*-Tree'' para armazenamento.
 
Em ''P-DBSCAN'' <ref>http://bib.dbvis.de/uploadedFiles/17.pdf</ref> <ref name="P-DBSCAN">, texto adicional.</ref>, a base é particionada e o agrupamento é feito de forma independente entre os nós de forma distribuída. Ao final, há uma agregação dos resultados de cada nó para formar o resultado final. Quanto ao armazenamento, a estrutura utilizada é a ''Priority R-Tree'' que é uma variação eficiente da ''R-Tree''. Nessa implementação há a limitação de haver um único nó para juntar os resultados do agrupamento feito por todos os nós. Além disso, os pontos considerados exceções por um nó não são tratados posteriormente na junção dos grupos, portanto grupos densos podem ser perdidos se seus registros estiverem divididos entre os nós.
 
De forma similar ao ''P-DBSCAN'', o ''MR-DBSCAN'', proposto em , é uma implementação distribuída do ''DBScan'' com quatro estágios e que utiliza o paradigma ''Map-reduce'' . A primeira etapa consiste em dividir a base entre os nós de forma balanceada e de forma a deixar os registros mais próximos no mesmo nó. Em seguida, na fase ''map'', o ''DBScan'' é executado de forma independente dentro de cada nó. A terceira etapa é a fase ''reduce'': todos os nós são analisados para descobrir em quais situações o mesmo nó foi agrupado para diferentes grupos, ou seja, é feito um mapeamento da junção e remarcação dos grupos que é realizada na quarta e última etapa. Os resultados mostraram que a escalabilidade e a eficiência dessa abordagem são bastante satisfatórias.
 
Em ''SDBDC''<ref>''Scalable Density-Based Distributed Clustering''</ref> , que é uma melhora de , também é realizada a tarefa de agrupamento baseada em densidade de forma distribuída. Nessa abordagem, os pontos centrais de cada nó são determinados e a partir deles, os pontos representativos globais são identificados. A partir dessa informação sobre os pontos representativos globais, os pontos de cada nó são rotulados para os grupos. Portanto essa técnica parte de uma informação local para gerar uma análise global e novamente gerar uma informação local. Há a possibilidade do usuário balancear a quantidade de pontos considerados representativos em cada nó, o que pode aumentar o tempo de execução e a qualidade ou realizar uma execução mais rápida com menos qualidade.
Em ''SDBDC''<ref>''Scalable Density-Based Distributed Clustering''
</ref> , que é uma melhora de , também é realizada a tarefa de agrupamento baseada em densidade de forma distribuída. Nessa abordagem, os pontos centrais de cada nó são determinados e a partir deles, os pontos representativos globais são identificados. A partir dessa informação sobre os pontos representativos globais, os pontos de cada nó são rotulados para os grupos. Portanto essa técnica parte de uma informação local para gerar uma análise global e novamente gerar uma informação local. Há a possibilidade do usuário balancear a quantidade de pontos considerados representativos em cada nó, o que pode aumentar o tempo de execução e a qualidade ou realizar uma execução mais rápida com menos qualidade.
 
Considerando os trabalhos existentes de paralelização do ''DBScan'', conclui-se que o agrupamento distribuído baseado em densidade não é uma tarefa trivial e há vários fatores a serem balanceados já que é inviável atender a todos. Alguns desses fatores são a comunicação, a descentralização de tarefas, a completude e a qualidade da solução.