Efficient processing of large graphs via input reduction

Amlan Kusum, Keval Vora, Rajiv Gupta, Iulian Neamtiu

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

16 Scopus citations

Abstract

Large-scale parallel graph analytics involves executing iterative algorithms (e.g., PageRank, Shortest Paths, etc.) that are both data- and compute-intensive. In this work we construct faster versions of iterative graph algorithms from their original counterparts using input graph reduction. A large input graph is transformed into a small graph using a sequence of input reduction transformations. Savings in execution time are achieved using our two phased processing model that effectively runs the original iterative algorithm in two phases: first, using the reduced input graph to gain savings in execution time; and second, using the original input graph along with the results from the first phase for computing precise results. We propose several input reduction transformations and identify the structural and non-structural properties that they guarantee, which in turn are used to ensure the correctness of results while using our two phased processing model. We further present a unified input reduction algorithm that efficiently applies a non-interfering sequence of simple local input reduction transformations. Our experiments show that our transformation techniques enable significant reductions in execution time (1.25×-2.14×) while achieving precise final results for most of the algorithms. For cases where precise results cannot be achieved, the relative error remains very small (at most 0.065).

Original languageEnglish (US)
Title of host publicationHPDC 2016 - Proceedings of the 25th ACM International Symposium on High-Performance Parallel and Distributed Computing
PublisherAssociation for Computing Machinery, Inc
Pages245-257
Number of pages13
ISBN (Electronic)9781450343145
DOIs
StatePublished - May 31 2016
Event25th ACM International Symposium on High-Performance Parallel and Distributed Computing, HPDC 2016 - Kyoto, Japan
Duration: May 31 2016Jun 4 2016

Publication series

NameHPDC 2016 - Proceedings of the 25th ACM International Symposium on High-Performance Parallel and Distributed Computing

Other

Other25th ACM International Symposium on High-Performance Parallel and Distributed Computing, HPDC 2016
Country/TerritoryJapan
CityKyoto
Period5/31/166/4/16

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Software

Keywords

  • Graph processing
  • Input reduction
  • Iterative algorithms

Fingerprint

Dive into the research topics of 'Efficient processing of large graphs via input reduction'. Together they form a unique fingerprint.

Cite this