31
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 18h53min de 16 de fevereiro de 2013
, 16 de fevereiro de 2013→Paralelizações existentes
| [edição não verificada] | [edição não verificada] |
|
As primeiras propostas de paralelização do algoritmo PageRank foram desenvolvidas implementando a versão matricial do algoritmo em resolvedores de sistema linear paralelos<ref name="cite1">Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, Eli Upfal, "Fast Distributed PageRank Computation", CoRR, 2012</ref>.
Outra estratégia utilizada é o esquema "URL Host", que aproveita a estrutura hierárquica da WEB para fazer a parelização. Basicamente o que ele faz é agrupar os vértices de página de um mesmo domínio (host) e fazer a computação distribuída. Apesar de eficiente, essa estratégia fica limitada a grafos que representem páginas de internet, sendo inadequada para uma abordagem mais genérica<ref name="cite2">Christian Kohlschütter , Ru Chirita , Wolfgang Nejdl, "Efficient parallel computation of PageRank", ECIR, 2006</ref>.
Existem algumas versões de PageRank que fornecem valores aproximados, que na maioria das vezes é justificado pela eficiência no tempo de execução, e uma vertente desses algoritmos faz uma abordagem paralela. Uma dessas abordagens utiliza um esquema MapReduce que utiliza um modelo probabilístico e utiliza o método de Monte Carlo para calcular os valores. <ref name="cite3">Bahman Bahmani, Kaushik Chakrabarti, Dong Xin, "Fast Personalized PageRank on MapReduce"</ref>
| |||