A Scalable Parallel Approach for Subgraph Census Computation

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2014

Autores

Aparicio, D (Autor) Outra; Paredes, P (Autor) Outra; Pedro Ribeiro (Autor) FCUP

Ata de Conferência Internacional

Título: EURO-PAR 2014: PARALLEL PROCESSING WORKSHOPS, PT II

Páginas: 194-205

20th Euro-Par International Workshops

Porto, PORTUGAL, AUG 25-26, 2014

Indexação

ISI Web of Knowledge - 6 Citações

Scopus - 5 Citações

Outras Informações

ID Authenticus: P-00A-8W0

DOI: 10.1007/978-3-319-14313-2_17

Abstract (EN): Counting the occurrences of small subgraphs in large networks is a fundamental graph mining metric with several possible applications. Computing frequencies of those subgraphs is also known as the subgraph census problem, which is a computationally hard task. In this paper we provide a parallel multicore algorithm for this purpose. At its core we use FaSE, an efficient network-centric sequential subgraph census algorithm, which is able to substantially decrease the number of isomorphism tests needed when compared to past approaches. We use one thread per core and employ a dynamic load balancing scheme capable of dealing with the highly unbalanced search tree induced by FaSE and effectively redistributing work during execution. We assessed the scalability of our algorithm on a varied set of representative networks and achieved near linear speedup up to 32 cores while obtaining a high efficiency for the total 64 cores of our machine.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 12