ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph

Ehab Abdelhamid, Ibrahim Abdelaziz, Panos Kalnis, Zuhair Khayyat, Fuad Tarek Jamour

Research output: Chapter in Book/Report/Conference proceedingConference contribution

29 Scopus citations

Abstract

Frequent Subgraph Mining is an essential operation for graph analytics and knowledge extraction. Due to its high computational cost, parallel solutions are necessary. Existing approaches either suffer from load imbalance, or high communication and synchronization overheads. In this paper we propose ScaleMine; a novel parallel frequent subgraph mining system for a single large graph. ScaleMine introduces a novel two-phase approach. The first phase is approximate; it quickly identifies subgraphs that are frequent with high probability, while collecting various statistics. The second phase computes the exact solution by employing the results of the approximation to achieve good load balance; prune the search space; generate efficient execution plans; and guide intra-task parallelism. Our experiments show that ScaleMine scales to 8,192 cores on a Cray XC40 (12× more than competitors); supports graphs with one billion edges (10× larger than competitors), and is at least an order of magnitude faster than existing solutions.
Original languageEnglish (US)
Title of host publicationSC16: International Conference for High Performance Computing, Networking, Storage and Analysis
PublisherIEEE
Pages727-727
Number of pages1
ISBN (Print)9781467388153
DOIs
StatePublished - 2016

Fingerprint

Dive into the research topics of 'ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph'. Together they form a unique fingerprint.

Cite this