Data analysis over large-scale graphs using vertex-centric asynchronous parallel processing (2020)
- Authors:
- Autor USP: GIMENES, GABRIEL PERRI - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- DOI: 10.11606/T.55.2020.tde-08062020-100828
- Subjects: WEB 2.0; PROGRAMAÇÃO PARALELA; GRAFOS ALEATÓRIOS; ANÁLISE DE DADOS
- Keywords: Belief propagation; Big data; Graph processing; Larga escala; Parallel processing; Processamento centrado em vertíces; Propagação de crenças; Vertex-centric processing
- Agências de fomento:
- Language: Inglês
- Abstract: Desde o surgimento da web 2.0, os usuários não mais apenas consomem conteúdo, mas também são responsáveis agora por criar conteúdo que será consumido por outros usuários. Essa nova dinâmica levou a produção de dados à uma nova e surpreendente escala, chamada de escala planetária. Muitas vezes tais dados representam relacionamentos entre seus elementos, como é o caso em redes sociais, sistemas de recomendação, fórums online, redes de email, redes de citação científica, entre outras. Analisar o fluxo de informações e como os nós influenciam uns aos outros nesses domínios é um problema recorrente; Apesar do algoritmo Belief Propagation ser um dos principais algoritmos utilizados nesse contexto, o algoritmo historicamente apresentou problemas de garantias de convergência quando aplicado à redes reais. Contudo, apesar de recentemente métodos alternativos como LinBP focarem em resolver o problema de convergência do algoritmo original, a escalabilidade do algoritmo em grafos de larga escala continua sendo um desafio. Além disso, muitas das propostas que tentam resolver o problema de escalabilidade necessitam de infraestrutura adicional como supercomputadores e clusters computacionais. Com a motivação desses desafios, essa tése propoe um novo algoritmo, chamado VCBP, que tem como objetivo prover um arcabouço escalável para Belief Propagation em problemas de larga escala, como ocorre nos casos em que o grafo não cabe na memória principal. A proposta combina técnicas de processamentoparalelo assíncrono centrado em vértices com avanços de estado-da-arte no algoritmo de Belief Propagation. O VCBP é capaz de alcançar novos patamares de performance que são ordens de magnitude melhores que a implementação do LinBP. Além disso, devido à natureza assíncrona do algoritmo são necessárias menos iterações até que a convergência seja alcançada quando comparado com outras soluções. Por fim, analisamos também o algoritmo quando aplicado à tarefa de classificação, alcançando resultados significativos em bases de dados reais. Nossas descobertas indicam que existe um grande potencial inexplorado na tecnologia de hardware largamente disponível atualmente, especialmente em relação ao paralelismo, apontando para a oportunidade de uma computação mais acessível e com melhor custo-benefício.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2020
- Data da defesa: 10.02.2020
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
GIMENES, Gabriel Perri. Data analysis over large-scale graphs using vertex-centric asynchronous parallel processing. 2020. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2020. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-08062020-100828/. Acesso em: 09 jun. 2024. -
APA
Gimenes, G. P. (2020). Data analysis over large-scale graphs using vertex-centric asynchronous parallel processing (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-08062020-100828/ -
NLM
Gimenes GP. Data analysis over large-scale graphs using vertex-centric asynchronous parallel processing [Internet]. 2020 ;[citado 2024 jun. 09 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-08062020-100828/ -
Vancouver
Gimenes GP. Data analysis over large-scale graphs using vertex-centric asynchronous parallel processing [Internet]. 2020 ;[citado 2024 jun. 09 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-08062020-100828/
Informações sobre o DOI: 10.11606/T.55.2020.tde-08062020-100828 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
