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 133:
Portanto, como o agrupamento baseado em densidade depende de informações globais sobre vizinhança entre os pontos e a implementação paralela ou distribuída deve ser capaz de encontrar um balanceamento entre agregação dos dados globais (centralização ou comunicação), eficiência e qualidade.
__TOC__
= PROJETO =
Essa seção descreve o projeto de implementação da abordagem distribuída do ''DBScan''. Para essa análise, o algoritmo será tratado por duas etapas: a primeira é o cálculo da distância entre todos os pares possíveis de registros e a segunda é a etapa de percorrimento dos pontos centrais e assimilação de pontos aos grupos.
== Oportunidades de paralelização ==
A primeira etapa é a mais custosa do algoritmo e representa uma oportunidade de paralelismo já que pode ser feita de forma independente entre todos os pares, sendo que um cuidado a ser tomado é garantir a completude e a não-redundância na distribuição dos pares. O paradigma ''Map-reduce'' pode ser considerado uma solução aderente, em que a fase ''map'' seria o cálculo das distâncias entre todos os pares e a etapa ''reduce'' seria a classificação dos pontos como ponto de centro, ponto de borda ou exceção. O objetivo final dessa etapa é ter a informação sobre quais pontos são vizinhos e qual a classificação de cada ponto.
Outra solução de paralelismo para a primeira etapa seria dividir os registros entre os nós e calcular apenas a distância dos pares de registros de cada nó de forma independente. Tratando-se de grandes volumes de dados, essa segunda abordagem é mais adequada, já que a primeira resultaria em um grande volume de informações sobre vizinhança, o que tornaria inviável a consulta e a distribuição dessas informações para todos os nós.
Em uma abordagem distribuída, a paralelização da segunda etapa só pode ser feita dividindo-se os registros entre os nós e executando a etapa de percorrimento dos pontos centrais e assimilação dos grupos de forma independente dentro de cada um. A variação nesse processo ocorre na quantidade de registros distribuídos por nó.
== Padrão de acesso aos dados ==
Quando o agrupamento é realizado com base na densidade de registros, é necessário manter e consultar a informação sobre quais registros são vizinhos, qual a classificação de cada ponto e quais pontos já foram agrupados e para qual grupo. Essas informações podem ser armazenadas ou de forma centralizada com uso de memória compartilhada ou de forma distribuída. Mais uma vez, o fato do algoritmo ser distribuído e direcionado para grandes volumes de dados torna inviável o uso de memória compartilhada. O controle de acesso e escrita tornaria essa atividade um gargalo para execução. Portanto as informações devem estar distribuídas entre os nós e é desejável que haja particionamento dos dados devido ao grande volume de dados para armazenamento.
== Padrão de comunicação ==
A comunicação do DBScan distribuído deve ocorrer no momento em que os grupos são formados. Para isso há duas possibilidades: realizar a comunicação entre os nós durante a etapa de assimilação dos grupos ou realizar o agrupamento sem comunicação entre os nós para depois realizar uma operação de junção dos grupos considerando os grupos formados por todos os nós.
== Linha do tempo integrada ==
A figura 5 resume a linha do tempo considerando as possibilidades discutidas para a implementação do DBScan distribuído.
<references />
| |||