Bridging the GAP: Towards approximate graph analytics

Anand Padmanabha Iyer, Aurojit Panda, Shivaram Venkataraman, Mosharaf Chowdhury, Aditya Akella, Scott Shenker, Ion Stoica

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

While there has been a tremendous interest in processing data that has an underlying graph structure, existing distributed graph processing systems take several minutes or even hours to execute popular graph algorithms. However, in several cases, providing an approximate answer is good enough. Approximate analytics is seeing considerable attention in big data due to its ability to produce timely results by trading accuracy, but they do not support graph analytics. In this paper, we bridge this gap and take a first attempt at realizing approximate graph analytics. We discuss how traditional approximate analytics techniques do not carry over to the graph usecase. Leveraging the characteristics of graph properties and algorithms, we propose a graph sparsification technique, and a machine learning based approach to choose the apt amount of sparsification required to meet a given budget. Our preliminary evaluations show encouraging results.

Original languageEnglish (US)
Title of host publicationProceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), GRADES-NDA 2018
EditorsArnab Bhattacharya, George Fletcher, Shourya Roy, Akhil Arora, Josep Lluis Larriba Pey, Robert West
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450356954
DOIs
StatePublished - Jun 10 2018
Event1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics, GRADES-NDA 2018 - Houston, United States
Duration: Jun 10 2018 → …

Publication series

NameProceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), GRADES-NDA 2018

Other

Other1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics, GRADES-NDA 2018
CountryUnited States
CityHouston
Period6/10/18 → …

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Information Systems

Fingerprint Dive into the research topics of 'Bridging the GAP: Towards approximate graph analytics'. Together they form a unique fingerprint.

  • Cite this

    Iyer, A. P., Panda, A., Venkataraman, S., Chowdhury, M., Akella, A., Shenker, S., & Stoica, I. (2018). Bridging the GAP: Towards approximate graph analytics. In A. Bhattacharya, G. Fletcher, S. Roy, A. Arora, J. L. Larriba Pey, & R. West (Eds.), Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), GRADES-NDA 2018 [a10] (Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), GRADES-NDA 2018). Association for Computing Machinery, Inc. https://doi.org/10.1145/3210259.3210269