More Web Proxy on the site http://driver.im/

research-article

STIC-D: algorithmic techniques for efficient parallel pagerank computation on real-world graphs

Authors:

Kishore KothapalliAuthors Info & Claims

ICDCN '16: Proceedings of the 17th International Conference on Distributed Computing and Networking

Article No.: 15, Pages 1 - 10

https://doi.org/10.1145/2833312.2833322

Published: 04 January 2016 Publication History

Abstract

Computing metrics on nodes of a graph is an essential step in understanding the properties of the graph. Pagerank is one such metric that is popular and is being used to measure the importance of nodes in not only web graphs but also in social networks, biological networks, road networks, and the like. The core of the computation of pagerank can be seen as an iterative approach that updates the pageranks of nodes until the values converge.

However, as real-world graphs such as road networks and the web have a large size, one needs to design efficient techniques to address the challenges of scale. In addition to parallelism that can be exploited, it is important to also look for specific properties of graphs and their impact on the algorithm.

In this paper, we present four algorithmic techniques that optimize the pagerank computation on real-world graphs. The techniques are presented with the aim of exploiting the nature of the real-world graphs and eliminating redundancies in the pagerank computation. Our techniques also have the advantage that with little extra effort one can quickly identify which of the techniques will be suitable for a given input graph.

We implement our algorithm on an Intel i7 980x CPU running 12 threads using OpenMP Version 3.0. We study our techniques on four classes of real-world graphs: web graphs, social networks, citation and collaboration networks, and road networks. Our implementation achieves an average speedup of 32% compared to a baseline implementation.

References

[1]

Stanford network analysis platform dataset. http://www.cise.uïňĆ.edu/research/sparse/matrices/SNAP.

[2]

The University of Florida Sparse Matrix Collection. http://www.cise.ufl.edu/research/sparse/matrices/.

[3]

Albert, R., Jeong, H., and Barabási, A.-L. Internet: Diameter of the world-wide web. Nature 401, 6749 (1999), 130--131.

[4]

Arasu, A., Novak, J., Tomkins, A., and Tomlin, J. Pagerank computation and the structure of the web: Experiments and algorithms. In Proceedings of the Eleventh International World Wide Web Conference, Poster Track (2002), pp. 107--117.

[5]

Backstrom, L., Huttenlocher, D., Kleinberg, J., and Lan, X. Group formation in large social networks: membership, growth, and evolution. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (2006), ACM, pp. 44--54.

Digital Library

[6]

Banerjee, D. S., Kumar, A., Chaitanya, M., Sharma, S., and Kothapalli, K. Work efficient parallel algorithms for large graph exploration on emerging heterogeneous architectures. JPDC 76 (2015), 81--93.

Digital Library

[7]

Banerjee, D. S., Sharma, S., and Kothapalli, K. Work efficient parallel algorithms for large graph exploration. In HiPC (2013).

[8]

Boldi, P., Rosa, M., Santini, M., and Vigna, S. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In Proceedings of the 20th international conference on World Wide Web (2011), ACM Press.

Digital Library

[9]

Boldi, P., and Vigna, S. The WebGraph framework I: Compression techniques. In Proc. of the Thirteenth International World Wide Web Conference (WWW 2004) (Manhattan, USA, 2004), ACM Press, pp. 595--601.

Digital Library

[10]

Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J. Graph structure in the web. Computer Networks 33, 1--6 (2000), 309--320.

Digital Library

[11]

Broder, A. Z., Lempel, R., Maghoul, F., and Pedersen, J. O. Efficient pagerank approximation via graph aggregation. In Proceedings of the 13th international conference on World Wide Web (2004), pp. 484--485.

Digital Library

[12]

Cong, G., and Bader, D. A. An experimental study of parallel biconnected components algorithms on symmetric multiprocessors (smps). In Proc. IEEE IPDPS (2005).

Digital Library

[13]

Cormen, Leiserson, Rivest, and Stein. Introduction To Algorithms. Prentice Hall.

Digital Library

[14]

