NDLI: Network motif discovery: A GPU approach

Content Provider	IEEE Xplore Digital Library
Author	Wenqing Lin Xiaokui Xiao Xing Xie Xiao-Li Li
Copyright Year	2015
Description	Author affiliation: Microsoft Res. Asia, Beijing, China (Xing Xie) \|\| A*STAR, Singapore, Singapore (Wenqing Lin; Xiao-Li Li) \|\| NTU, Singapore, Singapore (Xiaokui Xiao)
Abstract	The identification of network motifs has important applications in numerous domains, such as pattern detection in biological networks and graph analysis in digital circuits. However, mining network motifs is computationally challenging, as it requires enumerating subgraphs from a real-life graph, and computing the frequency of each subgraph in a large number of random graphs. In particular, existing solutions often require days to derive network motifs from biological networks with only a few thousand vertices. To address this problem, this paper presents a novel study on network motif discovery using Graphical Processing Units (GPUs). The basic idea is to employ GPUs to parallelize a large number of subgraph matching tasks in computing subgraph frequencies from random graphs, so as to reduce the overall computation time of network motif discovery. We explore the design space of GPU-based subgraph matching algorithms, with careful analysis of several crucial factors that affect the performance of GPU programs. Based on our analysis, we develop a GPU-based solution that (i) considerably differs from existing CPU-based methods, and (ii) exploits the strengths of GPUs in terms of parallelism while mitigating their limitations in terms of the computation power per GPU core. With extensive experiments on a variety of biological networks, we show that our solution is up to two orders of magnitude faster than the best CPU-based approach, and is around 20 times more cost-effective than the latter, when taking into account the monetary costs of the CPU and GPUs used.
Starting Page	831
Ending Page	842
File Size	444798
Page Count	12
File Format	PDF
ISBN	9781479979646
DOI	10.1109/ICDE.2015.7113337
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-04-13
Publisher Place	South Korea
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Graphics processing units Instruction sets Frequency estimation Labeling Indexes Central Processing Unit Parallel processing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient parallel GPU algorithms for BDD manipulation

GPU based implementation of recursive digital filtering algorithms

A GPU-accelerated network traffic monitoring and analysis system

A review of Genetic Algorithms and Parallel Genetic Algorithms on Graphics Processing Unit (GPU)

Motif Recognition Parallel Algorithm Based on GPU

GPU accelerated post-processing for multifrequency biplanar interferometric imaging

An Efficient Graph Isomorphism Algorithm Based on Canonical Labeling and Its Parallel Implementation on GPU

Accelerated parallel WLS state estimation for large-scale power systems on GPU

A novel approach toward parallel implementation of BFS algorithm using graphic processor unit

Network motif discovery: A GPU approach

Similar Documents

Efficient parallel GPU algorithms for BDD manipulation

GPU based implementation of recursive digital filtering algorithms

A GPU-accelerated network traffic monitoring and analysis system

A review of Genetic Algorithms and Parallel Genetic Algorithms on Graphics Processing Unit (GPU)

Motif Recognition Parallel Algorithm Based on GPU

GPU accelerated post-processing for multifrequency biplanar interferometric imaging

An Efficient Graph Isomorphism Algorithm Based on Canonical Labeling and Its Parallel Implementation on GPU

Accelerated parallel WLS state estimation for large-scale power systems on GPU

A novel approach toward parallel implementation of BFS algorithm using graphic processor unit

Network motif discovery: A GPU approach