Análise de grafos baseada em processamento paralelo assíncrono centrado em vértices: aplicações em dados de escala planetária

• Processo: 13/10026-7
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Vigência (Início): 01 de novembro de 2013
• Vigência (Término): 28 de fevereiro de 2015
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
• Pesquisador responsável: José Fernando Rodrigues Júnior
• Beneficiário: Gabriel Perri Gimenes
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Análise de dados Processamento paralelo Grafos
• Palavra(s)-Chave do Pesquisador: grafos | processamento paralelo | Análise de dados

Resumo

O processamento de grafos de alta escala -- chamados grafos em escala planetária, ou escala Web -- tem atraído o interesse em diversas aplicações como comércio eletrônico, redes de computadores, redes sociais, biologia (interação proteica), entre muitos outros. Para se processar tais grafos, os quais possuem milhões de vértices e bilhões de arestas, tem se utilizado recursos de processamento distribuído organizados em clusters computacionais gerenciados por arcabouços como o Hadoop. O problema de tal abordagem é o fato de que as exigências para se construir e gerenciar tais clusters muitas vezes trazem complexidades maiores do que as necessárias para se processar e analisar os grafos de interesse. Ocorre assim um desvio de recursos, pois o meio requer mais esforço do que o fim. Dessa maneira, torna-se desejável a capacidade de se processar grafos em escala planetária em um único nó computacional. Para este propósito, neste trabalho, se irá trabalhar com técnicas centradas em vértice combinadas com processamento paralelo assíncrono. As técnicas centradas em vértice permitem que propriedades locais dos grafos sejam calculadas sem que o grafo tenha que passar por uma varredura; já as técnicas de processamento paralelo assíncrono permitem que um grafo ocupando Terabytes de um único disco de armazenamento seja processado gradualmente em passos que cabem em memória. Com estas técnicas pretende-se o desenvolvimento de novos algoritmos capazes de calcular propriedades ainda não exploradas de grandes grafos processados em um único nó computacional. Tais propriedades serão usadas na definição de um arcabouço de análise capaz de revelar padrões, compreensão, e tomada de decisão.

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

GIMENES, GABRIEL; CORDEIRO, ROBSON L. F.; RODRIGUES-, JR., JOSE F.. ORFEL: Efficient detection of defamation or illegitimate promotion in online recommendation. INFORMATION SCIENCES, v. 379, p. 274-287, FEB 10 2017. (13/10026-7, 14/21483-2, 16/02557-0)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

GIMENES, Gabriel Perri. Técnicas avançadas de análise de grafos: uma abordagem multimodal sobre dados em escala planetária. 2015. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.