• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
https://doi.org/10.11606/T.55.2020.tde-08062020-100828
Documento
Autor
Nome completo
Gabriel Perri Gimenes
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2020
Orientador
Banca examinadora
Rodrigues Junior, José Fernando (Presidente)
Cordeiro, Robson Leonardo Ferreira
Prati, Ronaldo Cristiano
Santos, Renata Galante dos
Título em inglês
Data analysis over large-scale graphs using vertex-centric asynchronous parallel processing
Palavras-chave em inglês
Belief propagation
Big data
Graph processing
Parallel processing
Vertex-centric processing
Resumo em inglês
Since the birth of web 2.0, users no longer just consume but are now active creators of content that is going to be consumed by other users. This new dynamic took data generation to a whole new scale, called planetary-scale or web-scale. Often, this data represents relationships between its elements, such as in social networks, recommendation systems, online boards, email networks, scientific citation networks, and others. Analyzing how information flows and how nodes influence each other in several of such networks is a widely regarded problem; While Belief Propagation, which is the fundamental algorithm for these types of inference, is widely used, it historically lacked convergence guarantees for real-world networks. However, even though recently alternative methods such as LinBP solve the convergence problems of the original algorithm, its scalability when dealing with large-scale problems remains a challenge. Also, several of the works proposed to solve this issue, do so by relying on specific infrastructures such as supercomputers and computational clusters. Motivated by these challenges we propose a new algorithm, called VCBP, that aims to provide a scalable framework for belief propagation on largescale problems, such as when graphs do not fit the main memory. We do so by combining stateof- the-art asynchronous vertex-centric parallel processing with state-of-the-art belief propagation algorithm. Our algorithm maintains the same accuracy rate while achieving performance orders of magnitude higher than former LinBPs implementation. Due to the asynchronous nature of our algorithm, VCBP demands fewer iterations before convergence than any previous algorithm. Additionally, we analyze our algorithm in the task of node classification, achieving significant results over real-world datasets. Our findings indicate that there is unexplored potential in todays widely available modern hardware, specifically concerning parallelism, sparking a shift towards a more cost-efficient and ubiquitous data mining scenario.
Título em português
Análise de dados sobre grafos em larga escala por meio de processamento paralelo assíncrono centrado em vértices
Palavras-chave em português
Larga escala
Processamento centrado em vertíces
Processamento de grafos
Processamento paralelo
Propagação de crenças
Resumo em português
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 processamento paralelo 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.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2020-06-08
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.