Duong, N. T., Nguyen, Q. A. P., Nguyen, A. T., and Nguyen, H.-D. Parallel pagerank computation using gpus. In Proceedings of the Third Symposium on Information and Communication Technology (2012), SoICT '12, pp. 223--230.

Digital Library

[15]

Eiron, N., McCurley, K. S., and Tomlin, J. A. Ranking the web frontier. In Proceedings of the 13th international conference on World Wide Web (2004), pp. 309--318.

Digital Library

[16]

Geisberger, R., Sanders, P., and Schultes, D. Better approximation of betweenness centrality. In ALENEX (2008), SIAM, pp. 90--100.

Digital Library

[17]

Gleich, D. F. PageRank beyond the web. arXiv cs.SI (2014), 1407.5107. Accepted for publication in SIAM Review.

[18]

Hong, S., Rodia, N. C., and Olukotun, K. On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs. In Proc. of SC'13 (2013).

Digital Library

[19]

Kamvar, S., Haveliwala, T., Manning, C., and Golub, G. Exploiting the block structure of the web for computing pagerank. Tech. Rep. 2003-17, Stanford University, 2003.

[20]

Kohlschutter, C., Chirita, P.-A., and Nejdl, W. Efficient parallel computation of pagerank. In Proc. of the 28th European Conference on IR Research (2006), pp. 241--252.

Digital Library

[21]

Leskovec, J., Lang, K., Dasgupta, A., and Mahoney, M. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters.

[22]

Page, L., Brin, S., Motwani, R., and Winograd, T. The pagerank citation ranking: bringing order to the web.

[23]

Richardson, M., Agrawal, R., and Domingos, P. Trust management for the semantic web. In The Semantic Web-ISWC 2003. Springer, 2003, pp. 351--368.

[24]

Sarma, A. D., Molla, A. R., Pandurangan, G., and Upfal, E. Fast distributed pagerank computation. In Proc. of ICDCN (2013), pp. 11--26.

[25]

SarÄŚyuce, A. E., Saüle, E., Kaya, K., and Çatalyürek, U. V. Shattering and compressing networks for betweenness centrality. In SIAM Data Mining (2013).

[26]

Slota, K. G., and Madduri, K. Simple parallel biconnectivity algorithms for multicore platforms. In HiPC (2014), pp. 1--10.

[27]

Wang, Y., and DeWitt, D. J. Computing pagerank in a distributed internet search engine system. In Proceedings of the Thirtieth International Conference on Very Large Data Bases (2004), pp. 420--431.

Digital Library

[28]

Wu, J., and Aberer, K. Using siterank for decentralized computation of web document ranking. In Proc. of the Third Workshop on Adaptive Hypermedia and Adaptive Web-Based Systems (2004), pp. 265--274.

Cited By

Sahu SKothapalli KEedi HPeri S(2024)Lock-free Computation of PageRank in Dynamic Graphs2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00148(825-834)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00148
Sahu SKothapalli KEedi HPeri S(2024)DF* PageRank: Incrementally Expanding Approaches for Updating PageRank on Dynamic GraphsEuro-Par 2024: Parallel Processing10.1007/978-3-031-69583-4_22(312-326)Online publication date: 26-Aug-2024
https://doi.org/10.1007/978-3-031-69583-4_22
Eedi HKarra SPeri SRanabothu NUtkoor R(2022)An Improved/Optimized Practical Non-Blocking PageRank Algorithm for Massive Graphs*International Journal of Parallel Programming10.1007/s10766-022-00725-650:3-4(381-404)Online publication date: 26-Mar-2022
https://doi.org/10.1007/s10766-022-00725-6
Show More Cited By

Index Terms

STIC-D: algorithmic techniques for efficient parallel pagerank computation on real-world graphs
1. Theory of computation
  1. Design and analysis of algorithms
    1. Parallel algorithms

Recommendations

High Performance Detection of Strongly Connected Components in Sparse Graphs on GPUs
PMAM'17: Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores

