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

Saltar para a navegação Saltar para a pesquisa
[edição não verificada][edição não verificada]
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 6, 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.
 
[[Ficheiro:ExemploDB.png|400px|miniaturadaimagem|centro|''FigureFigura 6: Exemplo de situação em que a separação dos dados impede a formação de um grupo: enquanto os pontos do primeiro nó formaram o grupo em azul e os pontos do segundo nó formaram o grupo amarelo, os pontos em vermelho não estavam em quantidade suficiente em nenhum nó para formar um grupo.'']]
 
Para que essa condição seja satisfeita, o particionamento dos dados é feito com a função ''Z-order curve'' que mapeia dados multi-dimensionais para apenas uma dimensão preservando a localidade dos registros. O grande risco é de que um gargalo seja formado: caso essa etapa de pré-ordenaçao dos dados para definir o paticionamento não seja implementada de forma eficiente, a replicação dos dados será a única alternativa para evitar que situações como a da figura [exemplo] ocorram. Uma abordagem ''map-reduce'' também poderá ser aplicada no particionamento caso essa etapa esteja comprometendo a escalabilidade da aplicação.
 
A figura 7 mostra todas as informações que um nó precisa armazenar. Nesse exemplo com duas dimensões, o nó deverá armazenar informações sobre quais dos seus pontos são vizinhos, a classificação de cada ponto (de centro, de borda ou exceção) e quais partições já foram assimiladas a um grupo. A informação sobre os grupos formados deve ser a mesma em todos os nós: os grupos marcados de amarelo e azul foram informados por outros nós.
 
 
[[Ficheiro:Armazenamento.png|500px|miniaturadaimagem|centro|''Figura 7: Informações que cada nó precisa armazenar: a posição dos pontos, a qual grupo pertence cada partição, quais os pontos vizinhos e qual a classificação de cada ponto.'']]
 
== Estratégia de comunicação ==
 
A comunicação deve ser realizada para informar e sincronizar informações sobre quais partições foram assimiladas a qual grupo. Nesse caso, não é necessário direcionar as mensagens, elas devem ser enviadas para todos. Também não é necessário sincronização ou uso de barreiras: se dois nós enviam mensagem ao mesmo tempo informando que a mesma partição pertence a um de seus grupos, cada nó deve saber interpretar a informação baseando-se no tipo de ponto que levou à assimilação da partição ao grupo. Portanto, a cada vez que um ponto é assimilado a um grupo, o nó deve enviar uma mensagem avisando qual o tipo desse ponto e qual partição foi assimilada a qual grupo.
 
Se dois ou mais nós enviarem mensagem informando que uma partição contendo pelo menos um ponto de centro pertence a um determinado grupo, a interpretação de todos os nós devem ser de que esses grupos devem ser unidos. A figura 8 representa essa situação: a partição (2,3) foi assimilada para dois grupos diferentes no primeiro e no terceiro nó. Após o recebimento da mensagem informando que aquela partição contendo um ponto de centro foi assimilada para os grupos A e B, todos os nós fazem a junção desses grupos.
 
[[Ficheiro:Comunicacao.png|400px|miniaturadaimagem|centro|''Figura 8: Procedimento de comunicação quando dois pontos de centro (ou um ponto de centro e um de borda) têm sua partição assimilada para um grupo ao mesmo tempo. Os nós informam os demais sobre a assimilação e ao receber as duas mensagens, os nós juntam os grupos.'']]
 
Se essa situação ocorrer apenas com partições de borda, os nós devem manter a informação processada por último. Nesse caso haverá nós armazenando diferentes grupos para a mesma partição e apenas ao final, quando haverá a produção do resultado final, será definido a qual grupo a partição de borda pertence. Essa situação em que a definição de um ponto de borda não é determinística também ocorre no ''DBScan'' tradicional, já que a ordem de execução dos pontos centrais pode fazer com que os pontos de borda sejam assimilados a grupos distintos. Essa situação está ilustrada na figura 9.
 
[[Ficheiro:Comunicacao2.png|400px|miniaturadaimagem|centro|''Figura 9: Procedimento de comunicação quando duas partições que não contém ponto de centro são assimiladas a grupos distintos ao mesmo tempo. Ao final de todo o procedimento será escolhida uma das configurações.'']]
 
<references />

Menu de navegação