5
edições
Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Avaliação do algoritmo PageRank: diferenças entre revisões
Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Avaliação do algoritmo PageRank (editar)
Revisão das 01h15min de 15 de fevereiro de 2013
, 01h15min de 15 de fevereiro de 2013sem resumo de edição
Sem resumo de edição |
Sem resumo de edição |
||
|
[[Imagem:PageRanks-Example.svg|400px|right]]
== Descrição da Aplicação ==
Numa rede com n nodos, atribui-se inicialmente o valor de 1/n para cada um. Depois disso, realizamos uma regra de atualização um determinado número k de vezes. A regra de atualização é a seguinte: cada nodo compartilha seu valor atual de PageRank igualmente com todos os nodos que segue, e cada nodo atualiza seu valor para ser a soma das partes que recebeu. A teoria do PageRank diz que até mesmo uma pessoa que clica em links aleatoriamente vai, eventualmente, parar de clicar. A probabilidade, a qualquer passo, que uma pessoa continue clicando é dado por um fator de amortecimento (damping factor) d, que geralmente é configurado para ter o valor 0,85. O fator de amortecimento é subtraído de 1 e o resultado é adicionado ao produto do fator de amortecimento pela soma das partes que o nodo recebeu.
<code>
Para cada vértice <math>v</math>:
<math>PR(v, 0) = \frac{1}{N}</math>
<math>VA = {v \in V}</math>▼
Para cada iteração <math>t</math>, enquanto <math>|VA| > 0</math>:▼
▲VA = {v \in V}
Para cada vértice <math>v \in VA</math>:▼
<math>PR(v, t+1) = \frac{1-d}{N} + d \sum_{u \in M(v)} \frac{PR(u, t)}{L(u)}</math>▼
▲Para cada iteração t, enquanto |VA| > 0:
<math>VA = {v \in V : |PR(V, t+1) - PR(V, t)| > MAX_ERR}</math>▼
</code>
▲Para cada vértice v \in VA:
▲PR(v, t+1) = \frac{1-d}{N} + d \sum_{u \in M(v)} \frac{PR(u, t)}{L(u)}
▲VA = {v \in V : |PR(V, t+1) - PR(V, t)| > MAX_ERR}
=== Exemplo de Funcionamento ===
=== Oportunidades de paralelização ===
O valor do rank anterior não pode ser mudado enquanto esse passo é executado e isso pode ser evitado. Ao terminar esse passo, é necessário sincronizar as linhas de execução para que a próxima iteração leia valores de ranks atualizados.
A paralelização pode ser ampliada se os somatórios de ranks
Entretanto essa oportunidade paralelização não garante balanceamento de carga entre cada thread, porque enquanto um nodo pode ser apontado por apenas um nodo, outro pode ser apontado por inúmeros. O balanceamento pode ser melhorado
=== Padrões de acesso aos dados ===
Cada nodo tem como dados o cojunto de nodos para o qual ele aponta e o valor de page rank atual. É necessário que o nodo em cada iteração veja um grafo invertido, que tenha a lista de nodos que apontam para ele. E ele precisará saber o valor do rank atual desses nodos junto com o número de nodos para os quais eles apontam ou apenas a divisão
Quando um algoritmo paralelo executa no mesmo computador, as threads podem ter memória compartilhada e isso permite que cada thread leia todas as informações que precisar sobre o grafo e o custo disso é relativamente baixo.
Quando o volume de dados é muito grande, o processamento teria tempo de execução longo e os dados podem não caber
=== Padrões de comunicação ===
É necessário fazer comunicação para sincronizar as
Em processamento distribuído, o novo valor de rank deve ser enviado para todas as threads que usarão esse valor na próxima iteração. Assim, o número de mensagens trocadas na rede em cada iteração seria igual ao número de arestas do grafo, e
=== Linha do tempo integrada ===
Quando há uma thread por nodo, cada thread processa de maneira independente sua lista de apontadores e no final é necessário esperar todas as outras threads terminar para poder atualizar o rank do nodo e receber novos valores de rank. Além da comunicação para sincronização, em implementação distribuída, é necessário comunicação para enviar e receber valores do rank calculados durante a iteração.
== Desenvolvimento ==
| |||