GBASE: A Scalable and general graph management system

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

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationProceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'11
Pages1091-1099
Number of pages9
DOIs
StatePublished - Sep 16 2011
Event17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'11 - San Diego, CA, United States
Duration: Aug 21 2011Aug 24 2011

Publication series

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

Other

Other17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'11
CountryUnited States
CitySan Diego, CA
Period8/21/118/24/11

Keywords

  • Compression
  • Distributed computing
  • Graph
  • Indexing

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'GBASE: A Scalable and general graph management system'. Together they form a unique fingerprint.

  • 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). https://doi.org/10.1145/2020408.2020580