KIT | KIT-Bibliothek | Impressum | Datenschutz

Linear work generation of R-MAT graphs

Hübschle-Schneider, L.; Sanders, P.

R-MAT (for Recursive MATrix) is a simple, widely used model for generating graphs with a power law degree distribution, a small diameter, and communitys structure. It is particularly attractive for generating very large graphs because edges can be generated independently by an arbitrary number of processors. However, current R-MAT generators need time logarithmic in the number of nodes for generating an edge— constant time for generating one bit at a time for node IDs of the connected nodes. We achieve constant time per edge by precomputing pieces of node IDs of logarithmic length. Using an alias table data structure, these pieces can then be sampled in constant time. This simple technique leads to practical improvements by an order of magnitude. This further pushes the limits of attainable graph size and makes generation overhead negligible in most situations.

Open Access Logo

Verlagsausgabe §
DOI: 10.5445/IR/1000120771
Veröffentlicht am 11.07.2020
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2020
Sprache Englisch
Identifikator ISSN: 2050-1242, 2050-1250
KITopen-ID: 1000120771
Erschienen in Network science
Vorab online veröffentlicht am 29.05.2020
Schlagwörter graph generator, parallel processing, large graphs, bit parallelism, sampling
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page