Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Avaliação do algoritmo PageRank: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição |
|||
Linha 102:
=== GraphLab ===
Foi implementada a versão não normalizada do PageRank, ou seja, ao somar os valores de PageRank de todos os vértices o resultado é igual ao número de vértices, e não igual a 1. Observe que caso existam vértices "dangling" (não têm aresta de saída) a soma não sera totalizada, mas a ordenação relativa dos vértices será a mesma.
==== Estratégias de paralelização ====
O GraphLab provê um paradigma de programação ideal para se trabalhar com grafos. O principal elemento da plataforma é o "Vertex Program", que é executado em cada vértice do grafo. O "Vertex Program" tem 3 fases de execução: (1) gather, que é executada nas arestas adjacentes ao vértice e retorna um valor, (2) apply, que agrega os valores retornados pela fase anterior e (3) scatter, que novamente é executado nas arestas adjacentes do vértice.
Utilizando esse pardigma, o algoritmo PageRank será feito por paralelização de dados a nível de vértice. Como para o cálculo do valor de PageRank de um vértice só é necessário valores de vértices adjacentes, temos uma ferramenta que se adequa muito bem para a resolução do problema. Cada vértice armazenará apenas seu respectivo valor de PageRank e a atuzalização será feita através de um "Vertex Program", que também armazena um valor auxíliar de erro.
Na fase "gather" apenas as arestas de entrada são utilizadas, das quais o vértice recebe os valores de PageRank para atualizar seu próprio valor. Cada aresta (u, v) ativa na fase "gather" vai retornar o valor PR(u)/O(u), que corresponde a um valor parcial da soma de atualização.
A fase "apply" vai receber os valores parciais já somados, então basta atualizar o valor de acordo com o dumping factor. Além disso, ainda na fase "apply", vamos armazenar o valor de error calculando a diferença entre o novo e o antigo valor de PageRank, que será utilizado para decidir quais vértices deverão ser atualizados.
A fase "scatter" é utilizada para ativar vértices que deverão ter seus valores atualizados na próxima iteração do algoritmo. Portanto, caso o valor de erro do vértice seja menor do que o valor máximo de tolerância, nenhuma aresta será ativa. Caso o valor de erro seja maior, serão ativas as arestas de saída. Cada aresta (u, v) ativa na fase "scatter" vai assinalar o vértice v para execução na próxima iteração. Ou seja, um vértice só será convocado para execução na próxima iteração se pelo menos um de seus vizinhos de entrada ainda não tiver convergido, pois são justamente os vértices utilizados para o cálculo de seu PageRank.
==== Estratégias de armazenamento ====
O armazenamento é feito através do protocolo NFS, de forma que o acesso à base de dados seja transparente é igual entre os vértices. A base de dados pode ser dividida em arquivos, sendo uma opção de balanceamento explícito, entretanto como o protoclo já NFS provê o acesso aos vértices, optamos por deixar o balanceamento a carga do framework.
==== Estratégias de comunicação ====
A comunicação será feita sempre entre vértices e de forma transparente, devido a utilização do paradigma de programação do GraphLab. É interessante observar que, como a versão do algoritmo PageRank implementada é a não normalizada, não é necessário o compartilhamento de valores globais entre os vértices, como o número totais de vértices, que seria necessário para a versão normalizada.
| |||