Fast Random Graph Generation

Sadegh Heyrani Nobari, Xuesong Lu, Panagiotis Karras, Stephane Bressan
National University of Singapore
14th International Conference on Extending Database Technology (EDBT), 2011


   title={Fast random graph generation},

   author={Nobari, S. and Lu, X. and Karras, P. and Bressan, S.},

   booktitle={Proceedings of the 14th International Conference on Extending Database Technology},





Download Download (PDF)   View View   Source Source   Source codes Source codes




Today, several database applications call for the generation of random graphs. A fundamental, versatile random graph model adopted for that purpose is the Erdos-Renyi Gamma_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-Renyi 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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: