Skip to Main Content
 

Global Search Box

 
 
 

ETD Abstract Container

Abstract Header

Incremental PageRank acceleration using Sparse Matrix-Sparse Vector Multiplication

Ramachandran, Shridhar
http://orcid.org/0000-0003-1095-3940
http://rave.ohiolink.edu/etdc/view?acc_num=osu1462894358

Abstract Details

2016, Master of Science, Ohio State University, Computer Science and Engineering.
PageRank is an important measure to evaluate the relative importance of a node within a graph. Traditional linear algebraic methods to compute PageRank scores of nodes in a graph include the power method, which involves an iterative series of Sparse Matrix Vector multiplication (SpMV) operations. As graphs dynamically change over time, it becomes important to keep the PageRank scores updated in an efficient manner. Through the work done in this thesis, we try and solve this problem of efficiently updating PageRank scores by devising an algorithm that formulates the power method computation on the updated graph as a series of Sparse Matrix Sparse Vector (SpMSpV) multiplication operations - a method that improves upon the naive technique of recomputing PageRank scores from scratch. We present a rigorous mathematical proof for this. We also include several optimizations in our design and implementation of the algorithm based on theoretical and heuristic observations of the SpMSpV routine and our mathematical formulation of incremental PageRank. In addition to these optimizations, we implement a smart threshold-based technique during the SpMSpV routine to calculate a high quality approximation of PageRank scores, while improving efficiency significantly. Many of these optimization and approximation techniques were extended in the multicore and GPU implementations of our algorithm. We show promising empirical results for a wide variety of scale-free graphs.
Ponnuswamy Sadayappan, Dr (Advisor)
Srinvasan Parthasarathy, Dr (Committee Member)
43 p.
Computer Science
Incremental PageRank; SpMSpV

Recommended Citations

Citations

  • Ramachandran, S. (2016). Incremental PageRank acceleration using Sparse Matrix-Sparse Vector Multiplication [Master's thesis, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1462894358

    APA Style (7th edition)

  • Ramachandran, Shridhar. Incremental PageRank acceleration using Sparse Matrix-Sparse Vector Multiplication. 2016. Ohio State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1462894358.

    MLA Style (8th edition)

  • Ramachandran, Shridhar. "Incremental PageRank acceleration using Sparse Matrix-Sparse Vector Multiplication." Master's thesis, Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1462894358

    Chicago Manual of Style (17th edition)

osu1462894358
3,176
© 2016, some rights reserved.Creative Commons License Incremental PageRank acceleration using Sparse Matrix-Sparse Vector Multiplication by Shridhar Ramachandran is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by The Ohio State University and OhioLINK.