No More Leaky PageRank
Event Type
Workshop
Algorithms
Architectures
Big Data
Data Analytics
Memory Systems
Numerical Algorithms
W
TimeMonday, 15 November 202112pm - 12:30pm CST
Location224
DescriptionWe have surveyed multiple PageRank implementations available with popular graph processing frameworks, and discovered that they treat sink vertices (i.e., vertices without outgoing edges) incorrectly. This leads to two issues: (i) incorrect PageRank scores, and (ii) flawed performance evaluations (as costly scatter operations are avoided). For synchronous PageRank implementations, a strategy to fix these issues exists (accumulating values from sinks during an algorithmic superstep of a PageRank iteration), albeit with sizeable overhead. This solution, however, is not applicable to asynchronous frameworks.
We present and evaluate a novel, low-cost algorithmic solution to address this issue. For asynchronous PageRank, our solution simply requires an inexpensive O(Vertex) computation performed alongside the final normalization step. We also show that this strategy has advantages over prior work for synchronous PageRank, as it both avoids graph restructuring and reduces inline computation costs by performing a final score reassignment to vertices once at the end of processing.
We present and evaluate a novel, low-cost algorithmic solution to address this issue. For asynchronous PageRank, our solution simply requires an inexpensive O(Vertex) computation performed alongside the final normalization step. We also show that this strategy has advantages over prior work for synchronous PageRank, as it both avoids graph restructuring and reduces inline computation costs by performing a final score reassignment to vertices once at the end of processing.
