ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph
SessionData Analytics
Session ChairXuanhua Shi
Authors
Event Type
Paper
Data Analytics
Intermediate
Introductory
TimeThursday, November 17th11am - 11:30am
Location355-BC
DescriptionFrequent 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-phases 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 (12x more than competitors); supports graphs with one billion edges (10x larger than competitors), and is at least an order of magnitude faster than existing solutions.
Download PDF
Paper provided by the IEEE Computer SocietyPaper also available from the ACM Digital Library
Authors
