KIT | KIT-Bibliothek | Impressum | Datenschutz

Linear work generation of R-MAT graphs

Hübschle-Schneider, L. 1; Sanders, P. ORCID iD icon 1
1 Karlsruher Institut für Technologie (KIT)

Abstract:

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.


Verlagsausgabe §
DOI: 10.5445/IR/1000120771
Veröffentlicht am 11.07.2020
Originalveröffentlichung
DOI: 10.1017/nws.2020.21
Scopus
Zitationen: 5
Dimensions
Zitationen: 5
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 12.2020
Sprache Englisch
Identifikator ISSN: 2050-1242, 2050-1250
KITopen-ID: 1000120771
HGF-Programm 46.12.02 (POF III, LK 01) Data Activities
Erschienen in Network science
Verlag Cambridge University Press (CUP)
Band 8
Heft 4
Seiten 543-550
Vorab online veröffentlicht am 29.05.2020
Schlagwörter graph generator, parallel processing, large graphs, bit parallelism, sampling
Nachgewiesen in Dimensions
Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page