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

Em ''P-DBSCAN'' <ref name="pdbscan">[http://bib.dbvis.de/uploadedFiles/17.pdf P-DBScan] </ref> , a base é particionada e o agrupamento é feito de forma independente entre os nós de forma distribuída. Ao final, há uma agregação dos resultados de cada nó para formar o resultado final. Quanto ao armazenamento, a estrutura utilizada é a ''Priority R-Tree'' <ref name="prtree">[http://www.daimi.au.dk/~large/Papers/prtreesigmod04.pdf The priority r-tree: A practically eficient and worst-case optimal r-tree], .</ref> que é uma variação eficiente da ''R-Tree''. Nessa implementação há a limitação de haver um único nó para juntar os resultados do agrupamento feito por todos os nós. Além disso, os pontos considerados exceções por um nó não são tratados posteriormente na junção dos grupos, portanto grupos densos podem ser perdidos se seus registros estiverem divididos entre os nós.

De forma similar ao ''P-DBSCAN'', o ''MR-DBSCAN'' <ref name="mrdbscan">[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6121313&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D6121313 MR-DBScan], </ref>, proposto em , é uma implementação distribuída do ''DBScan'' com quatro estágios e que utiliza o paradigma ''Map-reduce'' . A primeira etapa consiste em dividir a base entre os nós de forma balanceada e de forma a deixar os registros mais próximos no mesmo nó. Em seguida, na fase ''map'', o ''DBScan'' é executado de forma independente dentro de cada nó. A terceira etapa é a fase ''reduce'': todos os nós são analisados para descobrir em quais situações o mesmo nó foi agrupado para diferentes grupos, ou seja, é feito um mapeamento da junção e remarcação dos grupos que é realizada na quarta e última etapa. Os resultados mostraram que a escalabilidade e a eficiência dessa abordagem são bastante satisfatórias.

Em ''SDBDC'' <ref name="sdbdc">''[http://pdf.aminer.org/000/541/673/scalable_density_based_distributed_clustering.pdf Scalable Density- Based Distributed Clustering''], .</ref> , que é uma melhora do DBDC <ref name="dbdc">[http://www.dbs.ifi.lmu.de/Publikationen/Papers/EDBT_04_DBDC.pdf Density Based Distributed Clustering], </ref> , também é realizada a tarefa de agrupamento baseada em densidade de forma distribuída. Nessa abordagem, os pontos centrais de cada nó são determinados e a partir deles, os pontos representativos globais são identificados. A partir dessa informação sobre os pontos representativos globais, os pontos de cada nó são rotulados para os grupos. Portanto essa técnica parte de uma informação local para gerar uma análise global e novamente gerar uma informação local. Há a possibilidade do usuário balancear a quantidade de pontos considerados representativos em cada nó, o que pode aumentar o tempo de execução e a qualidade ou realizar uma execução mais rápida com menos qualidade.