Parallel Subgraph Counting for Multicore Architectures

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

Autores

David Aparicio (Autor) Outra; Pedro Ribeiro (Autor) FCUP; Fernando Silva (Autor) FCUP

Ata de Conferência Internacional

Título: Proceedings - 2014 IEEE International Symposium on Parallel and Distributed Processing with Applications, ISPA 2014

Páginas: 34-41

12th IEEE International Symposium on Parallel and Distributed Processing with Applications, ISPA 2014

26 August 2014 through 28 August 2014

Indexação

ISI Web of Knowledge - 12 Citações

Scopus - 17 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-00A-4ES

DOI: 10.1109/ispa.2014.14

Abstract (EN): Computing the frequency of small subgraphs on a large network is a computationally hard task. This is, however, an important graph mining primitive, with several applications, and here we present a novel multicore parallel algorithm for this task. At the core of our methodology lies a state-of-the-art data structure, the g-trie, which represents a collection of subgraphs and allows for a very efficient sequential search. Our implementation was done using Pthreads and can run on any multicore personal computer. We employ a diagonal work sharing strategy to dynamically and effectively divide work among threads during the execution. We assess the performance of our Pthreads implementation on a set of representative networks from various domains and with diverse topological features. For most networks, we obtain a speedup of over 50 for 64 cores and an almost linear speedup up to 32 cores, showcasing the flexibility and scalability of our algorithm. This paves the way for the usage of such counting algorithms on larger subgraph and network sizes without the obligatory access to a cluster.

Idioma: Inglês

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

Nº de páginas: 8