Please use this identifier to cite or link to this item:
Title: Fast random graph generation
Authors: Nobari, S.
Lu, X.
Karras, P. 
Bressan, S. 
Keywords: Erdos-Rényi
Parallel algorithm
Random graphs
Issue Date: 2011
Citation: Nobari, S.,Lu, X.,Karras, P.,Bressan, S. (2011). Fast random graph generation. ACM International Conference Proceeding Series : 331-342. ScholarBank@NUS Repository.
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
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.


checked on Sep 19, 2019

Page view(s)

checked on Sep 9, 2019

Google ScholarTM



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