TY - GEN

T1 - Efficient processing of large graphs via input reduction

AU - Kusum, Amlan

AU - Vora, Keval

AU - Gupta, Rajiv

AU - Neamtiu, Iulian

N1 - Publisher Copyright:
Copyright © 2016 by the Association for Computing Machinery, Inc. (ACM).
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 2016/5/31

Y1 - 2016/5/31

N2 - 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).

AB - 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).

KW - Graph processing

KW - Input reduction

KW - Iterative algorithms

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

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

U2 - 10.1145/2907294.2907312

DO - 10.1145/2907294.2907312

M3 - Conference contribution

AN - SCOPUS:84978477229

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

SP - 245

EP - 257

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

PB - Association for Computing Machinery, Inc

T2 - 25th ACM International Symposium on High-Performance Parallel and Distributed Computing, HPDC 2016

Y2 - 31 May 2016 through 4 June 2016

ER -