A scalable CPU-MIC coordinated drug-finding tool by frequent subgraph mining

Shaoliang PENG; Qi NIU; Kenli LI; Quan ZOU

doi:10.11959/j.issn.2096-0271.2019016

您当前的位置：

首页 >

文章列表页 >

A scalable CPU-MIC coordinated drug-finding tool by frequent subgraph mining

STUDY | 更新时间：2024-06-03

- A scalable CPU-MIC coordinated drug-finding tool by frequent subgraph mining
- Big Data Research Vol. 5, Issue 2, Pages: 2019016-1(2019)
- 作者机构：
  
  1. 湖南大学信息科学与工程学院，湖南长沙 410082
  2. 电子科技大学基础与前沿研究院，四川成都 610054
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-0271.2019016
  CLC： TP31
- Online First：2019-03，
  
  Published：15 March 2019
- 稿件说明：
移动端阅览
Shaoliang PENG, Qi NIU, Kenli LI, et al. A scalable CPU-MIC coordinated drug-finding tool by frequent subgraph mining[J]. Big Data Research, 2019, 5(2): 2019016-1.
DOI：

Shaoliang PENG, Qi NIU, Kenli LI, et al. A scalable CPU-MIC coordinated drug-finding tool by frequent subgraph mining[J]. Big Data Research, 2019, 5(2): 2019016-1. DOI： 10.11959/j.issn.2096-0271.2019016.

摘要

频繁子图挖掘是许多实际应用领域中需要解决的重要问题，由于计算密集性、挖掘的图集及其结果容量大，现有的频繁子图挖掘方案无法满足时间需求，其处理效率是目前面临的主要挑战。原创性地提出了并行加速的频繁子图挖掘工具cmFSM。cmFSM主要在3个层次上进行并行优化：单节点上的细粒度OpenMP并行化、多节点多进程并行化和CPU-MIC协作并行化。在单节点上cmFSM的处理速度比基于CPU的最佳算法快一倍，在多节点方案中cmFSM提供可扩展性。结果表明，即使只使用一些并行计算资源，cmFSM也明显优于现有的最先进的算法。这充分表明提出的工具在生物信息学领域的有效性。

Abstract

Frequent subgraph mining is an important issue to be solved in many practical fields.Due to the computational intensiveness

the mining of the atlas and the large capacity of the results

the existing solutions can not meet the time requirements

and its efficiency is currently the main challenge.The frequent subgraph mining tool cmFSM for parallel acceleration was originally proposed.cmFSM performs parallel optimization on three levels:fine-grained OpenMP parallelization on a single node

multi-node multi-process parallelization and CPU-MIC collaborative parallelization.cmFSM is twice as fast as the best CPU-based algorithm on a single node and provides scalability in a multi-node approach.In the future

we will continue to improve the scalability of multiple solutions.The results show that even with only a few parallel computing resources

cmFSM is significantly better than the most advanced algorithms available.This fully demonstrates the effectiveness of the proposed tool in the field of bioinformatics.

关键词

Keywords

references

LIN W . Efficient techniques for subgraph mining and query processing [D ] . Singapore:Nanyang Technological University , 2015 .

HUAN J , WANG W , PRINS J , et al . SPIN:mining maximal frequent subgraphs from graph databases [C ] // The 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,August 22-25,2004,Seattle,USA . New York:ACM Press , 2004 : 581 - 586 .

JIANG X , XIONG H , WANG C , et al . Mining globally distributed frequent subgraphs in a single labeled graph [J ] . Data and Knowledge Engineering , 2009 , 68 ( 10 ): 1034 - 1058 .

KURAMOCHI M , KARYPIS G . Finding frequent patterns in a large sparse graph [J ] . Data Mining ＆ Knowledge Discovery , 2005 , 11 ( 3 ): 243 - 271 .

KANG U , TSOURAKAKIS CE , FALOUTSOS C . PEGASUS:mining peta-scale graphs [J ] . Knowledge ＆ Information Systems , 2011 , 27 ( 2 ): 303 - 325 .

REINHARDT S , KARYPIS G . A multi-level parallel implementation of a program for finding frequent patterns in a large sparse graph [C ] // 2007 IEEE International Parallel and Distributed Processing Symposium,March 26-30,2007,Rome,Italy . Piscataway:IEEE Press , 2007 : 1 - 8 .

WU B , BAI Y L . An efficient distributed subgraph mining algorithm in extreme largegraphs [C ] // The 2010 International Conference on Artificial Intelligence and Computational Intelligence,October 23-24,2010,Sanya,China . Heidelberg:Springer , 2010 : 107 - 115 .

YAN Y , DONG Y , HE X , et al . FSMBUS:a frequent subgraph mining algorithm in single large-scale graph using spark [J ] . Journal of Computer Research and Development , 2015 , 52 ( 8 ): 1768 - 1783 .

