Please use this identifier to cite or link to this item: https://doi.org/10.1109/BigData.2013.6691633
Title: Efficiently extracting frequent subgraphs using MapReduce
Authors: Lu, W.
Chen, G.
Tung, A.K.H. 
Zhao, F.
Issue Date: 2013
Source: Lu, W.,Chen, G.,Tung, A.K.H.,Zhao, F. (2013). Efficiently extracting frequent subgraphs using MapReduce. Proceedings - 2013 IEEE International Conference on Big Data, Big Data 2013 : 639-647. ScholarBank@NUS Repository. https://doi.org/10.1109/BigData.2013.6691633
Abstract: Frequent subgraph extraction from a large number of small graphs is a primitive operation for many data mining applications. To extract frequent subgraphs, existing techniques need to enumerate a large number of subgraphs which is superlinear with the cardinality of the dataset. Given the rapid growing volume of graph data, it is difficult to perform the frequent subgraph extraction on a centralized machine efficiently. In this paper, we investigate how to efficiently perform this extraction over very large datasets using MapReduce. Parallelizing existing techniques directly using MapReduce does not yield good performance as it is difficult to balance the workload among the compute nodes. We therefore propose a framework that adopts the breadth first search strategy to iteratively extract frequent subgraphs, i.e., all frequent size-(i+1) subgraphs are generated based on frequent size-i subgraphs at the ith iteration using a single MapReduce job. To efficiently extract frequent subgraphs, we propose an isomorphism-testing-free approach by properly maintaining how frequent subgraphs are mapped within each graph. Extensive experiments conducted on our in-house clusters demonstrate the superiority of our proposed solution in comparison with the baseline approach. © 2013 IEEE.
Source Title: Proceedings - 2013 IEEE International Conference on Big Data, Big Data 2013
URI: http://scholarbank.nus.edu.sg/handle/10635/78122
ISBN: 9781479912926
DOI: 10.1109/BigData.2013.6691633
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

9
checked on Feb 20, 2018

Page view(s)

32
checked on Feb 23, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.