Detecting strongly connected components (SCC) has been broadly used in many real-world applications. To speedup SCC detection for large-scale graphs, parallel algorithms have been proposed to leverage modern GPUs. Existing GPU implementations are able ...
Orchestrating parallel detection of strongly connected components on GPUs
Highlights
- Analysis on graph properties: skewed SCC sizes and dynamically changing structure.
Abstract
Detecting strongly connected components (SCC) is a practical graph analytics algorithm widely used in many application domains. To accelerate SCC detection, parallel algorithms have been proposed and implemented on GPUs. However, ...
Mars: Accelerating MapReduce with Graphics Processors

We design and implement Mars, a MapReduce runtime system accelerated with graphics processing units (GPUs). MapReduce is a simple and flexible parallel programming paradigm originally proposed by Google, for the ease of large-scale data processing on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICDCN '16: Proceedings of the 17th International Conference on Distributed Computing and Networking

January 2016

370 pages

ISBN:9781450340328

DOI:10.1145/2833312

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 January 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICDCN '16

ICDCN '16: 17th International Conference on Distributed Computing and Networking

January 4 - 7, 2016

Singapore, Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
161
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sahu SKothapalli KEedi HPeri S(2024)Lock-free Computation of PageRank in Dynamic Graphs2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00148(825-834)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00148
Sahu SKothapalli KEedi HPeri S(2024)DF* PageRank: Incrementally Expanding Approaches for Updating PageRank on Dynamic GraphsEuro-Par 2024: Parallel Processing10.1007/978-3-031-69583-4_22(312-326)Online publication date: 26-Aug-2024
https://doi.org/10.1007/978-3-031-69583-4_22
Eedi HKarra SPeri SRanabothu NUtkoor R(2022)An Improved/Optimized Practical Non-Blocking PageRank Algorithm for Massive Graphs*International Journal of Parallel Programming10.1007/s10766-022-00725-650:3-4(381-404)Online publication date: 26-Mar-2022
https://doi.org/10.1007/s10766-022-00725-6
Eedi HPeri SRanabothu NUtkoor R(2021)An Efficient Practical Non-Blocking PageRank Algorithm for Large Scale Graphs2021 29th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)10.1109/PDP52278.2021.00015(35-43)Online publication date: Mar-2021
https://doi.org/10.1109/PDP52278.2021.00015
Chandramouli AJana SKothapalli K(2021)Efficient Parallel Algorithms for Computing Percolation Centrality2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC)10.1109/HiPC53243.2021.00025(111-120)Online publication date: Dec-2021
https://doi.org/10.1109/HiPC53243.2021.00025
Regunta STondomker SShukla KKothapalli K(2021)Efficient parallel algorithms for dynamic closeness‐ and betweenness centralityConcurrency and Computation: Practice and Experience10.1002/cpe.665035:17Online publication date: 29-Sep-2021
https://doi.org/10.1002/cpe.6650
Giri HHaque MBanerjee D(2020)HyPR: Hybrid Page Ranking on Evolving Graphs2020 IEEE 27th International Conference on High Performance Computing, Data, and Analytics (HiPC)10.1109/HiPC50609.2020.00020(62-71)Online publication date: Dec-2020
https://doi.org/10.1109/HiPC50609.2020.00020
Eedi HKokkula M(2020)Parallel PageRank Algorithm Using MapReduceICDSMLA 201910.1007/978-981-15-1420-3_85(787-795)Online publication date: 19-May-2020
https://doi.org/10.1007/978-981-15-1420-3_85
Regunta STondomker SKothapalli K(2019)BRICS – Efficient Techniques for Estimating the Farness-Centrality in Parallel2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW.2019.00110(645-654)Online publication date: May-2019
https://doi.org/10.1109/IPDPSW.2019.00110
Panyala ASubasi OHalappanavar MKalyanaraman AChavarria-Miranda DKrishnamoorthy S(2017)Approximate Computing Techniques for Iterative Graph Algorithms2017 IEEE 24th International Conference on High Performance Computing (HiPC)10.1109/HiPC.2017.00013(23-32)Online publication date: Dec-2017
https://doi.org/10.1109/HiPC.2017.00013

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents