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 163:
Considerando a proposta exploratória e investigativa do trabalho e voltada para grandes volumes de dados, a solução escolhida consiste em dividir os dados em blocos, distribuindo entre os nós apenas os dados referentes a seus pontos e fazendo uso de comunicação na realização do agrupamento. A proposta de calcular a distância de todos os pares possíveis tornaria essa etapa um gargalo, principalmente em termos de armazenamentos se aplicada a dados massivos. Já a proposta de realizar agrupamento de forma independente para depois unir os grupos foi realizada em dois dos trabalhos mais relevantes com a mesma proposta. Portanto, dentre as opções que não tornam a primeira etapa um gargalo para a execução, foi escolhida a opção ainda não explorada.
__TOC__
= Desenvolvimento =
Essa seção descreve com mais detalhes a proposta de agrupamento distribuído para grandes volumes de dados para que as decisões do projeto permitam sua implementação independentemente das ferramentas e plataformas.
== Estratégias de paralelização ==
Conforme mostrado, a primeira etapa do algoritmo consiste em calcular a distância entre os pares de pontos, o que é uma tarefa custosa, com complexidade quadrática em termos do número de registros. A proposta de dividir os pontos em blocos e calcular apenas a distância intra bloco torna essa tarefa escalável e eficiente.
Esse paralelismo de dados será aplicado também na segunda etapa: cada nó vai executar o ''DBScan'' de forma independente considerando apenas a distância entre os pontos recebidos e calculada na primeira etapa. Como cada nó terá informações apenas de seus registros, a comunicação deve garantir que as informações seja transmitidas com algum critério para definir a granularidade na transmissão de informações.
Um cuidado a ser tomado é que a qualidade do agrupamento final dependerá diretamente de como os dados foram particionados em blocos: se os blocos apresentarem pontos muito distantes entre si, os nós formarão poucos grupos e encontrarão muitas exceções, conforme mostrado na figura [exemplo], em que cada quadrado representa um nó de processamento e os pontos vermelhos representam pontos que poderiam ter formado um grupo, mas não estavam em quantidade suficiente em nenhum dos nós para tal. Conforme será mostrado, uma estratégia para reduzir a probabilidade de ocorrer essa situação é replicar os pontos nos nós.
| |||