Please use this identifier to cite or link to this item: https://doi.org/10.1145/1951365.1951406
Title: Fast random graph generation
Authors: Nobari, S.
Lu, X.
Karras, P. 
Bressan, S. 
Keywords: Erdos-Rényi
Gilbert
Parallel algorithm
Random graphs
Issue Date: 2011
Source: Nobari, S.,Lu, X.,Karras, P.,Bressan, S. (2011). Fast random graph generation. ACM International Conference Proceeding Series : 331-342. ScholarBank@NUS Repository. https://doi.org/10.1145/1951365.1951406
Abstract: Today, several database applications call for the generation of random graphs. A fundamental, versatile random graph model adopted for that purpose is the Erdos-Rényi Γv,p model. This model can be used for directed, undirected, and multipartite graphs, with and without self-loops; it induces algorithms for both graph generation and sampling, hence is useful not only in applications necessitating the generation of random structures but also for simulation, sampling and in randomized algorithms. However, the commonly advocated algorithm for random graph generation under this model performs poorly when generating large graphs, and fails to make use of the parallel processing capabilities of modern hardware. In this paper, we propose PPreZER, an alternative, data parallel algorithm for random graph generation under the Erdos-Rényi model, designed and implemented in a graphics processing unit (GPU). We are led to this chief contribution of ours via a succession of seven intermediary algorithms, both sequential and parallel. Our extensive experimental study shows an average speedup of 19 for PPreZER with respect to the baseline algorithm.
Source Title: ACM International Conference Proceeding Series
URI: http://scholarbank.nus.edu.sg/handle/10635/41403
ISBN: 9781450305280
DOI: 10.1145/1951365.1951406
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

20
checked on Dec 13, 2017

Page view(s)

67
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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