Parallel Subgraph Counting for Multicore Architectures

• Type: Article in International Conference Proceedings Book
• Date: 2014

Authors

David Aparicio (Author) Other; Pedro Ribeiro (Author) FCUP; Fernando Silva (Author) FCUP

Conference proceedings International

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

Pages: 34-41

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

26 August 2014 through 28 August 2014

Indexing

ISI Web of Knowledge - 12 Citations

Scopus - 17 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 8