LIN W , XIAO X , XIE X , et al . Network motif discovery:a GPU approach [C ] // IEEE 31st International Conference on Data Engineering,April 13-17,2015,Seoul,Korea . Piscataway:IEEE Press , 2015 : 831 - 842 .

HILL S , SRICHANDAN B , SUNDERRAMAN R . An iterative MapReduce approach to frequent subgraph mining in biological datasets [C ] // The ACM Conference on Bioinformatics,Computational Biology and Biomedicine,October 7-10,2012,Orlando,USA . New York:ACM Press , 2012 : 661 - 666 .

INOKUCHI A , WASHIO T , MOTODA H . An apriori-based algorithm for mining frequent substructures from graph data [C ] // The 4th European Conference on Principles of Data Mining and Knowledge Discovery,September 13-16,2000,London,UK . London:SpringerVerlag , 2000 : 13 - 23 .

KURAMOCHI M , KARYPIS G . Frequent subgraph discovery [C ] // IEEE International Conference on Data Mining,November 29-December 2,2001,San Jose,USA . Piscataway:IEEE Press , 2001 : 313 - 320 .

MEINL T , FISCHER I , PHILIPPSEN M . A quantitative comparison of the subgraph miners mofa,gspan,FFSM,and gaston [C ] // European Conference on Principles and Practice of Knowledge Discovery in Databases,October 3-7,2005,Porto,Portugal . Heidelberg:Springer , 2005 : 392 - 403 .

BORGELT C , BERTHOLD M R . Mining molecular fragments:finding relevant substructures of molecules [C ] // 2002 IEEE International Conference on Data Mining,December 9-12,2002,Maebashi City,Japan . Piscataway:IEEE Press , 2002 : 51 - 58 .

HUAN J , WANG W , PRINS J . Efficient mining of frequent subgraphs in the presence of isomorphism [C ] // The 3rd IEEE International Conference on Data Mining,November 19-22,2003,Melbourne,USA . Washington,DC:IEEE Computer Society , 2003 : 549 - 552 .

YAN X , HAN J . gSpan:graph-based substructure pattern mining [C ] // 2002 IEEE International Conference on Data Mining,December 9-12,2002,Maebashi City,Japan . Piscataway:IEEE Press , 2002 : 721 - 724 .

NIJSSEN S , . A quickstart in frequent structure mining can make a difference [C ] // The 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,August 2225,2004,Seattle,USA . New York:ACM Press , 2004 : 647 - 652 .

BUEHRER G , PARTHASARATHY S , CHEN Y K . Adaptive parallel graph mining for CMP architectures [C ] // The 6th International Conference on Data Mining,December 18-22,2006,Hong Kong,China . Piscataway:IEEE Press , 2006 : 97 - 106 .

WANG C , WANG W , PEI J , et al . Scalable mining of large disk-based graph databases [C ] // The 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,August 22-25,2004,Seattle,USA . New York:ACM Press , 2004 : 316 - 325 .

NGUYEN S N , ORLOWSKA M E , LI X . Graph mining based on a data partitioning approach [C ] // The 19th Conference on Australasian Database,December 3-4,2007,Gold Coast,Australia.Darlinghurst:Australian Computer Society,Inc . , 2008 : 31 - 37 .

DEAN J , GHEMAWAT S . MapReduce:simplified data processing on large clusters [C ] // The 6th Conference on Symposium on Opearting Systems Design ＆ Implementation,December 6-8,2004,San Francisco,USA . Berkeley:USENIX Association , 2004 : 107 - 113 .

BHUIYAN M A , AL H M . An iterative MapReduce based frequent subgraph mining algorithm [J ] . IEEE Transactions on Knowledge＆ Data Engineering , 2013 , 27 ( 3 ): 608 - 620 .

LU W , CHEN G , TUNG A K H , et al . Efficiently extracting frequent subgraphs using MapReduce [C ] // 2013 IEEE International Conference on Big Data,October 6-9,2013,Silicon Valley,USA . Piscataway:IEEE Press , 2013 : 639 - 647 .

LIN W , XIAO X , GHINITA G . Largescale frequent subgraph mining in MapReduce [C ] // 2014 IEEE 30th International Conference on Data Engineering,March 31-April l4,2014,Chicago,USA . Piscataway:IEEE Press , 2014 : 844 - 855 .

Views

230

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Constructing the international database management system for omics big data

Bioinformatics methods for high-throughput DNA sequencing data

Related Author

Wenming ZHAO

Sisi ZHANG

Bixia TANG

Tingting CHEN

Lili HAO

Jian SANG

Rujiao LI

Jingfa XIAO

Related Institution

College of Computer Science and Technology, Heilongjiang Institute of Technology

School of Software, Harbin University of Science and Technology

Department of Biomedical Engineering, Peking University

Postal code：100079
Tel：（010）53879208、53859533 Email：bdr@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
Total Visits：273380 Visits Today：286

⁰