Cited 0 time in webofscience Cited 0 time in scopus

TrillionG: A trillion-scale synthetic graph generator using a recursive vector model

Title
TrillionG: A trillion-scale synthetic graph generator using a recursive vector model
Authors
Park, HimchanKim, Min-Soo
DGIST Authors
Park, Himchan; Kim, Min-Soo
Issue Date
2017
Citation
2017 ACM SIGMOD International Conference on Management of Data, SIGMOD 2017, Part F127746, 913-928
Type
Conference
Article Type
Conference Paper
ISBN
9781450000000
ISSN
0730-8078
Abstract
As many applications encounter exponential growth in graph sizes, a fast and scalable graph generator has become more important than ever before due to lack of large-scale realistic graphs for evaluating the performance of graph processing methods. Although there have been proposed a number of methods to generate synthetic graphs, they are not very efficient in terms of space and time complexities, and so, cannot generate even trillion-scale graphs using a moderate size cluster of commodity machines. Here, we propose an efficient and scalable disk-based graph generator, TrillionG that can generate massive graphs in a short time only using a small amount of memory. It can generate a graph of a trillion edges following the RMAT or Kronecker models within two hours only using 10 PCs. We first generalize existing graph generation models to the scope-based generation model, where RMAT and Kronecker correspond to two extremes. Then, we propose a new graph generation model called the recursive vector model, which compromises two extremes, and so, solves the space and time complexity problems existing in RMAT and Kronecker. We also extend the recursive vector model so as to generate a semantically richer graph database. Through extensive experiments, we have demonstrated that TrillionG outperforms the state-of-the-art graph generators by up to orders of magnitude. © 2017 ACM.
URI
http://hdl.handle.net/20.500.11750/4313
DOI
10.1145/3035918.3064014
Publisher
Association for Computing Machinery
Related Researcher
Files:
There are no files associated with this item.
Collection:
Information and Communication EngineeringETC2. Conference Papers


qrcode mendeley

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

BROWSE