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 176:
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
[[Ficheiro:ExemploDB.png|400px|miniaturadaimagem|centro|''Figure 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.
== Estratégias de armazenamento ==
Como em algumas aplicações a eficiência é mais importante que a precisão do agrupamento e em outras o inverso ocorre, desejou-se algum mecanismo que permita o balanceamento entre qualidade e tempo de execução no armazenamento. A solução encontrada foi a divisão do espaço dimensional e a possibilidade de replicação de registros entre os nós.
A divisão do espaço dimensional deve ser realizada de maneira similar ao espaço do ''CAN'' <ref name="teste">[http://www.eecs.harvard.edu/~mema/courses/cs264/papers/p13-ratnasamy.pdf Content Addressable Network] </ref> , uma rede par a par proposta em . Com essa divisão, a aplicação não armazena e transmite informações de cada ponto, o que seria ineficiente para dados massivos: as informações trocadas são referentes às partições e a granularidade do particionamento será um parâmetro do programa.
O outro mecanismo para permitir esse balanceamento entre tempo de execução e qualidade e ainda garantir tolerância a falha é a replicação de pontos em diferentes nós. Nesse caso, um parâmetro de execução define quantas vezes cada ponto será replicado entre os nós. Além de aumentar a tolerância a falhas de nós, esse parâmetro ajuda a evitar situações em que vários pontos vizinhos ficam espalhados e por isso não formam um grupo ao final da execuçã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.
<references />
| |||