GBASE: A Scalable and general graph management system

U. Kang; Hanghang Tong; Jimeng Sun; Ching Yung Lin; Christos Faloutsos

doi:10.1145/2020408.2020580

GBASE: A Scalable and general graph management system

U. Kang, Hanghang Tong, Jimeng Sun, Ching Yung Lin, Christos Faloutsos

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Graphs appear in numerous applications including cyber-security, the Internet, social networks, protein networks, recommendation systems, and many more. Graphs with millions or even billions of nodes and edges are common-place. How to store such large graphs efficiently? What are the core operations/queries on those graph? How to answer the graph queries quickly? We propose GBASE, a scalable and general graph management and mining system. The key novelties lie in 1) our storage and compression scheme for a parallel setting and 2) the carefully chosen graph operations and their efficient implementation. We designed and implemented an instance of GBASE using MAPREDUCE/HADOOP. GBASE provides a parallel indexing mechanism for graph mining operations that both saves storage space, as well as accelerates queries. We ran numerous experiments on real graphs, spanning billions of nodes and edges, and we show that our proposed GBASE is indeed fast, scalable and nimble, with significant savings in space and time.

Original language	English (US)
Title of host publication	Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'11
Publisher	Association for Computing Machinery
Pages	1091-1099
Number of pages	9
ISBN (Print)	9781450308137
DOIs	https://doi.org/10.1145/2020408.2020580
State	Published - 2011
Event	17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2011 - San Diego, United States Duration: Aug 21 2011 → Aug 24 2011

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Conference

Conference	17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2011
Country/Territory	United States
City	San Diego
Period	8/21/11 → 8/24/11

Keywords

Compression
Distributed computing
Graph
Indexing

ASJC Scopus subject areas

Software
Information Systems

Online availability

10.1145/2020408.2020580

Library availability

Discover UIUC Full Text

Cite this

Kang, U., Tong, H., Sun, J., Lin, C. Y., & Faloutsos, C. (2011). GBASE: A Scalable and general graph management system. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'11 (pp. 1091-1099). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). Association for Computing Machinery. https://doi.org/10.1145/2020408.2020580

GBASE: A Scalable and general graph management system. / Kang, U.; Tong, Hanghang ; Sun, Jimeng et al.
Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'11. Association for Computing Machinery, 2011. p. 1091-1099 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kang, U, Tong, H , Sun, J, Lin, CY & Faloutsos, C 2011, GBASE: A Scalable and general graph management system. in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'11. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery, pp. 1091-1099, 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2011, San Diego, United States, 8/21/11. https://doi.org/10.1145/2020408.2020580

Kang U, Tong H , Sun J, Lin CY, Faloutsos C. GBASE: A Scalable and general graph management system. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'11. Association for Computing Machinery. 2011. p. 1091-1099. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/2020408.2020580

@inproceedings{aa6e2f484ac149a58efbec6d10f60a51,

title = "GBASE: A Scalable and general graph management system",

abstract = "Graphs appear in numerous applications including cyber-security, the Internet, social networks, protein networks, recommendation systems, and many more. Graphs with millions or even billions of nodes and edges are common-place. How to store such large graphs efficiently? What are the core operations/queries on those graph? How to answer the graph queries quickly? We propose GBASE, a scalable and general graph management and mining system. The key novelties lie in 1) our storage and compression scheme for a parallel setting and 2) the carefully chosen graph operations and their efficient implementation. We designed and implemented an instance of GBASE using MAPREDUCE/HADOOP. GBASE provides a parallel indexing mechanism for graph mining operations that both saves storage space, as well as accelerates queries. We ran numerous experiments on real graphs, spanning billions of nodes and edges, and we show that our proposed GBASE is indeed fast, scalable and nimble, with significant savings in space and time.",

keywords = "Compression, Distributed computing, Graph, Indexing",

author = "U. Kang and Hanghang Tong and Jimeng Sun and Lin, {Ching Yung} and Christos Faloutsos",

year = "2011",

doi = "10.1145/2020408.2020580",

language = "English (US)",

isbn = "9781450308137",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery",

pages = "1091--1099",

booktitle = "Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'11",

address = "United States",

note = "17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2011 ; Conference date: 21-08-2011 Through 24-08-2011",

}

TY - GEN

T1 - GBASE

T2 - 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2011

AU - Kang, U.

AU - Tong, Hanghang

AU - Sun, Jimeng

AU - Lin, Ching Yung

AU - Faloutsos, Christos

PY - 2011

Y1 - 2011

N2 - Graphs appear in numerous applications including cyber-security, the Internet, social networks, protein networks, recommendation systems, and many more. Graphs with millions or even billions of nodes and edges are common-place. How to store such large graphs efficiently? What are the core operations/queries on those graph? How to answer the graph queries quickly? We propose GBASE, a scalable and general graph management and mining system. The key novelties lie in 1) our storage and compression scheme for a parallel setting and 2) the carefully chosen graph operations and their efficient implementation. We designed and implemented an instance of GBASE using MAPREDUCE/HADOOP. GBASE provides a parallel indexing mechanism for graph mining operations that both saves storage space, as well as accelerates queries. We ran numerous experiments on real graphs, spanning billions of nodes and edges, and we show that our proposed GBASE is indeed fast, scalable and nimble, with significant savings in space and time.

AB - Graphs appear in numerous applications including cyber-security, the Internet, social networks, protein networks, recommendation systems, and many more. Graphs with millions or even billions of nodes and edges are common-place. How to store such large graphs efficiently? What are the core operations/queries on those graph? How to answer the graph queries quickly? We propose GBASE, a scalable and general graph management and mining system. The key novelties lie in 1) our storage and compression scheme for a parallel setting and 2) the carefully chosen graph operations and their efficient implementation. We designed and implemented an instance of GBASE using MAPREDUCE/HADOOP. GBASE provides a parallel indexing mechanism for graph mining operations that both saves storage space, as well as accelerates queries. We ran numerous experiments on real graphs, spanning billions of nodes and edges, and we show that our proposed GBASE is indeed fast, scalable and nimble, with significant savings in space and time.

KW - Compression

KW - Distributed computing

KW - Graph

KW - Indexing

UR - http://www.scopus.com/inward/record.url?scp=80052662600&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052662600&partnerID=8YFLogxK

U2 - 10.1145/2020408.2020580

DO - 10.1145/2020408.2020580

M3 - Conference contribution

AN - SCOPUS:80052662600

SN - 9781450308137

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 1091

EP - 1099

BT - Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'11

PB - Association for Computing Machinery

Y2 - 21 August 2011 through 24 August 2011

ER -

GBASE: A Scalable and general graph management system

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this