Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Agrupamento baseado em densidade: diferenças entre revisões
Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Agrupamento baseado em densidade (editar)
Revisão das 14h03min de 15 de fevereiro de 2013
, 15 de fevereiro de 2013→Desenvolvimento
| [edição não verificada] | [edição não verificada] |
Linha 178:
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|''
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.
Linha 193:
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 />
| |||